Найдите медианы в нескольких поддиапазонах неупорядоченного списка

ЦЕЛОЕ ЭЛЕМЕНТЫ:

Если типом ваших элементов являются целые числа, то лучше всего иметь ведро для каждого числа, лежащего в любом из ваших поддиапазонов, где каждое ведро используется для подсчета числа, связанного с ним целого числа, найденного в ваших элементах ввода (например, , bucket[100] хранит количество 100 во входной последовательности). В основном вы можете добиться этого, выполнив следующие шаги:

1. создавать корзины для каждого номера, лежащего в любом из ваших поддиапазонов.
2. перебирать все элементы для каждого числа n, если у нас есть bucket[n], то bucket[n]++.
3. вычислить медианы на основе агрегированных значений, хранящихся в ваших корзинах.

Другими словами, предположим, что у вас есть поддиапазон [0, 10], и вы хотите вычислить медиану. Подход ведра в основном вычисляет, сколько 0 во входных данных, сколько 1 во входных данных и так далее. Предположим, что есть n чисел, лежащих в диапазоне [0, 10], тогда медиана - это n/2-й по величине элемент, который можно определить, найдя i такое, что bucket[0] + bucket[1] ... + bucket[i] больше или равно n/2, но bucket[0] + ... + bucket[i - 1] меньше n/2.

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

Вы также можете использовать иерархические сегменты, которые включают несколько проходов. На каждом проходе bucket[i] подсчитывает, что количество элементов во входных данных находится в определенном диапазоне (например, [i * 2^K, (i+1) * 2^K]), а затем сужает проблемное пространство, определяя, в каком сегменте будет находиться носитель после каждого шага, а затем уменьшает K на 1 в следующий шаг и повторяйте, пока не сможете правильно определить носитель.

ЭЛЕМЕНТЫ ПЛАВАЮЩЕЙ ТОЧКИ

Все элементы могут уместиться в памяти:

Если все ваши элементы могут уместиться в памяти, лучше всего сначала отсортировать элемент N, а затем найти медианы для каждого поддиапазона. линейный решение с кучей времени также хорошо работает в этом случае, если количество ваших поддиапазонов меньше logN.

Все элементы не помещаются в память, а хранятся на одном компьютере:

Обычно для внешней сортировки обычно требуется три сканирования диска. Следовательно, если количество ваших поддиапазонов больше или равно 3, то сначала сортировка N элементов, а затем поиск медиан для каждого поддиапазона путем загрузки только необходимых элементов с диска - лучший выбор. В противном случае лучше просто выполнить сканирование для каждого поддиапазона и выбрать эти элементы в поддиапазоне.

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

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

На практике, потому что вы можете вызывать высоко оптимизированные процедуры сортировки.

Теоретически и, возможно, на практике тоже, потому что, поскольку вы имеете дело с целыми числами, вам не нужно платить n log n за сортировку - см. http://en.wikipedia.org/wiki/Integer_sorting.

Если ваши данные на самом деле представляют собой числа с плавающей запятой, а не NaN, то немного подергивания фактически позволит вам использовать для них целочисленную сортировку - from - http://en.wikipedia.org/wiki/IEEE_754-1985.#Comparing_floating-point_numbers - двоичное представление имеет специальное свойство, которое, исключая NaN, любые два числа можно сравнивать как знаковые и абсолютные целые числа (хотя с современными компьютерными процессорами это больше не применимо напрямую): если знаковый бит отличается, отрицательное число предшествует положительному числу (за исключением того, что отрицательный ноль и положительный ноль следует считать равными), в противном случае относительный порядок такой же, как лексикографический, но инвертированный для двух отрицательных чисел; Применяются проблемы с порядком следования байтов.

Таким образом, вы можете проверить NaN и другие забавы, притвориться, что числа с плавающей запятой являются целыми числами знак + величина, вычесть отрицательные числа, чтобы исправить порядок для отрицательных чисел, а затем рассматривать как обычные целые числа со знаком дополнения 2s, отсортировать, а затем отменить процесс.

Моя идея:

• Сортировать список в массив (используя любой подходящий алгоритм сортировки)

• Для каждого диапазона найдите индексы начала и конца диапазона с помощью двоичного поиска.

• Найдите медиану, просто сложив их индексы и разделив на 2 (т.е. медиана диапазона [x,y] равна arr[(x+y)/2])

Время предварительной обработки: O (n log n) для общего алгоритма сортировки (например, быстрой сортировки) или время работы выбранной процедуры сортировки.

Время на запрос: O (log n)

Динамический список:

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

В конечном итоге ответ будет «в зависимости от обстоятельств». Существует множество подходов, любой из которых, вероятно, подойдет в большинстве случаев, с которыми вы можете столкнуться. Проблема в том, что каждый из них будет работать по-разному для разных входов. Если один может работать лучше для одного класса входных данных, другой будет лучше работать для другого класса входных данных.

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

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