Tengo muchos archivos de registro de visitas a la página web, donde cada visita está asociada con una identificación de usuario y una marca de tiempo. Necesito identificar la secuencia de tres páginas más popular (es decir, más visitada) de todas. Los archivos de registro son demasiado grandes para guardarlos en la memoria principal a la vez.Encontrar la secuencia de tres elementos más común en un archivo muy grande
Muestra de archivo de registro:
User ID Page ID
A 1
A 2
A 3
B 2
B 3
C 1
B 4
A 4
resultados correspondientes:
A: 1-2-3, 2-3-4
B: 2-3-4
2- 3-4 es la secuencia de tres páginas más popular
Mi idea es usar dos tablas hash. El primer hash en ID de usuario y almacena su secuencia; el segundo hash de secuencias de tres páginas y almacena el número de veces que aparece cada una. Esto toma O (n) espacio y O (n) tiempo.
Sin embargo, dado que tengo que usar dos tablas hash, la memoria no puede contener todo a la vez, y tengo que usar el disco. No es eficiente acceder al disco muy a menudo.
¿Cómo puedo hacer esto mejor?
¿El número de páginas web es bastante grande? (Estoy llegando a la conclusión: ¿es razonable mantener en la memoria una estructura de "visita de 3 páginas"?) –
sí, es muy grande. Es posible que no pueda guardarse en la memoria una vez. – user1002288
Las tablas hash en este caso serían num_users elementos de las últimas dos páginas (pequeño) y uno de (num_pages) * 3 elementos. Me sorprendería que ambas tablas no encajaran en la memoria, y el acceso al disco no puede ser mucho menor. –