php - hacer - rank mysql

¿Cómo se utilizan los algoritmos de clasificación de Reddit y Hacker News?

Question

He estado buscando algoritmos de clasificación recientemente, específicamente aquellos utilizados por Reddit y Hacker News. Los algoritmos en sí son bastante simples, pero no entiendo bien cómo se usan.

Una cosa que podría hacer es implementar el algoritmo directamente en SQL, de modo que cada vez que un usuario vaya a una página que muestre publicaciones clasificadas, se ejecute algo como esto:

SELECT thing1, thing2 FROM table
ORDER BY ranking_algorithm DESC
LIMIT page*20, 20

Hay varias preguntas similares sobre SO, pero la única respuesta es colocar el algoritmo de clasificación dentro de la consulta SQL. Entonces el hilo muere ...

Poner el algoritmo en la consulta SQL bien en una escala más pequeña, pero ¿qué sucede si el sitio web tiene una gran cantidad de usuarios y una gran cantidad de publicaciones? Eso significa que cada vez que un usuario abre una página que muestra las publicaciones clasificadas, esa consulta se ejecutará. Eso no puede ser muy eficiente.

Ahora, Reddit y Hacker News no ejecutan sus algoritmos de clasificación como consultas SQL, sino en python y ark respectivamente. Entonces, ¿cómo y cuándo se utilizan exactamente?

Una posible solución es tomar toda la información relevante de cada publicación y almacenarla en alguna estructura de datos en el servidor web. Luego clasifica y ordena esta estructura de datos.

Cada vez que alguien abre una página que muestra las publicaciones clasificadas, solo tiene que ir a la estructura de datos, recuperar el rango correcto de publicaciones y mostrarlas.

Luego, aproximadamente cada media hora, recupera la información más actualizada del servidor, la clasifica, la clasifica y actualiza la estructura de datos.

Otras consultas menos costosas, como la recuperación y visualización de toda la información de una publicación específica, o la visualización de las publicaciones más recientes (a diferencia de la mejor puntuada) se pueden realizar en SQL cada vez que se abre la página correspondiente.

La ventaja es que su base de datos está siendo alcanzada (para la consulta de clasificación cara) solo una vez cada media hora. La desventaja es que necesita tener un duplicado de una gran parte de su base de datos.

Answer 1

Implementé una versión SQL del algoritmo de clasificación de Reddit para un agregador de video como:

SELECT id, title
FROM videos
ORDER BY
LOG10(ABS(cached_votes_total) + 1) * SIGN(cached_votes_total)
+ (UNIX_TIMESTAMP(created_at) / 300000) DESC
LIMIT 50

cached_votes_total se actualiza mediante un disparador cada vez que se emite un nuevo voto. Se ejecuta lo suficientemente rápido en nuestro sitio actual, pero estoy planeando agregar una columna de valor de clasificación y actualizarla con el mismo activador que la columna cached_votes_total . Después de esa optimización, debería ser lo suficientemente rápido para la mayoría de los sitios de cualquier tamaño.

edición: Más información en Reddit Hotness Algorithm en SQL

Answer 2

Reddit usa Pyrex, el algoritmo de clasificación es una extensión de Python C para mejorar el rendimiento.

Por lo tanto, puede hacer lo mismo en SQL cuando se actualiza el registro, pex: cuando está arriba o abajo votado.

El pseudocódigo que debe traducir a la sintaxis de su motor SQL:

function hot(ups, downs, date){
score = ups - downs;
order = log(max(abs(score), 1), 10);
if (score>0){
sign = 1;
} else {
if (score<0){
sign = -1;
} else {
sign = 0;
}
}
td = date - datetime(1970,1,1);
seconds = td.days * 86400 + td.seconds + (float(td.microseconds) / 1000000) - 1134028003;
return round(order + sign * seconds / 45000, 7);
}

Por lo tanto, debe almacenar en la tabla de publicaciones las subidas, bajadas, la fecha y el resultado de la función activa. Y luego puedes hacer una clasificación en la columna caliente.

Puede ver el código fuente de Reddit aquí: http://code.reddit.com/