Нахождение k наиболее распространенных слов в файле с использованием параллелизма - PullRequest
0 голосов
/ 11 ноября 2018

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

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

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

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

Ответы [ 3 ]

0 голосов
/ 11 ноября 2018

Это операция уменьшения карты. Допустим, у нас есть файл с длиной 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 потоков.

0 голосов
/ 13 ноября 2018

Вы можете использовать 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).

0 голосов
/ 11 ноября 2018

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

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

...