Pregel—workflow的一种解决途径

五月 27th, 2011 by klose | No Comments | Filed in mapreduce

来自http://www.royans.net/arch/pregel-googles-other-data-processing-infrastructure/说明google有20%的计算由Pregel完成: “   Inside Google, MapReduce is used for 80% of all the data processing needs. That includes indexing web content, running the clustering engine for Google News, generating reports for popular queries (Google Trends), processing satellite imagery , language model processing for statistical machine translation and  even mundane tasks like data backup and restore. The other 20% is handled by a lesser known infrastructure called “Pregel” which is optimized to mine relationships from “graphs”.” google在SIGMOD2010上就Pregel发表了一篇论文,以下是阅读笔记: Pregel:

Java并发编程总结—Hadoop核心源码实例解读

五月 26th, 2011 by klose | No Comments | Filed in mapreduce, 互联网应用, 求职技术, 编程点滴

程序设计需要同步(synchronization),原因: 1)复杂的功能要求的需要使用多线程编程,线程之间存在读写共享变量。 2)读写共享变量(shared mutual variable),JVM的内存模型(Memory model: decide when and how changes made by one thread become visuble to others)受到其它因素干扰。 3)对共享变量的操作非原子性。例如 i++;就不是原子操作,它分为两部分,(1) 读i (2) i+1写入内存。如果i是线程A和线程B共享的变量,线程A在操作(1)之后,线程调度器调度调度线程B执行i++,因此两个线程在变量i产生了不一致。注意,volatile修饰符是线程操作之前更新数据,但是,上面的问题显然不是更新数据就能解决的。 4)增加互斥区(mutual exclusion)会降低执行效率,但是这是实现数据安全、功能强大的多线程编程最为重要的部分。 5)线程之间需要

Tags: , , ,

数组top K的数

五月 25th, 2011 by klose | No Comments | Filed in 求职技术, 编程点滴

给定数组,求top K的数。 算法思路: 使用快排插入排序的做法,在每次迭代求得数组第一个元素需要插入的位置m, 1)如果m恰好为k或者k-1,则停止迭代,当前数组的前k个位置的数即是前K大的数。 2)如果m < k-1, 那么只需继续对于(m+1,length)进行迭代即可。 3)如果m > k, 继续(l, m-1)迭代。 代码献上: #include <stdio.h> #include <stdlib.h> #include <unistd.h> void getRand(int* data, int length) { int i; srand((unsigned int) getpid()); //generate the array using rand() for (i = 0; i < length; i++) { data[i] = rand() % 1000; } //print the array printf(“generate the array using rand:\n”); for (i = 0; i < length; i++) { printf(“%d “, data[i]); } } int length;

Hadoop如何组织中间数据的存储和传输(源码级分析)1

五月 25th, 2011 by klose | No Comments | Filed in mapreduce, 海量数据存储与处理

Hadoop以可扩展、易用、分布式处理海量数据为目标,在海量数据处理领域不断地制造着神话。其中,最为重要的一个特性就是中间数据的使用上。Hadoop将Map阶段产生的结果,不直接存入HDFS,而是放在本地磁盘中作为中间数据存储起来。等到Reduce启动以后,就从Map阶段拉取中间数据。这个过程成为了MapReduce中的一个大家津津乐道的经典过程,但是,它内部是如何实现的呢? 传输其中中间是通过Http方式来传输Map阶段产生的中间文件到Reducer,分析这个过程是如何实现的,首先看Hadoop的执行task的流程。 这里面最引人注意的是Hadoop重新启动了一个Java虚拟机来启动一个Task,这个task可能是MapTask和ReduceTask,这样做是为了用户定义的MapTask和ReduceTask与JobTracker-TaskTracker体系隔离开来,保证安全。另外也使得一些配置参数可以重新设置。 下面貼上

Hadoop的实现查找辞典中的变位词的程序

五月 20th, 2011 by klose | No Comments | Filed in mapreduce

在Programming peals的第一部分介绍了实现变位词的程序。但是,如果处理的海量辞典,单独的机器恐怕很难给出一个合适的答案。于是,我尝试使用Hadoop实现了这个程序。 Map阶段:拆分单词,输出key-value,key:单词内字母重新排序之后的word value:原单词。例如: apple  —map—> <aelpp, apple> Reduce阶段:相同key的<key,value>代表着相同的变位词。于是,我们将所有Iterator获取所有的value,将其添加到HashSet当中,重复的单词只记录一次。  package cn.ict.dpg; import java.io.IOException; import java.util.Arrays; import java.util.HashSet; import java.util.Iterator; import java.util.StringTokenizer; import org.apache.hadoop.conf.Configuration; import org.apache.hadoop.fs.Path

MapReduce学习曲线(初学者)

五月 19th, 2011 by klose | No Comments | Filed in mapreduce, 海量数据存储与处理

Jeaf Dean 在OSDI04上论文:http://labs.google.com/papers/mapreduce.html 然后有如下的列表,请关注klose的分析的文章: MapReduce 1  2  3  4  5 HaLoop: hadoop对于迭代MapReduce的支持,从而丰富应用范围。 部署多个Hadoop集群,资源复用 Data Join MapReduce优化 Hadoop探索 From Binospace, post MapReduce学习曲线(初学者) 文章的脚注信息由WordPress的wp-posturl插件自动生成

Tags: ,

JobHunting — 随机排序算法求第k大的数O(n)

五月 18th, 2011 by klose | No Comments | Filed in 求职技术

基于快速排序思想的随机排列的数组中找第k小的数 在一组随机排列的数组中找出第k小的,这个元素称为k-th Order Statistic。 能想到的最直观的算法肯定是先把这些数排序然后取第k个,时间复杂度和排序算法相同,可以是Θ(nlgn)。 但它也有平均情况下时间复杂度是Θ(n)的算法,基于快速排序思想。算法: 01  02 int partition(int start, int end) 03 { 04     int i, j, pivot=a[start], temp; 05     i = start; 06     j = end; 07  08     while (i < j) 09     { 10         while (a[i] <= pivot && i < end) i++; 11         while (a[j] >= pivot && j > start) j–; 12         if (i < j) 13    

JobHunting — 二分查找

五月 18th, 2011 by klose | No Comments | Filed in 求职技术, 编程点滴

算法不多说了,相信如果有人读过Jon Bentley 的《Programming Pearls》,就会十分重视这个算法了。记得上大学的时候,写的第一个程序也是这个,:-)。 #include <stdio.h> #include <stdlib.h> typedef int DataType; int length = 10; int data[] = {1, 3, 5, 23, 45, 231, 234, 754, 5632, 12345}; int bS(DataType * d, int length, DataType target) { int left = 0, right = length-1, mid; if    (length <= 0) { return -1; } while (left <= right) { mid = (right + left) >> 1; if (d[mid] > target) { right = mid – 1; } else if (d[mid] == target) { return mid; } else { left = mid + 1; } } return -1; } int main (int argc, char* argv[]) { if (argc != 2) { printf(“Usage:binarySear

Tags: ,

Linux系统调用篇1—vfork、fork、clone

五月 15th, 2011 by klose | No Comments | Filed in 编程点滴

下面是转自一个来自与JavaEye的blog:http://memorymyann.iteye.com/blog/235638 下面是blog的内容:大部分的内容都写得很好 fork,vfork,clone都是linux的系统调用,用来创建子进程的(确切说vfork创造出来的是线程)。 先介绍下进程必须的4要点: a.要有一段程序供该进程运行,就像一场戏剧要有一个剧本一样。该程序是可以被多个进程共享的,多场戏剧用一个剧本一样。 b.有起码的私有财产,就是进程专用的系统堆栈空间。 c.有“户口”,既操作系统所说的进程控制块,在linux中具体实现是task_struct d.有独立的存储空间。 当一个进程缺少d条件时候,我们称其为线程。 1.fork 创造的子进程复制了父亲进程的资源,包括内存的内容task_struct内容(2个进程的pid不同)。这里是资源的复制不是指针的复制。下面的例子可以看出 [root@l