Skip to content

Instantly share code, notes, and snippets.

Created September 4, 2010 15:09
Show Gist options
  • Save anonymous/565255 to your computer and use it in GitHub Desktop.
Save anonymous/565255 to your computer and use it in GitHub Desktop.
<?
// 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;
};
?>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment