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

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

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

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

下面是MapReduce中典型示例:计算文件中的单词个数的实现(Go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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//次数相加
}