PythonでMapReduceの真似事

MapReduceとはGoogleによって考案され，クラウドコンピューティングの要として注目されたアルゴリズムフレームワークです．Googleによる分散処理の実装自体をMapReduceと呼ぶことも少なくありませんが，アルゴリズムにおける分割統治法のように，並列コンピューティングにおける考え方の枠組みこそがMapReduceであると捉えることができます．Hadoop等のソフトウェアフレームワークを使用せずに，PythonのみでMapReduceを実践してみましょう．問題はオライリーから出版の「並行コンピューティング技法」より，friendly数の計算です．

問題

• 互いにfriendlyな自然数の組を，プログラム起動時に与えられた正の整数までの範囲で，すべて探索せよ．
• 2つの数のうち，一方の数のすべての約数の和をその数で除した比率が，もう一方の数を同じように処理した比率と等しい場合を，2つの数が互いにfriendlyであると言い，またこの比率をその数のabundancyと言います．
• (例)30と140はfriendly
  
  
  

実装

#!/usr/bin/env python2.6

import multiprocessing
import fractions
import collections

def abundancy(n):
    numerator = n + 1
    for i in range(2, n/2):
        if n%i == 0:
            numerator += i
    return [[fractions.Fraction(numerator, n), n]]

def find_friend(mapped_value):
    abundancy, values = mapped_value
    num_values = len(values)
    result = []
    for i in range(num_values):
        for j in range(i+1, num_values):
            result.append((values[i], values[j]))
    return result

def partition(mapped_values):
    partitioned_data = collections.defaultdict(list)
    for sublist in mapped_values:
        for key, value in sublist:
            partitioned_data[key].append(value)
    return partitioned_data

def mapreduce(inputs):
    pool = multiprocessing.Pool()
    mapped_values = pool.map(abundancy, inputs)
    partitioned_data = partition(mapped_values)
    reduced_values = pool.map(find_friend, partitioned_data.items())
    return reduced_values

if __name__ == '__main__':
    results = mapreduce(range(1,10000))
    for result in results:
        for a,b in result:
            print '{0} and {1} are friendly'.format(a, b)

参考

• 翻訳 - Pythonのmultiprocessingモジュールを使ってGoogleの並列処理システムMapReduceをインプリする
• 並行コンピューティング技法 ―実践マルチコア/マルチスレッドプログラミング