Twitter ha publicado su Algebird una biblioteca de álgebra abstracta para scala.
A grandes rasgos, ¿cuáles son las matemáticas del álgebra abstracta que repercuten en la agregación de grandes conjuntos de datos?
Respuesta
¿Demasiados anuncios?
Chad Brewbaker
Puntos
217
Respuesta corta, si tus operaciones son comunicativas el orden de tu salida/entrada no importa haciendo mucho más fácil programar operaciones ya que no tienes que preocuparte por el orden. Esta es una buena característica en el procesamiento paralelo, ya que tienes que hacer mucho menos sincronización.
Problema de piedra, papel o tijera: (Añade a Spock y al lagarto para ganar puntos extra ;)
Digamos que tienes una larga cadena de RPS y quieres saber quién queda en pie. Supongamos que el resultado es el mismo que el juego realizado cuando se emparejan iterativamente los dos primeros elementos de la lista hasta que sólo queda uno.
RPSSPSRSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSPRPSSPRRRRSPSPSPPPRSPSPSRP
Tabla de multiplicar:
RR->R
PP->P
SS->S
RS->R
SR->R
SP->S
PS->S
RP->P
PR->P
Siéntate y averigua cómo puedes evaluar una cadena RPS enorme en paralelo.... (solución al final)
Consulta su biblioteca de pruebas para ver casos de uso: https://github.com/twitter/algebird/tree/develop/src/test/scala/com/twitter/algebird
O el propio código: https://github.com/twitter/algebird/tree/develop/src/main/scala/com/twitter/algebird
Es un marco de programación genérico para tipos de datos que soportan los conceptos de 0,1,más, veces, inverso ... El usuario tiene que escribir un wrapper en Scala que se encargue de la gestión de memoria, y realice las operaciones. Dependiendo de qué conceptos implemente la estructura de datos caerá dentro de algún concepto de álgebra abstracta: grupo, semigrupo, monoide,... donde podrá utilizar algoritmos especializados específicos de ese concepto genérico de álgebra abstracta para alcanzar sus objetivos computacionales.
Por ejemplo, si tienes una operación comunicativa, puede ser más rápida que una asociativa, ya que se te permite reordenar los elementos; sin embargo, el framework necesita saber esto para hacer optimizaciones.
En mi opinión, un marco C++/Python/Java/Ruby basado en el prefijo paralelo habría sido más útil. Además, la documentación es un poco escasa. No pude encontrar fácilmente un ejemplo conciso de cómo tomar tu estructura de datos y envolverla con todas las funciones que necesita para el framework.
Solución RPS paralela.
Piense en ello como una máquina de estados finitos de tres estados R, P, S; con transiciones R, P, S. Primero codifica R->0, P-> 1, S ->2.
Transformación de roca {RR->R, PR -> P, SR -> R} | {00->0, 10->1, 20->0} | {0,1,0}
Transformación de papel {RP->P, PP->P, SP -> S} | {1,1,2}
Transformación de tijera {RS->R, PS->S, SS->S } | {0,2,2}
Ahora aplica un prefijo paralelo sobre las transformaciones {0,1,0}, {1,1,2}, y {0,2,2} bajo composición de transformaciones; igual que composición/multiplicación de permutaciones donde haces f(g(x)).
¿Cómo te ayudaría algebird con eso? Eh.... no estoy seguro.
