(Это интересная проблема, потому что она связана с параллелизмом. Поскольку я раньше не сталкивался с оптимизацией параллельного алгоритма, это довольно забавно: вы можете покончить с некоторыми смехотворно сложными шагами, потому что можете восполнить это позже.В любом случае, на ответ ...)
> " Что я могу сделать быстрее всего? "
Лучшее, что вы можете сделать, это O (K). Ниже я иллюстрирую как простой алгоритм O (K log (K)), так и более сложный алгоритм O (K).
Первый шаг:
Каждому компьютеру нужно достаточно времени, чтобы прочитать каждый элемент.Это означает, что , если элементы уже не находятся в памяти, одной из двух границ времени является O (наибольший размер массива) .Если, например, ваш самый большой размер массива изменяется как O (K log (K)) или O (K ^ 2) или что-то еще, никакие алгоритмические хитрости не позволят вам идти быстрее, чем это.Таким образом, фактическое наилучшее время работы технически составляет O(max(K, largestArraySize)).
Допустим, максимальная длина массивов равна N, что составляет <= K.С вышеупомянутым предостережением мы можем ограничить <code>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 .
ВыМожно также представить это как алгоритм строчной линии из вычислительной геометрии или эффективный вариант шага 'слияния' из mergesort.Элементы с круглыми скобками представляют элементы, с помощью которых мы инициализируем наше потенциальное «потенциальное решение» (на каком-то центральном сервере).Алгоритм будет сходиться на правильных o ответах путем сброса (x) ответов для двух невыбранных o s.
Алгоритм:
- Все компьютеры запускаются как 'активные'.
- Каждый компьютер сортирует свои элементы.(параллельно O (N logN))
- Повторять до тех пор, пока все компьютеры не будут активны:
- Каждый активный компьютер находит следующий по наивысшему элементу элемент (O (1) после сортировки) и передает его центральномуserver.
- Сервер разумно комбинирует новые элементы со старыми элементами K и удаляет равное количество самых низких элементов из объединенного набора.Для эффективного выполнения этого шага у нас есть очередь с глобальным приоритетом фиксированного размера K. Мы вставляем новые потенциально лучшие элементы, и плохие элементы выпадают из набора.Когда элемент выпадает из набора, мы сообщаем компьютеру, который отправил этот элемент, никогда не отправлять другой.(Обоснование: Это всегда поднимает наименьший элемент из набора кандидатов. )
(sidenote: добавление ловушки обратного вызова для выпадения из очереди с приоритетамиявляется операцией O (1).)
Мы можем графически увидеть, что это будет выполнять не более 2K * (findNextHighest_time + queueInsert_time) операций, и при этом элементы естественным образом выпадают из очереди с приоритетами.findNextHighest_time равен O (1), так как мы отсортировали массивы, поэтому, чтобы минимизировать 2K * queueInsert_time, мы выбираем очередь с приоритетом с временем вставки O (1) (например, очередь приоритетов на основе кучи Фибоначчи).Это дает нам время извлечения 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) наивысший элемент своего набора и разбивает набор на элементы <и> it.Это занимает O (N) времени параллельно. - Компьютеры объединяются, чтобы объединить эту статистику в новый набор и найти
K/sqrt(N) самый высокий элемент из , который установлен (назовем его'superstatistic') и обратите внимание, на каких компьютерах есть статистика <и> superstatistic.Это занимает время O (K). - Теперь рассмотрим все элементы меньше, чем статистика их компьютера, на компьютерах, статистика которых меньше, чем суперстатическая. Эти элементы могут быть исключены. Это потому, что элементы, превышающие статистику их компьютера, на компьютерах, статистика которых больше, чем суперстатистические, представляют собой набор из K элементов, которые больше.(См. Рисунок здесь ).
- Теперь компьютеры с неизолированными элементами равномерно перераспределяют свои данные на компьютеры, которые потеряли данные.
- Recurse: у вас все еще есть Kкомпьютеров, но значение N уменьшилось.Если N меньше заранее определенной константы, используйте алгоритм предыдущий , который я упомянул в «простом подходе - O (NlogN + K)»;за исключением этого случая, теперь это O (K).=)
Оказывается, что сокращения составляют O (N) всего (удивительно не порядок K), за исключением, возможно, заключительного шага, который может быть O (K).Таким образом, этот алгоритм O (N + K) = O (K) всего.
Анализ и моделирование времени работы 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 до 
, что весело упрощается до 
Теперь компьютеры с неослабленными элементамиперераспределить их данные (REDIST прямоугольник выше) на компьютеры с удаленными элементами (ELIMIN).Это делается параллельно, когда узкое место в полосе пропускания соответствует длине короткого размера REDIST (поскольку их число превышает число компьютеров ELIMIN, ожидающих своих данных).Поэтому данные будут передаваться так же долго, как и длинная длина прямоугольника REDIST (можно подумать об этом: K/√N * (N-√N) - это область, разделенная на K/√N данные за время, что приводит к O (*)1148 *) время).
Таким образом, на каждом шаге размером 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, поэтому нам нужно было бы выполнить работу 3K log (log (N)). Но -1 играет важную роль в определении размера задачи. Очень маловероятно, что время выполнения на самом деле будет выше линейного, но определенно намного меньше, чем даже N log (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 > (.....)
\_/