¿Cómo funciona el algoritmo de ‘conteo’ de Gmail?

Digamos que estamos buscando el término “vuelo” en nuestra bandeja de entrada.

Podríamos obtener todos los resultados de la búsqueda, contarlos y luego descartar todo excepto las primeras 20 coincidencias. ¿Suena derrochador? ¿Especialmente si estamos hablando de decenas, si no cientos de miles de correos electrónicos? ¿Especialmente si estamos hablando de millones de usuarios que usan la aplicación simultáneamente? Muy derrochador.

Entonces, en lugar de eso, podemos hacer trampa (también conocido como optimizar):
Busque los primeros 20 correos correspondientes para “vuelo” a partir de ahora y retroceda en el tiempo.
Cuando alcanzamos 20 resultados, dejamos de buscar. De esta manera, solo barajamos ~ 100-1000 correos electrónicos en lugar de todos. Esta es una optimización maravillosa para obtener los mismos resultados de búsqueda , “¿Pero cómo podemos tener algún tipo de sentido en el recuento total ?”, Escuché que preguntas.

Podemos extrapolar. Si descubrimos que el vigésimo correo electrónico más reciente sobre “vuelo” fue hace 2 meses, y sabemos que esta dirección de Gmail fue creada hace 1 año, entonces podríamos hacer una simple aritmética para estimar el número total:

[matemáticas] \ frac {1 \; año 2 \; meses} \ veces 20 \ aprox 120 \; total \, coincide con [/ math]

En el caso no tan frecuente cuando el usuario decide ir a la página 2, simplemente podemos continuar buscando hasta que encontremos los siguientes 20 correos coincidentes, y nuestro número total se autocorregirá en el camino, con suerte convergiendo hacia el recuento real Digamos, en la segunda página, el partido # 40 se recibió hace 3 meses, entonces nuestra estimación se vería así:

[matemáticas] \ frac {1 \; año} {3 \; meses} \ veces 40 \ aprox 160 \; total \, coincide con [/ math]

Y así…

¿Qué pasa con muchos , entonces?
Buena pregunta. Este tipo de optimización solo funciona bien si la distribución de coincidencias es pareja. Podría ser que Gmail analiza cómo fueron las coincidencias que encontró hasta ahora, y si son esporádicas, en lugar de decir algo extravagante como “1-20 de aproximadamente 47827” (que podría ser como el 80% de su correo entrante total) solo dicen muchos , para salvar la cara y no parecer tontos.


No conozco los aspectos internos de Gmail, por lo que esta es una suposición educada de mi parte.
AKA esta es una forma en que podría hacerlo / trataría de hacerlo si tuviera que construir algo similar.

Imagina que buscas una palabra clave. Desea que se muestren todos los correos de su bandeja de entrada que contengan esa palabra clave. Entonces simplemente pones la palabra en la barra de búsqueda y haces clic. Simple.

¿Ahora qué tiene que hacer el servidor? Tiene que realizar búsquedas a través de cada uno de sus correos. En un algoritmo de búsqueda de cadena simple, para texto de longitud n y p patrones de longitud combinada m , su tiempo de ejecución promedio y en el mejor de los casos es O ( n + m ) en el espacio O ( p ), pero su peor momento es O ( nm ).

Imagine un servidor que ejecuta este cálculo para usted y al menos otras 10 personas que buscan en su bandeja de entrada al mismo tiempo. Entonces, como diseñador de productos, ¿tiene que optimizarlo? Qué harás. Primero descubrirá lo que necesita el usuario. Sabes que es raro que la gente busque viejos correos electrónicos. Por lo general, buscan los recientes (probablemente su informe de análisis de comportamiento del usuario le dijo). Así que modifique la búsqueda en consecuencia.

De esta manera, los números muestran solo el número de correos electrónicos que se han encontrado en la primera búsqueda de un rango de fechas. Luego, vuelve a buscar cada vez que hace clic en el botón siguiente. Esta es una optimización lógica que ahorra los recursos.

ps: He hecho una suposición aquí sobre el algoritmo que mencioné. Estoy seguro de que Google tiene mejores algoritmos, pero el punto es ahorrar recursos.

Sí. puedes ver resultados interesantes cuando buscas una palabra clave en Gmail. En su primera búsqueda, mostrará un recuento de correos electrónicos, pero a medida que profundice, la cantidad de correos electrónicos devueltos para esa palabra clave puede aumentar.

En caso de que hagas un par de búsquedas, probablemente puedas notar un patrón. La mayoría de las veces, obtendrá un poco más del doble del número total de correos electrónicos que se muestran por página como el recuento total de correos electrónicos. Entonces, si se muestran 20 correos electrónicos a la vez, puede esperar ver un poco más de 40 correos electrónicos como el recuento total de correos electrónicos.

Si profundiza, se agregará aproximadamente el doble de la cantidad de correos electrónicos que se muestran por página al recuento de correos electrónicos actual para obtener el nuevo recuento de correos electrónicos. Entonces, si fue alrededor de 40 en la primera vez, espere ver alrededor de 80 la próxima vez. Entonces, cada vez, se agregarán alrededor de 40 al recuento total de correos electrónicos. Esto continúa hasta que se hayan contabilizado todos los correos electrónicos que contienen esa palabra clave.

Al principio, solo busca un rango de fechas particular de correos. Si el usuario no está satisfecho con los resultados, ya que solicita más, solicita el siguiente rango de fechas y se agrega a los resultados existentes.