Other articles


  1. 理解Hadoop和MapReduce

    为什么需要用到Hadoop

    Hadoop是Apache开源基金会下的一个项目,针对处理大数据的特性设计的分布式编程模型工具。Hadoop的核心思想来源于Google的MapReduce和Google File System(GFS)。通俗来讲,就是将处理的问题分为两个子问题,一个负责将问题分割成一个一个小的部分,另一个负责将前一个步骤的每一部分都合并在一起。

    最常见的例子就是单词统计。假设我们需要统计一个文档里的单词,最简单的方式就是用一个dictionary或者map来存储一个key-value对。一旦发现一个新的单词,我们就在这个dictionary里面添加一个条目,value设为1。如果这个单词已经存在,那么取出这个key对应的value,将其加1。这种方式对于一个小的文档来说固然合适,但如果我们处理的是一个TB,PB级别的数据呢?如果我们想在1秒钟之内就处理完这些数据?这就需要用到分布式处理了,也就是多台机器同时运算。对于数单词这样一个简单的工作,要解决的就是如何分配任务,每一台机器需要处理文档的哪个部分,以及如何将这些结果整合在一起。有了这样的思想,我们可以给这两个部分的工作分配给两个模块,一个是mapper,一个是reducer。mapper负责把问题分割成很小的一部分,每一部分都会产生一个问题的输出;reducer负责把所有若干个mapper产生的输出汇总,再计算出所需的输出。由于这种模型涉及到的数据量都比较大,而建立在大数据上的数据处理一般来说都相对比较简单,因此将这种模型一般化,使用户只需要关注mapper和reducer的具体实现,而不用考虑异常处理,问题分割等等细节问题,这就是Hadoop需要解决的问题。

    但是,并不是所有问题都适合用MapReduce模型解决,比如说PageRank。当问题涉及到图结构的时候,一个很普遍的现象就是活跃节点和不活跃节点差异非常明显 …

    read more

    There are comments.

  2. Constraint Satisfaction Problem

    CSP概述

    作为对学了一个学期的内容的总结,在这里稍微介绍一下Constraint Satisfaction Problem(CSP)吧。这个题目我也不知道中文叫做什么,也许叫做有约束问题解决模型比较合适。虽然我没有学过数学建模,但或许他们之间是比较类似的,CSP的中心思想就是针对一个特定的问题建立模型,然后解决它。解决问题的具体实现就叫做Constraint Solver(约束处理机)。我认为这个方法还是很实际的,它可以帮助我们快速建立起对一个问题的数学角度的认识,同时在编程方面也有很多的函数库,比如说IBM的CPLEX。这里只介绍Gecode的使用,当然官方文档对于Gecode已经解释的很详细了,我在这里只想梳理一下整个建立模型的步骤和稍微介绍一下Gecode。

    Gecode

    Gecode是一个用于解决约束问题的基于C++的函数库,覆盖了Windows,Linux,Mac三个平台。在2012年以前长期霸占着MiniZinc比赛的头名,就现在来说当然性能也不差,而且也一直有更新。关键的是,相比起CPLEX,它是免费开源的。官方主页:Gecode

    问题描述

    在CSP概念里,问题被表示成几个部分:变量(Variable),值域(Domain),约束(Constraint)。变量是问题模型中所有可以改变的量,可以是一组数,也可以是未知的属性,比如说香港的某一所高校 …

    read more

    There are comments.

links

social