Teóricamente, ¿se puede implementar algún algoritmo en el marco de MapReduce?

Creo que sí, aunque una formulación precisa de la pregunta sustituiría “algoritmo” por “función computable”. [1] Entonces podríamos preguntar si fue posible implementar una máquina Turing [2] como una serie de trabajos MapReduce.

Me parece que un ejemplo trivial de esto sería un mapeador único que estaba leyendo cinta, escribiendo valores y luego actualizando su estado interno basado en una tabla de acciones. La parte desafiante es que, estrictamente hablando, solo podemos mover la cinta en una dirección en MapReduce: no podemos volver a la izquierda y volver a escribir una celda que ya hemos escrito en un solo paso del mapa. En el caso de que esto sucediera, tendríamos que emplear algún tipo de trucos, y en el peor de los casos, tendríamos que detener el trabajo actual de MapReduce y comenzar uno nuevo que necesitara avanzar rápidamente al símbolo que necesitábamos. actualizar. Por lo tanto, creo que una serie de trabajos de MapReduce (pero no un solo trabajo) podría usarse para implementar una máquina de Turing, lo que implicaría que una serie de trabajos de MapReduce puede simular la lógica de cualquier algoritmo.

Aunque podría hacerse, no significa que sea una buena idea hacerlo realmente. Este documento brinda condiciones que pueden usarse para determinar qué tan “capaz es MapReduce” de un problema, y ​​lo recomiendo encarecidamente:

http://arxiv.org/abs/1204.1754

[1] http://en.wikipedia.org/wiki/Com …
[2] http://en.wikipedia.org/wiki/Tur …

Según mi experiencia, la respuesta es que depende. Dado que la condición básica de que MapReduce puede mejorar el tiempo de ejecución es que el problema se puede convertir en problemas independientes y secundarios, y el resultado final se puede combinar en función de los resultados secundarios. Si hay una fuerte dependencia de datos entre los pasos, digamos c = a + b, x = c + e, entonces no puede aplicar MapReduce (ni ningún algoritmo paralelo).

Como algunas personas ya lo han dicho, cualquier algoritmo puede implementarse en MapReduce, incluso un algoritmo secuencial, ya que puede establecer la función de mapa en la función de identidad y luego ejecutar el algoritmo secuencial en la fase de reducción con una tarea leyendo toda la entrada.

La pregunta más interesante, supongo, es si algún algoritmo paralelo puede implementarse eficientemente en el marco. Recientemente escribí un artículo sobre esto [1] que puede ver, junto con trabajos previos realizados por Karloff et al. y Goodrich et al. referenciado en el documento.

[1] BSP vs MapReduce http://arxiv.org/abs/1203.2081

Prueba el APL de Kenneth Iverson. El hecho de que sea Turing Complete, y utiliza principalmente Map-Reduce-Filter con algunos complementos adicionales, deja en claro que la respuesta a su pregunta es positiva.

Hay algunos algoritmos que son convertibles en reducción de mapa, pero aún así no obtienes una aceleración en el rendimiento. En tales casos, puedes sentir que la implementación ingenua en sí misma fue más rápida y la reducción de mapa fue una sobrecarga en el cálculo.

No.

Hay algoritmos que son inherentemente seriales.

Es importante destacar que un número sustancial de algoritmos estadísticos se implementan mejor con el uso de análisis de muestreo vs fuerza bruta de todo el conjunto de datos.

La idea de que cada conjunto de datos debe procesarse en su totalidad para obtener una respuesta válida es una que carece de consideración de las técnicas de muestreo para dar una respuesta válida. También supone erróneamente que el tiempo (tanto CPU como humano) es libre y que el análisis de más datos producirá mejores (o diferentes) resultados.

Sí. Si incluye funciones triviales y recursivas.

Bueno, si estamos hablando de Turing-Completeness Reduce es una función muy poderosa (y podría hacer “Mapa”). Solo necesita igualdad (o algo para crear sentencias condicionales if / then), comandos de matriz triviales (concatenación, elemento de lectura / eliminación) y recursividad. De hecho, si usa tanto read-first-in-list como read-last-in-list, ya no creo que necesite recurrencia (PUEDE necesitar una estructura en bucle, porque no puedo pensar en una forma de reducir ejecutar un bucle infinito?). Y la mayoría de estas propiedades son triviales, ya que es difícil imaginar reducir la ejecución sin funciones para leer / agregar a las listas. La recursión es menos trivial, pero es la forma en que lo haces, es decir. Ordenar en Mapa / Reducir.

Solo proporciono esta explicación porque Map / Reduce (o Reduce específicamente) no es un lenguaje, y por lo tanto necesita algo más para estar Turing Complete. Pero creo que, a los fines de su pregunta, la respuesta es sí , solo recuerde que la recursión es una gran parte de lo que hace que este Turing sea completo.

De manera más general, MapReduce puede funcionar con cualquier función que sea transitiva (a = byb = c implica a = c), y asociativa (ab) c = a (bc). Es útil si es conmutativo (el orden no importa, así que ab = ba como una Suma). Incluso hay funciones que funcionan con el paradigma (como, creo, encontrar la mediana) que no se “distribuyen” fácilmente, pero que aún funcionan con Reducir, siempre que el conjunto completo de números pase a través de Reducir.

Obviamente, esta respuesta no tiene nada que ver con la optimización y la velocidad. Ciertamente, hay casos en que MapReduce no es una solución óptima (aunque sorprendentemente hay menos de lo que podría pensar). Y además, no todos los marcos prácticos Map / Reduce son capaces de ser Turing Complete.

ps (técnico) La razón por la que leer primero y leer por último crea la integridad completa es que puede implementar un autómata pushdown con dos pilas.

Encuentro un gran dolor al menos para implementar el algoritmo de isomorfismo de subgrafo de Ullman en el marco de MapReduce. Map es para permitir que todos participen, Reduce es para obtener un resultado global. Parece que estos dos pasos son indispensables. Pero algunos programas sutiles no se pueden implementar en MapReduce intuitivamente. Entonces, mi sensación personal es que debería haber una mejor manera para el marco paralelo de datos.