Нахождение k наиболее распространенных слов в файле с использованием параллелизма

Question

Это вопрос интервью, который я нашел.
Первая часть состоит в том, чтобы найти k наиболее распространенных слов в файле. Это хорошо известный вопрос, и решение можно найти здесь . Время выполнения этого решения составляет O(nlogk + k), когда n - размер файла.

Вторая часть - это поиск k наиболее распространенных слов в файле, но на этот раз с использованием параллелизма. Это означает, что если мы можем запустить поток m параллельно в нашей системе - как мы можем улучшить решение, описанное выше?

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

У вас есть идея, как реализовать это с помощью параллелизма, чтобы улучшить время выполнения?

Answer 1

Это операция уменьшения карты. Допустим, у нас есть файл с длиной N и M потоков:

1. Каждому потоку назначается часть файла и подсчитывается частота всех слов в его части. Это предполагает, что потоки могут получать доступ к этим данным параллельно с ограниченными расходами: O (N / M)
2. Каждый поток последовательно хэширует слова в M сегментов и отправляет счетчики для сегмента в соответствующий поток, так что каждый поток получает счетчики для примерно равной части слов: O (N / M)
3. Каждый поток объединяет полученные значения для генерации общего количества всех своих слов. То есть объединение M результатов размера O (N / M ^ 2): O (N / M)
4. Каждый поток вычисляет свои верхние значения K и отправляет их в поток обработки результатов: O (log K * N / M)
5. Поток обработки результатов объединяет M отсортированных списков, чтобы извлечь верхние значения K. Важно убедиться, что этот поток может прекратить чтение списка ввода, когда ему не нужны остальные данные. Тогда: O ((K + M) log M)

Таким образом, с помощью M потоков вы можете выполнить всю работу за O ((N / M) * log K + (K + M) * log M).

Если вы используете потоковое параллельное объединение для шага 5, то вы можете уменьшить его до O ((N / M) * log K + K + log M), но это будет лучше, если у вас есть lot потоков.

Answer 2

Вы можете использовать CountMinSketch, чтобы приблизительно сохранить счет в компактной форме O(1). Это дает вам тяжелые нападающие без сохранения слов. Несколько эскизов могут быть объединены как простые суммирования массива, при условии, что используется идентичная хеш-функция. Это позволяет потокам обрабатывать независимые секции параллельно. Это похоже на подход с использованием хеш-таблицы, за исключением того, что вы забыли отображение слова.

Следующим шагом будет сканирование словаря слов для определения top k. Если вы поддерживаете словарь для каждого потока, его можно объединить, а не повторно сканировать файл. Для каждого элемента в этом списке вы запрашиваете его частоту O(1), что позволяет вам ранжировать их для получения наиболее популярных. Поскольку мы заботимся о порядке частот, а не о самих словах, мы уменьшаем O(lg k) до O(lg f). В этом случае слова с одинаковой популярностью включаются в список. Мы можем оценить новое слово с наименьшим частым словом в O(1), если используется SkipList или MinHeap.

Время выполнения - это добавление,

• O(n/T), где n - размер файла, а T - количество потоков
• O(T * m), где m - количество уникальных слов (количество элементов), а потоки T могут выдать все m слов для хеширования
• O(m * lg f), где f - верхние частоты, чтобы найти самые популярные слова

Это приводит к O(n/T) + O(T * m) + O(m * lg f), где n является безусловно доминирующим параметром, поэтому на практике его следует уменьшить до O(n).

Answer 3

Как насчет того, чтобы каждый поток мог найти k, наиболее часто встречающихся в своей части файла, независимо, а затем объединить результаты?

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