Как найти наиболее часто посещаемую последовательность из 3 веб-страниц из большого файла журнала с идентификатором пользователя и идентификатором страницы

Question

С учетом файла журнала посещенной страницы:

Userid  PageID
A          1
A          2
A          3
B          2
B          3
C          1
B          4
A          4

Найдите наиболее частую последовательность посещений идентификатора страницы:

 for A : 1-2-3, 2-3-4
 for B : 2-3-4

так, 2-3-4 наиболее часто.

Моя идея:

1. Поместите каждый элемент файла в map1<key:user_id, list<pageID> >.
2. Когда list.size() == 3, создайте новую структуру three_hits для хранения трех ID страницы.
3. Вставьте его в map2<struct three_hits, int counter>.
4. Затем найдите элемент на карте2 с наибольшим значением счетчика.

Объявления:

 struct three_hits
 {
     int f_page;
     int s_page;
     int t_page;  
 };
 map<string, list<int> > map_hit;
 map<struct three_hits, int> map_t_hits;

Сканирование записей:

for each( record: r in log)
{
    if(map_hit.count(r.userid) >0) 
    {
        map_hit[r.uid].second.push_back(r.pageID);

        if(map_hit[r.uid].second.size() ==3)
        {

            list<int> tmp=map_hit[r.uid].second;

            t_hits(tmp[0],tmp[1],tmp[2]);

            // O(n lg n)
            if( map_t_hits.count(t_hits) >0)
                map_t_hits[t_hits]++;
            else
                map_t_hits[t_hits]=1;
        }
        else
        { 
            list<int> tmp(r.pageID);

            map_hit[r.uid]=tmp;
        }
    }
    // O(n)

Выполните итерацию map_t_hits один раз, чтобы найти ключ (t_hits) с наибольшим значением.

Время O (n lg n) и пробел O (n) для карт.

Есть ли лучшие решения?

Answer 1

Вы можете рассмотреть возможность сделать это с помощью сортировки слиянием.Сначала используйте стабильную сортировку по идентификатору пользователя, чтобы собрать все последовательности для данного пользователя, сохраняя первоначальный порядок.Затем отсортируйте все последовательности из 3 веб-страниц и, наконец, посчитайте серии одинаковых последовательностей.Это также O (n log n).Вероятно, на практике это займет немного больше времени, но может занять меньше памяти, если запускаться с использованием внутренней памяти, и может выполняться с сортировками во внешней памяти, если у вас слишком много данных, чтобы поместиться в хранилище одновременно.Будет ли это на самом деле лучше, зависит от деталей вашей конкретной ситуации.