algorithm - 使用 Map/Reduce 从多个 Sets 创建 Map

Question

假设有 N 组单词，我想从这些组创建一个映射，以便它将单词映射到所有这些组中单词出现的次数。

例如:

N = 3S1 = {"a", "b", "c"}, S2 = {"a", "b", "d"}, S3 = {"a", "c", "e"}M = { "a" -> 3, "b" -> 2, "c" -> 2, "d" -> 1, "e" -> 1}

现在我有 M 台电脑可以使用。因此，我可以让每台计算机根据 N/M 集创建 map 。在第二(最后)阶段，我可以从 M map 创建 map 。看起来像一个 map/reduce。是否有意义 ？您将如何改进这种方法？

Answer 1

这是标准的 map reduce 示例。

例如，这里是基于 mincemeat map/reduce library 的 Python 代码:

#!/usr/bin/env python
import mincemeat

S1 = {"a", "b", "c"}
S2 = {"a", "b", "d"}
S3 = {"a", "c", "e"}

datasource = dict(enumerate([S1,S2,S3]))

def mapfn(k, v):
    for w in v:
        yield w, 1

def reducefn(k, vs):
    result = sum(vs)
    return result

s = mincemeat.Server()
s.datasource = datasource
s.mapfn = mapfn
s.reducefn = reducefn

results = s.run_server(password="changeme")
print results

打印

{'a': 3, 'c': 2, 'b': 2, 'e': 1, 'd': 1}

请注意，map/reduce 的结构方式意味着服务器会在客户端完成任务时将新任务分配给它们。

这意味着没有必要为每个客户端固定分配 N/M 任务。

如果一个客户端比其他客户端快，那么它最终会被分配更多任务以充分利用可用资源。