random - ideas - ¿Cómo cargo un documento aleatorio desde CouchDB(de manera eficiente y justa)?

story title generator based on plot

Question

Me gustaría cargar un documento aleatorio de un conjunto de documentos almacenados en una base de datos CouchDB. El método para seleccionar y cargar el documento debe cumplir con los siguientes requisitos:

• Eficiencia: la búsqueda del documento debe ser eficiente; lo más importante es que el tiempo para cargar el documento no debe crecer linealmente con la cantidad total de documentos. Esto significa que el argumento de consulta de omisión no se puede usar.

• Distribución uniforme: la elección debe ser verdaderamente aleatoria (en la medida de lo posible, utilizando generadores de números aleatorios estándar), cada documento debe tener las mismas posibilidades de ser elegido.

¿Cuál es la mejor manera de implementar esto en CouchDB?

Answer 1

Después de pensarlo un poco más, se me ocurrió una solución. Para completar, primero mostraré dos enfoques simples y explicaré por qué tienen fallas. La tercera solución es con la que voy.

Enfoque 1: Saltar

Esta es la solución trivial: tiene una vista simple (llamémosla random ) con una función de mapa que emite todos los documentos de los que desea elegir y la función de reducción de cuenta incorporada. Para elegir un documento aleatorio, siga estos pasos:

• Encuentre la cantidad total de documentos N en la vista llamando al:
  http://localhost:5984/db/_design/d/_view/random
• Elija el número aleatorio 0 <= i < N
• Cargue el i -ésimo documento:
  http://localhost:5984/db/_design/d/_view/random?reduce=false&skip=i&limit=1

Este enfoque es malo porque no escala bien para una gran cantidad de documentos. De acuerdo con esta sección de "CouchDB - The Definitive Guide", el argumento de omisión solo debe usarse con valores de un solo dígito.

La solución anterior debería recorrer los documentos antes de devolver la elegida. En términos de SQL, es el equivalente de una exploración de tabla completa en lugar de una búsqueda de índice.

Enfoque 2: Número aleatorio en el documento

Con este enfoque, se genera un número aleatorio para cada documento en el momento de la creación y se almacena en el documento. Un documento de ejemplo:

{
  _id: "4f12782c39474fd0a498126c0400708c",
  rand: 0.4591819887660398,
  // actual data...
}

La vista random tiene entonces la siguiente función de mapa:

function(doc) {
  if (doc.rand) {
    emit(doc.rand, doc);
  }
}      

Estos son los pasos para elegir un documento aleatorio:

• Elija un número aleatorio 0 <= r < 1
• Cargue el documento:
  http://localhost:5984/db/_design/d/_view/random?startkey=r&limit=1
• Si no se devuelve ningún documento (porque r es más grande que el número aleatorio más grande almacenado en la base de datos), envuelva y cargue el primer documento.

Esto es muy rápido y se ve muy bien a primera vista. Sin embargo, hay una falla grave: no todos los documentos tienen las mismas posibilidades de ser seleccionados.

En el ejemplo más simple, hay dos documentos en la base de datos. Cuando elijo un documento aleatorio una gran cantidad de veces, quiero que cada documento aparezca la mitad del tiempo. Digamos que a los documentos se les asignaron los números aleatorios 0.2 y 0.9 en el momento de la creación. Entonces, el documento A se selecciona cuando (r <= 0.2) or (r > 0.9) y el documento B se elige cuando 0.2 < r <= 0.9 . La posibilidad de ser elegido no es del 50% para cada documento, sino del 30% para A y del 70% para B.

Puede pensar que la situación mejora cuando hay más documentos en la base de datos, pero realmente no. Los intervalos entre documentos se hacen más pequeños, pero la variación en el tamaño del intervalo empeora: imagine tres documentos A, B y C con los números aleatorios 0.30001057, 0.30002057 y 0.30002058 (no hay otros documentos en el medio). Las posibilidades de que se elija B son 1000 veces mayores que la elección de C. En el peor de los casos, a dos documentos se les asigna el mismo número aleatorio. Entonces solo se puede encontrar uno de ellos (el que tiene la identificación del documento inferior), el otro es esencialmente invisible.

Enfoque 3: una combinación de 1 y 2

La solución que ideé combina la velocidad del enfoque 2 con la equidad del enfoque 1. Aquí está:

Como en el enfoque 2, a cada documento se le asigna un número aleatorio en el momento de la creación, la misma función de mapa se usa para la vista. Como en el enfoque 1, también tengo una función de reducción de cuenta.

Estos son los pasos para cargar un documento aleatorio:

• Encuentre la cantidad total de documentos N en la vista llamando al:
  http://localhost:5984/db/_design/d/_view/random
• Elija el número aleatorio 0 <= r < 1
• Calcular el índice aleatorio: i = floor(r*N)
  Mi objetivo es cargar el i -ésimo documento (como en el enfoque 1). Asumiendo que la distribución de números aleatorios es más o menos uniforme, supongo que el documento tiene un valor aleatorio de aproximadamente r .
• Encuentre la cantidad de documentos L con un valor aleatorio inferior a r : http://localhost:5984/db/_design/d/_view/random?endkey=r
• Vea qué tan lejos de nuestra conjetura es: s = i - L
• if (s>=0)
http://localhost:5984/db/_design/d/_view/random?startkey=r&skip=s&limit=1&reduce=false
• if (s<0)
http://localhost:5984/db/_design/d/_view/random?startkey=r&skip=-(s+1)&limit=1&descending=true&reduce=false

Entonces, el truco consiste en adivinar el número aleatorio asignado al i -ésimo documento, buscarlo, ver cuán lejos estamos y luego omitir la cantidad de documentos que perdimos.

La cantidad de documentos omitidos debe ser pequeña, incluso para las bases de datos grandes, ya que la precisión de las estimaciones aumentará con la cantidad de documentos. Mi suposición es que s permanece constante cuando la base de datos crece, pero no lo he intentado y no me siento capacitado para probarlo teóricamente.

Si tienes una mejor solución, ¡estaría muy interesado!

Answer 2

Si el rendimiento de la inserción no es un problema, puede tratar de hacer que el número no sea aleatorio, por ejemplo, que sea doc_count + 1 en el momento de la creación. Entonces podrías buscarlo con un número aleatorio 0 <= r <doc_count. Pero eso requeriría sincronizar la creación de documentos o tener una secuencia externa a couchdb, por ejemplo, una base de datos SQL.

Atentamente

Felix

Answer 3

¿Qué tal "abusar" de la función de reducción de una vista?

function (keys, values, reduce) {
    if (reduce)
      return values[Math.floor(Math.random()*values.length)];
    else
      return values;
}