Найти наибольшие k чисел в k массивах, хранящихся в k машинах

Это вопрос интервью. У меня есть K-машины, каждая из которых подключена к 1 центральной машине. Каждый из машин K имеет массив из 4 байтов в файле. Вы можете использовать любую структуру данных для загрузки этих чисел в память на этих машинах, и они подходят. Номера не уникальны для машин K. Найдите K наибольших чисел в объединении чисел на всех машинах K. Что самое быстрое, что я могу сделать?

Ответ 1

Найдите наибольшие числа на каждой машине. О (п * журнала (к))
Объедините результаты (на централизованном сервере, если k не является огромным, в противном случае вы можете объединить их в иерархию дерева по серверному кластеру).

Обновление: чтобы это стало ясно, шаг комбайна не сортирован. Вы просто выбираете верхние k чисел из результатов. Есть много способов сделать это эффективно. Например, вы можете использовать кучу, нажимая головку каждого списка. Затем вы можете удалить голову из кучи и вытащить головку из списка, к которому принадлежит элемент. Выполнение этого k раз дает вам результат. Все это O (k * log (k)).

Ответ 2

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

> "Что самое быстрое, что я могу сделать это?"

Лучшее, что вы можете сделать, это O (K). Ниже я иллюстрирую как простой алгоритм O (K log (K)), так и более сложный алгоритм O (K).

Первый шаг:

Каждому компьютеру требуется достаточно времени для чтения каждого элемента. Это означает, что, если элементы уже находятся в памяти, одна из двух границ во времени равна O (наибольший размер массива). Если, например, ваш самый большой размер массива изменяется как O (K log (K)) или O (K ^ 2) или что-то в этом роде, никакая алгоритмическая обманка не позволит вам идти быстрее. Таким образом, фактическое лучшее время работы O(max(K, largestArraySize)) технически.

Скажем, массивы имеют максимальную длину N, которая равна <= K. С приведенным выше предостережением нам разрешено связать N<K, так как каждый компьютер должен хотя бы один раз смотреть на каждый из своих элементов (O (N) для предварительной обработки на компьютер), каждый компьютер может выбирать самые большие элементы K (это известно как найти статистику k-го порядка, см. эти алгоритмы ). Более того, мы можем сделать это бесплатно (так как это также O (N)).

Оценки и разумные ожидания:

Давайте начнем с рассмотрения некоторых наихудших сценариев и оценок минимального необходимого объема работы.

Одна оценка минимальной работы - O (K * N/K) = O (N), потому что нам нужно взглянуть на каждый элемент, по крайней мере. Но, если мы умны, мы можем распределить работу равномерно на всех K-компьютерах (отсюда и на K).
Еще одна необходимая минимальная работа - O (N): если один массив больше всех элементов на всех других компьютерах, мы возвращаем набор.
Мы должны вывести все K элементов; это, по крайней мере, O (K), чтобы распечатать их. Мы можем избежать этого, если мы довольствуемся просто знанием того, где находятся элементы, и в этом случае не обязательно применяется O (K).

Можно ли достичь этой границы O (N)? Посмотрим...

Простой подход - O (NlogN + K) = O (KlogK):

Теперь давайте придумаем простой подход, который достигает O (NlogN + K).

Рассмотрим данные, упорядоченные так, где каждый столбец является компьютером, и каждая строка является числом в массиве:

computer: A  B  C  D  E  F  G
      10 (o)      (o)          
       9  o (o)         (o)    
       8  o    (o)             
       7  x     x    (x)        
       6  x     x          (x)  
       5     x     ..........     
       4  x  x     ..          
       3  x  x  x  . .          
       2     x  x  .  .        
       1     x  x  .           
       0     x  x  .

Вы также можете представить это как алгоритм развертки из геометрии вычислений или эффективный вариант шага 'merge' от mergesort, Элементы с круглыми скобками представляют собой элементы, с помощью которых мы будем инициализировать наше потенциальное "решение кандидата" (на некотором центральном сервере). Алгоритм будет сходиться в правильных ответах o путем сброса ответов (x) для двух невыбранных o s.

Алгоритм:

Все компьютеры запускаются как "активные".
Каждый компьютер сортирует свои элементы. (параллельный O (N logN))
Повторяйте, пока все компьютеры не активны:
- Каждый активный компьютер находит следующий высший элемент (O (1) после сортировки) и передает его на центральный сервер.
- Сервер сочетает в себе новые элементы со старыми элементами K и удаляет равное количество наименьших элементов из объединенного набора. Для эффективного выполнения этого шага у нас есть глобальная очередь приоритетов фиксированного размера K. Мы вставляем новые потенциально лучшие элементы, а плохие элементы выпадают из набора. Всякий раз, когда элемент выпадает из набора, мы говорим компьютеру, который отправил этот элемент, чтобы никогда не отправлять другой. (Обоснование: это всегда поднимает наименьший элемент набора кандидатов.)

(sidenote: добавление крюка обратного вызова к выходу из очереди приоритетов - операция O (1).)

Графически видно, что это будет выполнять не более 2K * (findNextHighest_time + queueInsert_time) операций, и, как мы это делаем, элементы, естественно, выпадают из очереди приоритетов. findNextHighest_time - это O (1), поскольку мы сортировали массивы, поэтому, чтобы минимизировать 2K * queueInsert_time, мы выбираем очередь приоритетов с временем вставки O (1) (например, очередь приоритетов на основе Fibonacci-heap). Это дает нам время извлечения O (log (queue_size)) (мы не можем вводить и извлекать O (1)); однако нам никогда не нужно использовать операцию извлечения! Как только мы закончим, мы просто выгружаем очередь приоритетов как неупорядоченный набор, который принимает O (queue_size) = O (K).

Таким образом, мы имеем общее время работы O (N log (N) + K) (параллельная сортировка, а затем O (K) * O (1) вставки очереди приоритетов). В худшем случае N = K это O (K log (K)).

Лучший подход - O (N + K) = O (K):

Однако я придумал лучший подход, который достигает O (K). Он основан на медианном медианном алгоритме выбора, но распараллелен. Это происходит следующим образом:

Мы можем исключить набор чисел, если мы точно знаем, что среди всех компьютеров есть не менее K (не строго) большее число.

Алгоритм:

Каждый компьютер находит sqrt(N) самый высокий элемент своего набора и разбивает его на элементы < и > это. Это занимает время O (N) параллельно.
Компьютеры объединяются, чтобы объединить эти статистические данные в новый набор и найти K/sqrt(N) самый высокий элемент этого набора (назовите его "суперстатическим" ) и обратите внимание, какие компьютеры имеют статистику < и > сверхстатистический. Это занимает время O (K).
Теперь рассмотрим все элементы, меньшие, чем их компьютерная статистика, на компьютерах, статистика которых меньше, чем суперстатистика. Эти элементы могут быть устранены. Это потому, что элементы, превышающие их компьютерную статистику, на компьютерах, статистика которых больше, чем суперстатистика, представляют собой набор из K элементов, которые больше. (См. Визуальный здесь).
Теперь компьютеры с неуправляемыми элементами равномерно перераспределяют свои данные на компьютеры, которые потеряли данные.
Recurse: у вас все еще есть K-компьютеры, но значение N уменьшилось. Когда N меньше заданной константы, используйте алгоритм предыдущий, упомянутый в "простом подходе - O (NlogN + K)"; за исключением этого случая, теперь O (K). =)

Оказывается, что сокращения - это O (N) total (удивительно не порядок K), за исключением, возможно, последнего шага, который может быть O (K). Таким образом, этот алгоритм O (N + K) = O (K) total.

Анализ и моделирование времени работы O (K) ниже. Статистика позволяет нам разделить мир на четыре неупорядоченных множества, представленных здесь как прямоугольник, разделенный на четыре под-ящика:

         ------N-----

         N^.5            
         ________________                     
|       |     s          |  <- computer
|       | #=K s  REDIST. |  <- computer
|       |     s          |  <- computer
| K/N^.5|-----S----------|  <- computer
|       |     s          |  <- computer
K       |     s          |  <- computer
|       |     s  ELIMIN. |  <- computer
|       |     s          |  <- computer
|       |     s          |  <- computer
|       |_____s__________|  <- computer

LEGEND:
s=statistic, S=superstatistic
#=K -- set of K largest elements

(Я бы нарисовал связь между неупорядоченными наборами строк и s-столбцов здесь, но он будет загромождать вещи, см. добавление прямо сейчас.)

Для этого анализа мы будем рассматривать N при его уменьшении.

На данном этапе мы можем устранить элементы, помеченные ELIMIN; это удалило область из представленного выше прямоугольника, уменьшив размер проблемы от K * N до , что смешно упрощает до

Теперь компьютеры с uneliminated элементами перераспределяют свои данные (REDIST прямоугольник выше) на компьютеры с удаленными элементами (ELIMIN). Это делается параллельно, когда узкое место в пропускной способности соответствует длине короткого размера REDIST (поскольку они превосходят число компьютеров ELIMIN, ожидающих их данные). Поэтому данные будут длиться так долго, как длинная длина прямоугольника REDIST (другой способ думать об этом: K/√N * (N-√N) - это область, деленная на K/√N данные за время, в результате чего O (N-√N)).

Таким образом, на каждом шаге размера N мы можем уменьшить размер проблемы до K(2√N-1) за счет выполнения работы N + 3K + (N-√N). Теперь мы возвращаемся. Рекуррентное отношение, которое сообщит нам о нашей эффективности:

T(N) = 2N+3K-√N + T(2√N-1)

Децимация размера подзадачи намного быстрее, чем нормальный геометрический ряд (являющийся √N, а не чем-то вроде N/2, который вы обычно получаете от общих разделов и побед). К сожалению, ни Мастер-теорема, ни мощная теорема Акра-Бацци не работают, но мы можем хотя бы убедить себя, что она линейна с помощью моделирования:

>>> def T(n,k=None):
...      return 1 if n<10 else sqrt(n)*(2*sqrt(n)-1)+3*k+T(2*sqrt(n)-1, k=k)
>>> f = (lambda x: x)
>>> (lambda n: T((10**5)*n,k=(10**5)*n)/f((10**5)*n) - T(n,k=n)/f(n))(10**30)
-3.552713678800501e-15

Функция T(N) в больших масштабах кратна линейной функции x, следовательно, линейная (удвоение входа удваивает выход). Поэтому этот метод почти наверняка достигает границы O(N), которую мы предполагаем. Хотя см. Добавление для интересной возможности.

...

Добавление

Одна ловушка случайно сортируется. Если мы делаем что-то, что случайно сортирует наши элементы, мы по меньшей мере будем подвергать логарифмическому (N) штрафу. Таким образом, лучше подумать о массивах как множеств, чтобы избежать ложного представления о том, что они отсортированы.
Также мы могли бы подумать, что при постоянном объеме работы на каждом шаге 3K нам нужно будет работать 3Klog (log (N)). Но -1 имеет мощную роль в прореживании размера проблемы. Немного возможно, что время выполнения на самом деле является чем-то выше линейного, но определенно намного меньше, чем даже Nlog (log (log (log (N)))). Например, это может быть что-то вроде O (N * InverseAckermann (N)), но при тестировании я попал в предел рекурсии.
O (K), вероятно, происходит только из-за того, что мы должны распечатать их; если мы довольствуемся просто пониманием того, где находятся данные, мы могли бы даже снять O (N) (например, если массивы имеют длину O (log (K)), мы могли бы достигнуть O (log (K )))... но это другая история.
Связь между неупорядоченными множествами заключается в следующем. Повлияли бы на объяснение.

          _
         / \
(.....) > s > (.....)
          s
(.....) > s > (.....)
          s
(.....) > s > (.....)
         \_/

          v

          S

          v

         / \
(.....) > s > (.....)
          s
(.....) > s > (.....)
          s
(.....) > s > (.....)
         \_/

Ответ 3

Сохраняйте минимальную кучу размера "k" на централизованном сервере.
Сначала вставьте первые k элементов в мини-кучу.
Для остальных элементов
- Проверьте (загляните) на элемент min в куче (O (1))
- Если минимальный элемент меньше текущего элемента, удалите элемент min из кучи и вставьте текущий элемент.
Наконец, min heap будет иметь "k" наибольшие элементы
Для этого потребуется время n (log k).

Ответ 4

Я бы предложил что-то вроде этого:

возьмите k наибольших чисел на каждой машине в отсортированном порядке O (Nk), где N - число элементов на каждой машине
сортировать каждый из этих массивов из k элементов по наибольшему элементу (вы получите k массивов из k элементов, отсортированных по наибольшему элементу: квадратная матрица kxk)
возьмите "верхний треугольник" матрицы, сделанной из этих k массивов из k элементов (наибольший элемент k будет в этом верхнем треугольнике)
центральная машина теперь может найти k наибольший элемент этих k (k + 1)/2 элементов

Ответ 5

Пусть машины обнаруживают, что из k наибольших элементов копируют его в datastructure (stack), сортировать его и передавать его на Центральный машина.
На центральной машине получают стеки со всей машины. найти самый большой из элементов в верхней части стеков.
Выделите самый большой элемент из его стека и скопируйте его в "Список TopK" . Оставьте остальные стеки неповрежденными.
Повторите шаг 3, k раз, чтобы получить номера Top K.

Ответ 6

1) сортировать элементы на каждой машине 2) используйте k-двоичную кучу на центральной машине а) заполнить кучу первым (максимальным) элементом с каждой машины б) извлеките первый элемент и верните в кучу первый элемент из машины, на котором вы извлекли этот элемент. (разумеется, heapify your heap, после добавления элемента).

Сортировка будет O (Nlog (N)), где N - максимальный массив на машинах. O (k) - построить кучу O (klog (k)) для извлечения и заполнения кучи k раз.

Сложность max (O (klog (k)), O (Nlog (N)))

Ответ 7

Я бы подумал, что парадигма MapReduce хорошо подходит для такой задачи.

Каждая машина запускает собственную независимую задачу карты, чтобы найти максимальное значение в своем массиве (в зависимости от используемого языка), и это, вероятно, будет сложностью O (N) для N чисел на каждой машине.

Задача уменьшения сравнивает результат с выходами отдельных машин, чтобы дать вам наибольшие числа k.