Map-reduce 功能概要

Question

注意：这是一个更基本的编程问题，与 Hadoop 或“大数据处理”的 Map/Reduce 方法无关。

让我们看一个序列 (1 2 3 4 5):

要将其映射到某个函数，比方说 square，我可以这样做：

(define (map function sequence)
  ; apply the function to each element in the sequence
  ; we do not reduce it, but return a list
  (if (null? sequence)
      nil
      (cons (function (car sequence))
            (map function (cdr sequence)))))

(map (lambda (x) (* x x)) '(1 2 3 4 5))
; (1 4 9 16 25)

>>> map(lambda x: x*x, [1,2,3,4,5])
# [1, 4, 9, 16, 25]
>>> def mymap(function, sequence):
      return [function(item) for item in sequence]

>>> mymap(lambda x: x*x, [1,2,3,4,5])
# [1, 4, 9, 16, 25]

对于像“map-reduce”这样的东西，它可能有大约三个步骤（我认为？），如果我们假设一个给定的序列：

map
filter（顺序可能会与 map 交换，具体取决于正在做什么）
reduce

这是对 'map-reduce' 范式的正确理解吗？它通常是一个看起来像这样的函数吗：

mapreduce(map_function, filter_function, reduce_function, sequence)

或者合并在一起一般是怎么处理的？

Answer 1

为了给您直觉，我们需要（简要地）离开代码中的具体实现。 MapReduce（我不只是在谈论特定的实现）是关于问题的形状。

假设我们有一个 xs 的线性数据结构（列表、数组等），并且我们有一个要应用于它们中的每一个的转换函数，并且我们有一个可以表示为重复应用的聚合函数关联成对组合的：

    xA           xB
     |           |
  xform(xA)   xform(xB)
       \       /
aggregator(xform(xA), xform(xB))
           |
         value

并且我们可以递归地将聚合器应用于 xs 的整个 list/array/whatever:

    xA           xB               xC
     |           |                |
  xform(xA)   xform(xB)         xform(xC)
     |           |                |
     yA          yB               yC
       \       /                  |
aggregator(yA, yB)                |
           |                     /
         value                  /
           |                   /
          aggregator(value, yC)
                   |
              next_value

你要求 Python 或 Scheme，但我发现如果我们使用类型，这更容易考虑。转换器 xform 采用类型 A 和 returns 类型的单个参数：(x: A) -> B。聚合器 aggregator 接受两个类型 B 的参数以及 returns 一个 B：(x: B, y: B) -> B.

最简单且经常被过度使用的例子是平方和：

import functools

# Combiner
def add(a, b):
    return a + b

# Transformer
def square(a):
    return a * a

one_to_ten = range(1, 11)

functools.reduce(add, map(square, one_to_ten), 0)

不是很令人兴奋。但是，将此与代码中未真正显示的更直接版本（但确实显示在图中）区分开来的是 MapReduce 版本是完全可并行化的。您可以轻松地将它分块并运行部分放在不同的线程、不同的盒子上，等等。我们有变换，我们有组合函数，结合性意味着组合的顺序无关紧要。

现在，并不是所有的问题都可以用这种方式分解，但令人惊讶的是，有很多问题可以用这种方式建模，并且它允许处理太大而无法在一个盒子上处理的数据集。显然，上面天真的写法 Python 不能做到这一点，至少现在不能。但是，一个足够聪明的编译器没有理由不能发出字节码来做到这一点。

虽然我不知道 Scheme，但我知道 Clojure，它确实提供了 parallelized version of this exact thing:

(require '[clojure.core.reducers :as r])

(defn square [x] (* x x))

(r/fold + (pmap square (range 1 11)))

注意这不是很完美：并行映射必须在（也是并行的）组合发生之前完成，但我们越来越接近这些是标准库调用。

Map-reduce 功能概要

Map-reduce functional outline

lisp

python

scheme

functional-programming

mapreduce