Estos son algunos de los resultados que encontr茅 implementando lo que dice el paper de referencia:
Primero, pueden hechar una mirada al c贸digo. No es lindo, posiblemente no sea 贸ptimo, pero quer铆a tener un feel real de qu茅 iba a costar 茅sto:
El c贸digo tiene las siguientes partes:
Un matcher usando la red descripta en el paper
Un matcher naive ( fors anidados )
Un generador de eventos random
Un generador de subscripciones random
Un tester (genera subscripciones, genera eventos y compara el resultado de los dos matchers, por ahora dan siempre lo mismo)
Un medidor de perfomance: Crea un mont贸n (X) de subscripciones al azar y prueba cuantas evaluaciones tiene que hacer para matchear una serie de eventos random (xx) y cuanto tiempo tarda en esto.
Resultados
Este es el plot que compara la cantidad de evaluaciones entre los dos m茅todos. El eje X es la cantidad de subscripciones x10. Prob茅 de 1 a 1000 subscripciones. El eje Y es la cantidad de comparaciones que se realizaron para ver que subscripciones matcheaban contra 5000 eventos. (la cantidad de eventos no var铆a para las pruebas, solo la cantidad de subscripciones)
Como pueden ver, la cantidad de matcheos en la red es sub lineal y bastante menos que en el caso naive.
Sin embargo, el problema se da con los tiempos, que no son nada buenos en ninguno de los dos casos.
Conclusiones
Aunque la cantidad de evaluaciones crece de manera sub lineal, el tiempo que toma el algoritmo mas complicado es mayor para una cantidad de subscripciones < 1000.
Aunque vemos que el tiempo del algortimo de red crece menos que el naive, los tiempos son bastante malos. De base estamos viendo un nivel de matcheo de 700/s con 100 subscripciones, 200/s con 1000 subscripciones y 53/s con 10.000 subscripciones.
Para poder soportar miles de usuarios, donde cada evento matchea con solo UNA subscripci贸n (y hay miles de subscripciones, una por usuario) me parece LENTO. No necesariamente el O(), pero si en tiempo total de ejecuci贸n.