Cómo seleccionar aleatoriamente elementos únicos de una lista desplegable

La solución más fácil es mostrar a cada usuario el mismo contenido nuevo. Como el contenido es nuevo, ninguno de ellos lo habrá visto todavía. Para muchos tipos de sitios, el contenido nuevo es el tipo de interés que más les interesa a los usuarios.

Si no tiene suficiente contenido nuevo para hacer esto o desea mostrar contenido antiguo, puede hacerlo de manera bastante eficiente a través de un filtro de floración. En lugar de almacenar el contenido visto para cada usuario, usted almacena una estructura de datos de tamaño fijo que le indica si el contenido ha sido visto por el usuario con alguna probabilidad de un falso positivo. Ahora puede generar aleatoriamente una lista de contenido y filtrar el contenido visto, así como una pequeña cantidad de contenido invisible.

La tasa de falsos positivos con este enfoque aumentará para los usuarios más pesados, hasta que eventualmente sea imposible mostrarles contenido nuevo a pesar del contenido que no han visto existente. Para estos usuarios, deberá tomar una decisión.

Una opción es mantener una base de datos fuera de línea de todo el contenido visto por todos los usuarios. Dices que es obvio que no puedes hacer esto, pero no veo por qué esto es obvio. Con la ingeniería adecuada, probablemente incluso podría consultar esto en vivo en producción, pero al menos debería poder encontrar suficiente almacenamiento en la nube para mantener esta información para el procesamiento fuera de línea. Estos datos pueden ser muy valiosos y el almacenamiento en la nube es barato, por lo que debe reconsiderar si realmente no es posible registrar todo. Básicamente estás tirando dinero. Una vez que tenga registros completos, puede precalcular listas aleatorias para usuarios más pesados ​​sin conexión o producir un filtro de floración más grande para ellos. Los filtros Bloom no pueden redimensionarse dinámicamente, por lo que generar filtros más grandes requiere tener registros completos de lo que los usuarios han visto.

Alternativamente, puede aflojar su requisito de que nunca le muestre a alguien algo que haya visto antes. En cambio, solo garantice que solo le mostrará a las personas algo que no han visto en mucho tiempo. Es posible que no pueda mantener una lista completa de todo lo que ha visto un usuario, pero debería poder mantener una lista parcial. Tal vez los últimos 100 o los últimos 1000 artículos que han visto. Ahora solo filtre estos de sus elecciones aleatorias. Los usuarios más ligeros verán contenido completamente nuevo o casi completamente nuevo, mientras que los usuarios más pesados ​​al menos no seguirán viendo el mismo contenido repetidamente.

Su pregunta fue un poco vaga, así que espero que uno de estos enfoques ayude.

No dice por qué no puede almacenar el contenido mostrado para cada usuario. ¿Es por limitaciones de almacenamiento o rendimiento? Por lo general, hay formas de evitar esas limitaciones. Los filtros Bloom, como sugiere otra respuesta, pueden ser una solución para ahorrar espacio. Pero en términos generales, la solución dependerá de las dimensiones del problema: ¿cuántos usuarios? cuantos articulos ¿Con qué frecuencia acceden los usuarios al servicio? ¿Cuál es el patrón de llegada de nuevos artículos?

También depende de cuáles son los requisitos del conjunto de elementos para mostrar. ¿Totalmente al azar? Aleatorio por categorías? ¿Por lo reciente? Si, por ejemplo, desea priorizar el contenido “nuevo”, puede almacenar la marca de tiempo de la última visita para cada usuario (esto tiene demandas de tamaño moderadas) y, a la llegada del usuario, seleccione N elementos aleatorios de entre los que aparecieron desde esa última visita. Se garantiza que nunca se le han mostrado al usuario (y son recientes, lo cual es una ventaja).

Otra pregunta: ¿cuántos elementos se muestran al usuario en cada visita? Si hay muchos, podría precompilar paquetes disjuntos de elementos aleatorios y, a la llegada del usuario, seleccione uno de ellos para esta visita; entonces, lo que debe registrarse para no repetirse es qué paquete se seleccionó, no la lista completa de elementos del paquete. Esto podría reducir mucho los requisitos de almacenamiento. Además, al generar listas previamente, evita la necesidad de realizar un muestreo aleatorio “en vivo” sobre su conjunto de elementos, lo que también mejora el rendimiento.

Como está almacenando la lista en un disco o una base de datos, y dado que no se trata de un elemento transitorio, sino de contenido, mantenga una lista de URL como un archivo de disco o una tabla de base de datos, luego seleccione un número aleatorio entre 0 yn, con n siendo el tamaño de la lista.

Llámalo “índice”. Cargue el registro de índice de la lista si desea hacerlo en RAM, lo cual no se recomienda, pero proporciona una buena ilustración. Haga algo como lo siguiente:

n = número de registros
arr = nueva matriz [n] ()

leer en todos los registros en arr

return arr [número aleatorio entre 0 y n]

Puede que esto no te convenga, pero es una idea:

No mostrar elementos al azar. El usuario no sabe la diferencia de todos modos, si el usuario solo está recibiendo nuevo contenido cada vez, ¿cómo sabe si está en orden o al azar? Es solo contenido nuevo.

Entonces solo necesita almacenar el índice más alto que cada usuario haya tenido hasta ahora.