SimpleMapReduce.php

<?

// For article http://habrahabr.ru/blogs/algorithm/103467/
 
$words = "foo bar baz bar";
$words_split = explode(" ", $words);
 
function map1($word) {
  return array($word, 1);
};
 
function reduce1($tuple) {
  return array($tuple[0], array_sum($tuple[1]));
};
 
print "<pre>";
print_r(map_reduce($words_split, 'map1', 'reduce1'));
 
// Простейшее воплощение MapReduce 
// БЕЗ MergeSort и файлов - только чтобы понять идею. 
// Ограничено памятью одной машины.
 
function group_tuples_by_first_element($result1) {
 
    // эта функция берет сорированный массив
    // [
    //   [bar, 1]
    //   [bar, 1]
    //   [foo, 1]
    // ]
    //
    // а возвращает
    // [
    //   [bar, [1,1]]
    //   [foo, [1]]
    // ]
 
    $result2 = array();
    foreach($result1 as $tuple) {
        list($word, $value) = $tuple;
        $last_index = count($result2)-1;
        if((count($result2) == 0) || ($word != $result2[$last_index][0])) {
            $new_item = array($word, array());
            array_push($result2, $new_item);
        };
        $last_index = count($result2)-1;
        array_push($result2[$last_index][1], $value);
    };
    return $result2;
};
 
 
function map_reduce($words_split, $map_func, $reduce_func) {
 
    $result1 = array();
    foreach($words_split as $word) {
      // вызываем наш map1()
      array_push($result1, call_user_func($map_func, $word));
      // здесь должна быть проверка памяти, если заняли всю
      // сохранить промежуточные результаты в первый файл и продолжить,
      // очистив $result1 (= array())
    };
 
    //print "Map готов:<br><pre>";
    //print_r($result1);
    //print "</pre><hr>";
 
    // здесь вместо двух следующих строк должно быть 
    // чтение из всех сохраненных файлов
    // методом MergeSort, описанным в статье (брать минимальные элементы, 
    // двигаться дальше)
 
    sort($result1);
    $result2 = group_tuples_by_first_element($result1);
 
 
    $result3 = array();
    foreach($result2 as $tuple) {
      // вызываем наш reduce1()
      array_push($result3, call_user_func($reduce_func, $tuple));
    };
 
    //print "Reduce готов:<br><pre>";
    //print_r($result3);
    //print "</pre><hr>";
 
    return $result3;
 
};
 
?>