Encontrar la secuencia de tres elementos más común en un archivo muy grande

Question

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.

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?

Answer 1

Si quiere obtener rápidamente un resultado aproximado, use las tablas hash, como deseaba, pero agregue una cola de tamaño limitado a cada tabla hash para eliminar las entradas utilizadas menos recientemente.

Si desea obtener resultados exactos, utilice el procedimiento de clasificación externo para ordenar los registros por ID de usuario, luego combine cada 3 entradas consecutivas y vuelva a ordenar, esta vez por ID de página.

Update (ordenar por fecha y hora)

Algunos pre-procesamiento puede ser necesaria para utilizar correctamente las marcas de tiempo archivos de registro:

• Si los archivos de registro ya están ordenados por fecha y hora, sin procesamiento previo necesario.
• Si hay varios archivos de registro (posiblemente provenientes de procesos independientes), y cada archivo ya está ordenado por marca de tiempo, abra todos estos archivos y use merge sort para leerlos.
• Si los archivos están casi ordenados por marca de tiempo (como si varios procesos independientes escriben registros en un solo archivo), utilice el montón binario para obtener datos en el orden correcto.
• Si los archivos no están ordenados por marca de tiempo (lo cual no es probable en la práctica), utilice la clasificación externa por fecha y hora.

Update2 (Mejora método aproximado)

método aproximado con cola LRU debe producir resultados bastante buenos para los datos distribuidos al azar. Pero las visitas a la página web pueden tener diferentes patrones a diferentes horas del día, o pueden ser diferentes los fines de semana. El enfoque original puede dar resultados pobres para tales datos. Para mejorar esto, se puede usar una cola de LRU jerárquica.

Partición LRU queue en el registro (N) colas más pequeñas. Con tamaños N/2, N/4, ... El más grande debe contener cualquier elemento, el siguiente - solo elementos, vistos al menos 2 veces, el siguiente - al menos 4 veces, ...Si el elemento se elimina de alguna subcola, se agrega a otra, por lo que vive en todas las subcolas, que son inferiores en jerarquía, antes de que se elimine por completo. Dicha cola de prioridad sigue siendo de complejidad O (1), pero permite una mejor aproximación para la página más popular.

Answer 2

Probablemente haya muchos errores de sintaxis aquí, pero esto debería llevar una cantidad limitada de RAM para un archivo de registro de longitud prácticamente ilimitada.

typedef int pageid; 
typedef int userid; 
typedef pageid[3] sequence; 
typedef int sequence_count; 

const int num_pages = 1000; //where 1-1000 inclusive are valid pageids 
const int num_passes = 4; 
std::unordered_map<userid, sequence> userhistory; 
std::unordered_map<sequence, sequence_count> visits; 
sequence_count max_count=0; 
sequence max_sequence={}; 
userid curuser; 
pageid curpage; 
for(int pass=0; pass<num_passes; ++pass) { //have to go in four passes 
    std::ifstream logfile("log.log"); 
    pageid minpage = num_pages/num_passes*pass; //where first page is in a range 
    pageid maxpage = num_pages/num_passes*(pass+1)+1; 
    if (pass==num_passes-1) //if it's last pass, fix rounding errors 
     maxpage = MAX_INT; 
    while(logfile >> curuser >> curpage) { //read in line 
     sequence& curhistory = userhistory[curuser]; //find that user's history 
     curhistory[2] = curhistory[1]; 
     curhistory[1] = curhistory[0]; 
     curhistory[0] = curhistory[curpage]; //push back new page for that user 
     //if they visited three pages in a row 
     if (curhistory[2] > minpage && curhistory[2]<maxpage) { 
      sequence_count& count = visits[curhistory]; //get times sequence was hit 
      ++count; //and increase it 
      if (count > max_count) { //if that's new max 
       max_count = count; //update the max 
       max_sequence = curhistory; //arrays, so this is memcpy or something 
      } 
     } 
    } 
} 
std::cout << "The sequence visited the most is :\n"; 
std::cout << max_sequence[2] << '\n'; 
std::cout << max_sequence[1] << '\n'; 
std::cout << max_sequence[0] << '\n'; 
std::cout << "with " << max_count << " visits.\n"; 

en cuenta que si pageid o userid está string s en lugar de int s, tomará una penalización de velocidad/capacidad/almacenamiento en caché significativa.

[EDIT2] Ahora funciona en 4 pases (personalizables), lo que significa que utiliza menos memoria, por lo que esto funciona de manera realista en la memoria RAM. Simplemente va proporcionalmente más lento.

Answer 3

Si tiene 1000 páginas web, entonces tiene 1 billón de secuencias posibles de 3 páginas. Si tiene una matriz simple de contadores de 32 bits, entonces usaría 4GB de memoria. Puede haber formas de reducir esto descartando datos a medida que avanza, pero si quiere garantizar que obtendrá la respuesta correcta, este siempre será su peor caso: no hay forma de evitarlo e inventar maneras de guardar memoria en el el caso promedio hará que el peor caso tenga aún más memoria hambrienta.

Además de eso, debe rastrear a los usuarios. Para cada usuario, debe almacenar las últimas dos páginas que visitó. Suponiendo que los usuarios son referidos por nombre en los registros, necesitarías almacenar los nombres de los usuarios en una tabla hash, más los dos números de página, así que digamos que 24 bytes por usuario en promedio (probablemente conservador - estoy asumiendo nombres de usuario cortos). Con 1000 usuarios que serían 24KB; con 1000000 usuarios 24MB.

Claramente, los contadores de secuencia dominan el problema de memoria.

Si solo tiene 1000 páginas, entonces 4 GB de memoria no son irrazonables en una máquina moderna de 64 bits, especialmente con una buena cantidad de memoria virtual respaldada por disco. Si no tienes suficiente espacio de intercambio, puedes simplemente crear un archivo mmapped (en Linux - supongo que Windows tiene algo similar), y confiar en que el sistema operativo siempre tiene a la mayoría de los casos usados ​​en la memoria.

Así que, básicamente, las matemáticas dictan que si tiene un gran número de páginas para seguir, y quiere ser capaz de hacer frente al peor de los casos, entonces tendrá que aceptar que tendrá para usar archivos de disco

Creo que una tabla hash de capacidad limitada es probablemente la respuesta correcta. Probablemente pueda optimizarlo para una máquina específica dimensionándola de acuerdo con la memoria disponible. Una vez conseguido, debe manejar el caso donde la tabla alcanza su capacidad. Puede que no necesite ser terriblemente eficiente si es probable que rara vez llegues allí. Aquí hay algunas ideas:

• Expulsa las secuencias menos utilizadas al archivo, manteniendo las más comunes en la memoria. Necesitaría dos pases sobre la mesa para determinar qué nivel está por debajo del promedio y luego hacer el desalojo. De alguna manera, necesitarías saber dónde colocarías cada entrada, cada vez que obtienes un hash-miss, lo que podría ser complicado.

• Simplemente descargue toda la tabla al archivo y cree uno nuevo desde cero. Repetir. Finalmente, recombine las entradas coincidentes de todas las tablas. La última parte también podría ser difícil.

• Utilice un archivo mmapped para ampliar la tabla. Asegúrese de que el archivo se use principalmente para las secuencias menos utilizadas comúnmente, como en mi primera sugerencia.Básicamente, simplemente lo usaría como memoria virtual: el archivo no tendría sentido más adelante, después de que se olvidaran las direcciones, pero no necesitaría mantenerlo así de largo. Supongo que no hay suficiente memoria virtual regular aquí, y/o no quieres usarla. Obviamente, esto es solo para sistemas de 64 bits.

Answer 4

Creo que solo tiene que almacenar el triple visto más recientemente para cada ID de usuario ¿verdad? Así que tienes dos tablas hash. La primera clave que contiene el ID de usuario, el valor del triple visto más recientemente tiene un tamaño igual al número de ID de usuario.

EDIT: asume el archivo ordenado por timestamp ya.

La segunda tabla hash tiene una clave de ID de usuario: página-triple, y un valor del recuento de veces visto.

Sé que dijiste C++ Pero aquí hay algunos awk que hace esto en una sola pasada (debe ser bastante recta hacia adelante para convertir a C++):

# $1 is userid, $2 is pageid 

{ 
    old = ids[$1];   # map with id, most-recently-seen triple 
    split(old,oldarr,"-"); 
    oldarr[1]=oldarr[2]; 
    oldarr[2]=oldarr[3]; 
    oldarr[3] = $2; 
    ids[$1]=oldarr[1]"-"oldarr[2]"-"oldarr[3]; # save new most-recently-seen 
    tripleid = $1":"ids[$1]; # build a triple-id of userid:triple 
    if (oldarr[1] != "") { # don't accumulate incomplete triples 
     triples[tripleid]++; } # count this triple-id 
} 
END { 
    MAX = 0; 
    for (tid in triples) { 
     print tid" "triples[tid]; 
     if (triples[tid] > MAX) MAX = tid; 
    } 
    print "MAX is->" MAX" seen "triples[tid]" times"; 
} 

Answer 5

Si se está utilizando Unix, el comando sort puede hacer frente a archivos arbitrariamente grandes Por lo que podría hacer algo como esto:

1. sort -k1,1 -s logfile > sorted (tenga en cuenta que esto es una especie estable (-s) en la primera columna)
2. realizar algún procesamiento personalizado de sorted que las salidas de cada triplete como una nueva línea a otra archivo, digamos triplets, utilizando C++ o un script de shell. Entonces, en el ejemplo dado, obtienes un archivo con tres líneas: 1-2-3, 2-3-4, 2-3-4. Este proceso es rápido porque el Paso 1 significa que solo está tratando con las visitas de un usuario a la vez, por lo que puede trabajar a través del archivo sorted línea por línea.
3. sort triplets | uniq -c | sort -r -n | head -1 debe dar el triplete más común y su conteo (ordena los trillizos, cuenta las ocurrencias de cada uno, los ordena en orden descendente de conteo y toma el superior).

Este enfoque podría no tener un rendimiento óptimo, pero no debería quedarse sin memoria.