query maxmemory hkeys commands cli basics algorithm redis

algorithm - maxmemory - Algoritmo de coincidencia de usuario



redis instructions (1)

Sería bueno saber de qué tipo de datos estamos hablando. ¿Cuántos usuarios existen? ¿Cuántos estarán en línea en promedio? ¿Cómo se compara la proporción de "usuarios vistos" con todos los usuarios (escasa vs. densa)?

Modificación de su algoritmo No muestre el primero, sino elija un elemento aleatorio del conjunto de usuarios en línea. ¡Esto debería mejorar el equilibrio y puede ayudar con la complejidad amortizada dependiendo de la proporción de estos dos conjuntos!

Algoritmo alternativo (más estructurado, aún peor peor de los casos; debería ser bueno si se observa escaso)

  • Mantener visto como un árbol equilibrado (inserción O (log n))
  • Mantente en línea como un árbol equilibrado.
  • Si bien no se eligieron suficientes usuarios:
    • Buscar la primera brecha en la vista (por ejemplo, [0,1,3,7] -> 2; O (log n) según SO-link )
    • Buscar el primer usuario> = gap-value (O (log n))
    • Si el usuario <next_gap_neighbor (en el ejemplo anterior: 3; el siguiente valor después del espacio elegido 2)
    • -> recoger
    • Más
    • -> agregar el valor de brecha elegido temporalmente (para este momento; modelo-decisión con qué frecuencia actualizar en línea ) para ver O limitar la búsqueda de alguna manera a> valor de brecha elegida (O (log n))

Dependiendo de los datos, esto debería funcionar muy bien si los datos son enormes y se ven escasos.

Entonces, este problema tenemos usuarios que coinciden con otros usuarios en línea. Sin embargo, no es solo un partido de uno a uno. A un usuario se le da una selección de otros 5 usuarios para elegir, que luego se marcan como se ven y no se deben volver a mostrar cuando el usuario solicite que se muestren otros 5 usuarios. Más personas pueden conectarse en línea durante el proceso.

El problema es que quiero una forma para que cada usuario se muestre en la selección para otros usuarios, con redis, pero un algoritmo es principalmente lo que estoy buscando. Estoy tratando de implementar esto de la manera más rápida posible, usando redis si es posible, pero también puedo hacer llamadas a la base de datos si es necesario.

Mi solución actual es la siguiente, con suerte alguien tendrá algunos consejos para mejorar esto de O (N) llamadas.

Entonces cada usuario necesita tener un conjunto visto de user_id s. Podemos tener una lista redis (cola) de onlineusers . Donde seguimos colocando usuarios desde la izquierda hasta que encontremos uno que no esté en el conjunto visto por el usuario, guárdelo, agregue a los usuarios vistos y luego empújelo a la derecha. Luego, una vez que tenemos 5 de los que dejamos, retrocedemos los que dejamos que ya se vieron.

Esto es lo mejor que pude pensar, sin embargo, es O (N) cada vez que queremos encontrar 5 usuarios para que este usuario seleccione. Es posible (aunque no probable) que el usuario haya visto una gran cantidad y esté saliendo de la lista completa.

Para ayudar a entender esto mejor Un enfoque ingenuo es hacer que cada usuario individual contenga una copia de todos los usuarios en línea en forma de un conjunto. Entonces, simplemente seleccionamos 5 miembros aleatorios. Pero esto no puede funcionar porque no hay suficiente espacio, y cada vez que un usuario se conecta debe ser agregado a los usuarios en línea de cada usuario. O eliminados cuando se desconectan y esas operaciones son O (N) considerando que están hechas para N usuarios en O (1)

¿Alguien tiene alguna sugerencia para unir usuarios con otros usuarios?