Это довольно стандартная проблема, для которой существует хорошо известное решение. Вы просто сортируете файлы журнала на каждом компьютере по URL-адресу и затем объединяете их через очередь приоритетов размера k (количество элементов, которые вы хотите) на «главном» компьютере. Этот метод существует с 1960-х годов и до сих пор используется (хотя и слегка изменен) в форме MapReduce.
На каждом компьютере извлеките URL-адрес и счетчик из файла журнала и отсортируйте по URL-адресу. Поскольку файлы журналов больше, чем вписываются в память, вам необходимо выполнить слияние на диске. Это подразумевает чтение фрагмента файла журнала, сортировку по URL-адресу, запись фрагмента на диск. Чтение следующего фрагмента, сортировка, запись на диск и т. Д. В какой-то момент у вас есть фрагменты файла журнала M, каждый из которых отсортирован. Затем вы можете выполнить слияние M-way. Но вместо того, чтобы записывать элементы на диск, вы представляете их в отсортированном порядке (отсортированном по URL-адресу, то есть), «хозяину».
Каждая машина сортирует свой собственный журнал.
«Главный» компьютер объединяет данные с отдельных компьютеров и выполняет выбор K верхнего уровня. Это на самом деле две проблемы, но их можно объединить в одну.
Мастер создает две очереди очередности: одну для слияния и одну для выбора K. Первый имеет размер N, где N - количество компьютеров, с которых они объединяют данные. Второй - размер K: количество элементов, которые вы хотите выбрать. Для этого я использую кучу минут, так как это легко и быстро.
Чтобы настроить очередь слияния, инициализируйте очередь и получите первый элемент с каждого из «рабочих» компьютеров. В псевдокоде ниже «получить наименьший элемент из очереди слияния» означает получение корневого элемента из очереди слияния, а затем получение следующего элемента из того, какой рабочий компьютер представил этот элемент. Поэтому, если очередь содержит [1, 2, 3], а элементы поступают с компьютеров B, C, A (в указанном порядке), то получение младшего элемента означает получение следующего элемента с компьютера B и добавление его в очередь приоритетов.
Мастер затем выполняет следующие действия:
working = get lowest item from merge queue
while (items left to merge)
{
temp = get lowest item from merge queue
while (temp.url == working.url)
{
working.count += temp.count
temp = get lowest item from merge queue
}
// Now have merged counts for one url.
if (topK.Count < desired_count)
{
// topK queue doesn't have enough items yet.
// so add this one.
topK.Add(working);
}
else if (topK.Peek().count < working.count)
{
// the count for this url is larger
// than the smallest item on the heap
// replace smallest on the heap with this one
topK.RemoveRoot()
topK.Add(working)
}
working = temp;
}
// Here you need to check the last item:
if (topK.Peek().count < working.count)
{
// the count for this url is larger
// than the smallest item on the heap
// replace smallest on the heap with this one
topK.RemoveRoot()
topK.Add(working)
}
В этот момент, topK очереди имеет элементы K с самыми высокими пунктами.
Таким образом, каждый компьютер должен выполнить сортировку слиянием, которая представляет собой O (n log n), где n - это количество элементов в журнале этого компьютера. Слияние на ведущем устройстве - это O (n), где n - сумма всех предметов с отдельных компьютеров. Выбор верхних позиций k - O (n log k), где n - это число уникальных адресов.
Сортировка выполняется параллельно, конечно, с каждым компьютером, который готовит свой отсортированный список. Но «слияние» части сортировки выполняется одновременно с подключением главного компьютера, поэтому происходит некоторая координация, и на этом этапе задействованы все машины.
Десятка из каждого компьютера, а затем сортировка в качестве последней вершины 10 может быть с одного компьютера и ни с каких компьютеров. Начните собирать сверху с самого начала, остановитесь, когда вы нажмете номер 10. – SparKot
@SparKot Вы уверены, что мы можем взять только первую десятку с каждого компьютера и выбросить все остальные URL-адреса? Что делать, если первая десятка содержит верхнюю десятку – Michael
Упс! Я согласен с вышеприведенным комментарием. Хороший вопрос +1 – SparKot