MapReduce的变体:HashFold介绍

说到MapReduce计算模型大家应该都清楚。今天我们来看一下MapReduce一个变体：HasFold。

这种模型将MapReduce中一些没有细化的部分，如Map后数据如何排序再进行Reduce等，通过Hash表这一数据结构的性质做了清晰的描述。

HashFold模型的大概过程大概是这样的：

• Map过程在接收原始数据之后，将数据生成key-value对。
• 对于key重复的value，会将两个重复的value传给Fold过程，Fold过程会返回一个新值。

下面是MapReduce中典型示例：计算文件中的单词个数的实现（Go）

package main

import (
	"fmt"
	"io/ioutil"
	"regexp"
	"strings"
)

type Pair struct {
	key   string
	count int
}

func main() {
	fname := "README"
	hash := Start(fname)
	for k, v := range hash {
		fmt.Printf("word:%s,count:%d\n", k, v)
	}
}

func Start(fname string) map[string]int {
	hash := make(map[string]int, 0)
	bytes, _ := ioutil.ReadFile(fname)
	source := string(bytes)
	pairs := Map(source)//调用Map分割输入
	for _, p := range pairs {
		if _, ok := hash[p.key]; !ok {//判断重复
			hash[p.key] = p.count
		} else {//如果重复，调用Fold函数
			hash[p.key] = Fold(hash[p.key], p.count)
		}
	}
	return hash
}

func Map(source string) []Pair {
	pairs := make([]Pair, 0, 0)
	arr := strings.Split(source, "\n")
	re := regexp.MustCompile("[\\pP‘’“”]") 
	for _, line := range arr {
		newLine := re.ReplaceAllString(line, " ")//替换标点符号
		for _, word := range strings.Split(newLine, " ") {
			if word != "" {
				k := strings.ToLower(word)//转换为小写
				pairs = append(pairs, *&Pair{key: k, count: 1})
			}
		}
	}
	return pairs
}

func Fold(v1, v2 int) int {
	return v1 + v2//次数相加
}