Поиск наиболее распространенной последовательности из трех элементов в очень большом файле

Ответ 1

Если вы хотите быстро получить приблизительный результат, используйте хеш-таблицы, как вы планировали, но добавьте очередь ограниченного размера в каждую хеш-таблицу, чтобы удалить наименее недавно используемые записи.

Если вы хотите получить точный результат, используйте внешнюю процедуру сортировки для сортировки журналов по идентификатору пользователя, затем объедините все три последовательные записи и выполните сортировку снова, на этот раз - по идентификаторам страницы.

Обновить (сортировать по метке времени)

Некоторая предварительная обработка может потребоваться для правильного использования временных меток журналов:

• Если файлы журналов уже отсортированы по метке времени, предварительная обработка не требуется.
• Если есть несколько файлов журналов (возможно, из независимых процессов), и каждый файл уже отсортирован по метке времени, откройте все эти файлы и используйте сортировку слияния, чтобы прочитать их.
• Если файлы сортируются по меткам времени (как если бы несколько независимых процессов записывали журналы в один файл), используйте двоичную кучу, чтобы получить данные в правильном порядке.
• Если файлы не сортируются по метке времени (что маловероятно на практике), используйте внешнюю сортировку по метке времени.

Update2 (Улучшение приближенного метода)

Приблизительный метод с очередью LRU должен давать неплохие результаты для случайно распределенных данных. Но посещения веб-страниц могут иметь разные шаблоны в разное время суток или могут быть разными по выходным. Первоначальный подход может дать плохие результаты для таких данных. Чтобы улучшить это, можно использовать иерархическую очередь LRU.

Разбить LRU на очереди в лог (N) меньших очередей. С размерами N/2, N/4,... Наибольший должен содержать любые элементы, следующие один - только элементы, видимые как минимум 2 раза, следующий один - по меньшей мере 4 раза,... Если элемент удален из некоторого суб -queue, он добавляется к другому, поэтому он живет во всех под-очередях, которые ниже по иерархии, до того, как они полностью удалены. Такая очередь приоритетов по-прежнему имеет сложность O (1), но позволяет гораздо лучше приблизить для большинства популярных страниц.

Ответ 2

Вероятно, здесь есть синтаксические ошибки, но это должно занимать ограниченное количество ОЗУ для файла журнала с неограниченной длиной.

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 last pass, fix rounding errors
        maxpage = MAX_INT;
    while(logfile >> curuser >> curpage) { //read in line
        sequence& curhistory = userhistory[curuser]; //find that user 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 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";

Обратите внимание, что если вы pageid или userid равны string вместо int s, вы получите значительный штраф скорости/размера/кеширования.

[EDIT2] Теперь он работает в 4 (настраиваемых) проходах, что означает, что он использует меньше памяти, что делает эту работу реалистично в ОЗУ. Он просто идет пропорционально медленнее.

Ответ 3

Если у вас 1000 веб-страниц, у вас есть 1 миллиард возможных трехстраничных последовательностей. Если у вас есть простой массив из 32-битных счетчиков, вы будете использовать 4 ГБ памяти. Могут быть способы сократить это, отбросив данные по мере их поступления, но если вы хотите гарантировать правильный ответ, это всегда будет вашим худшим случаем - не избежать его и изобретать способы сохранения памяти в средний случай сделает наихудший случай еще более голодным.

Кроме того, вы должны отслеживать пользователей. Для каждого пользователя вам нужно сохранить последние две страницы, которые они посетили. Предполагая, что пользователи упоминаются по имени в журналах, вам нужно будет хранить имена пользователей в хеш-таблице, а также два номера страниц, поэтому пусть скажем, что в среднем 24 байта на пользователя (вероятно, консервативный - я предполагаю короткие имена пользователей). С 1000 пользователей, которые будут 24 КБ; с 1000000 пользователей 24 МБ.

Очевидно, что счетчики последовательностей доминируют над проблемой памяти.

Если у вас есть только 1000 страниц, тогда 4 ГБ памяти не является необоснованным на современной 64-разрядной машине, особенно с большим количеством виртуальной памяти с поддержкой диска. Если у вас недостаточно пространства подкачки, вы можете просто создать mmapped файл (в Linux - я предполагаю, что Windows имеет нечто подобное) и полагаться на ОС, чтобы всегда иметь к большинству использованных случаев, кэшированных в памяти.

Итак, в основном, математика диктует, что если у вас есть большое количество страниц для отслеживания, и вы хотите иметь возможность справиться с наихудшим случаем, тогда вам придется принять, что вам придется использовать файлы на диске.

Я думаю, что хэш-таблица с ограниченным объемом, вероятно, является правильным ответом. Вероятно, вы можете оптимизировать его для конкретной машины, задав ее в соответствии с доступной памятью. Получив это, вам нужно обработать случай, когда таблица достигает емкости. Возможно, это не должно быть ужасно эффективным, если вы, вероятно, редко попадаете туда. Вот некоторые идеи:

• Вырезать наименее часто используемые последовательности для файла, сохраняя наиболее распространенные в памяти. Мне нужно два прохода над столом, чтобы определить, какой уровень ниже среднего, а затем сделать выселение. Как-то вам нужно знать, где вы поместили каждую запись, всякий раз, когда вы получаете хэш-промах, что может оказаться сложным.

• Просто выгрузите всю таблицу в файл и создайте новую с нуля. Повторение. Наконец, рекомбинируйте совпадающие записи из всех таблиц. Последняя часть также может оказаться сложной.

• Используйте файл mmapped для расширения таблицы. Убедитесь, что файл используется в основном для наименее часто используемых последовательностей, как в моем первом предложении. В принципе, вы просто будете использовать его как виртуальную память - файл будет бессмыслен позже, после того, как адреса будут забыты, но вам не нужно будет так долго. Я предполагаю, что здесь недостаточно регулярной виртуальной памяти и/или вы не хотите ее использовать. Очевидно, что это только для 64-битных систем.

Ответ 4

Думаю, вам нужно сохранить только самую последнюю тройку для каждого пользователя? Итак, у вас есть две таблицы хэша. Первый содержащий ключ идентификатора пользователя, значение последней увиденной тройки имеет размер, равный числу пользователей.

EDIT: предполагается, что файл уже отсортирован по метке времени.

Вторая хеш-таблица имеет ключ userid: page-triple и значение подсчета времени.

Я знаю, что вы сказали С++, но здесь некоторый awk, который делает это за один проход (должен быть довольно прямой для преобразования в С++):

#  $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";
}

Ответ 5

Если вы используете Unix, команда sort может работать с произвольно большими файлами. Таким образом, вы можете сделать что-то вроде этого:

• sort -k1,1 -s logfile > sorted (обратите внимание, что это стабильный вид (-s) в первом столбце)
• Выполните произвольную обработку sorted, которая выводит каждый триплет как новую строку в другой файл, скажем triplets, используя либо С++, либо оболочку script. Поэтому в приведенном примере вы получаете файл с тремя строками: 1-2-3, 2-3-4, 2-3-4. Эта обработка выполняется быстро, потому что шаг 1 означает, что вы имеете дело только с посещением одного пользователя за раз, поэтому вы можете работать через файл sorted по очереди за раз.
• sort triplets | uniq -c | sort -r -n | head -1 должен давать наиболее распространенный триплет и его счетчик (он сортирует триплеты, подсчитывает вхождения каждого, сортирует их в порядке убывания count и берет верхний).

Этот подход может не иметь оптимальной производительности, но он не должен исчерпываться.