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

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.