Что-то быстрее, чем std :: nth_element

Вам действительно нужен n-й элемент, или вам нужен элемент «около» середины?

Есть более быстрые способы получить элемент «около» середины. Один пример выглядит примерно так:

function rough_middle(container)
divide container into subsequences of length 5
find median of each subsequence of length 5 ~ O(k) * O(n/5)
return rough_middle( { median of each subsequence} ) ~ O(rough_middle(n/5))

Результатом должно быть что-то примерно посередине. Алгоритм реального n-го элемента может использовать что-то подобное выше, а затем очистить его, чтобы найти фактический n-й элемент.

В n=5Вы получаете середину.

В n=25Вы получите середину короткой последовательности середины. Это будет больше, чем все меньшие из каждой короткой последовательности, или, по крайней мере, 9-й элемент и не более, чем 16-й элемент, или 36% от края.

В n=125Вы получаете грубую середину каждой средней последовательности. Это как минимум 9-я середина, поэтому на 8 * 3 + 2 = 26 элементов меньше, чем ваша грубая середина, или на 20,8% от края.

В n=625Вы получаете грубую середину каждой средней последовательности. Это как минимум 26-я середина, поэтому на 77 элементов меньше, чем ваша грубая середина, или на 12% от края.

В n=5^kГрубая середина 5^(k-1) грубые середины. Если грубая середина 5^k последовательность r(k), затем r(k+1) = r(k)*3-1 ~ 3^k,

3^k растет медленнее, чем 5 ^ K в О-записи.

3^log_5(n)
= e^( ln(3) ln(n)/ln(5) )
= n^(ln(3)/ln(5))
=~ n^0.68

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

Теоретически, это может занять около n^0.33 итерации сокращений для достижения одного элемента, что не очень хорошо. (число бит в n ^ 0,68 ~ 0,68 раз больше количества бит в n. Если мы сильно сбреем каждую грубую середину, нам нужно повторить это очень грубо n^0.33 раз количество бит в n, чтобы потреблять все биты — больше, потому что, как мы вычитаем из n, следующий n получает немного меньшее значение, вычтенное из него).

Способ решения n-го элемента, который я видел, решает эту проблему, выполняя разбиение и восстановление на каждом уровне: вместо повторения в rough_middleВы вернетесь в middle, Таким образом, настоящая середина медиан будет гарантированно находиться довольно близко к фактической середине вашей последовательности, и вы сможете относительно быстро «найти настоящую середину» (в О-записи).

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

Но на практике вероятность того, что ваша последовательность действительно плохая, которая на самом деле занимает n ^ 0,33 шага, чтобы разделить до нуля, может быть действительно низкой. Вроде как проблема быстрой сортировки: медиана из 3 элементов обычно достаточно хороша.

---

Быстрый анализ статистики.

Вы выбираете 5 случайных элементов и выбираете средний.

Медианный индекс набора 2m+1 случайная выборка равномерного распределения следует бета-распределению с параметрами примерно (m+1, m+1), с некоторыми коэффициентами масштабирования для[0,1] интервалы.

Среднее значение медианы явно 1/2. Дисперсия это:

(3*3)^2 / ( (3+3)^2 (3+3+1) )
= 81 / (36 * 7)
=~ 0.32

Выяснение следующего шага выходит за рамки моей статистики. Я буду обманывать.

Если мы представим, что взятие медианного элемента индекса из набора элементов со средним значением 0,5 и дисперсией 0,32 равнозначно усреднению их индекса …

Позволять n Теперь количество элементов в нашем оригинальном наборе.

Тогда сумма индексов медиан коротких последовательностей имеет в среднем n раз n / 5 * 0,5 = 0.1 * n^2, Дисперсия суммы индексов медиан коротких последовательностей составляет n раз n / 5 * 0,32 = 0.064 * n^2,

Если затем разделить значение на n / 5, мы получим:

Таким образом, среднее значение n / 2 и дисперсия 1,6.

О, если бы это было правдой, это было бы здорово. Дисперсия, которая не растет с размером n означает, что как n становится большим, средний индекс медиан коротких последовательностей смехотворно плотно распределен. Я думаю, в этом есть какой-то смысл. К сожалению, мы не совсем это делаем — мы хотим распределение псевдомедианы медиан коротких последовательностей. Что почти наверняка хуже.

---

Реализация подробно. Мы можем с логарифмическим числом накладных расходов памяти сделать грубую медиану на месте. (мы могли бы даже сделать это без памяти!)

Мы поддерживаем вектор из 5 индексов с заполнителем «здесь ничего».

Каждый последовательный слой.

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

В конце мы завершаем.

using target = std::pair<size_t,std::array<size_t, 5>>;
bool push( target& t, size_t i ) {
t.second[t.first]=i;
++t.first;
if (t.first==5)
return true;
}
template<class Container>
size_t extract_median( Container const& c, target& t ) {
Assert(t.first != 0);
std::sort( t.data(), t.data()+t.first, [&c](size_t lhs, size_t rhs){
return c[lhs]<c[rhs];
} );
size_t r = t[(t.first+1)/2];
t.first = 0;
return r;
}
template<class Container>
void advance(Container const& c, std::vector<target>& targets, size_t i) {
size_t height = 0;
while(true) {
if (targets.size() <= height)
targets.push_back({});
if (!push(targets[height], i))
return;
i = extract_median(c, targets[height]);
}
}
template<class Container>
size_t collapse(Container const& c, target* b, target* e) {
if (b==e) return -1;
size_t before = collapse(c, b, e-1);
target& last = (*e-1);
if (before!=-1)
push(before, last);
if (last.first == 0)
return -1;
return extract_median(c, last);
}
template<class Container>
size_t rough_median_index( Container const& c ) {
std::vector<target> targets;
for (auto const& x:c) {
advance(c, targets, &x-c.data());
}
return collapse(c, targets.data(), targets.data()+targets.size());
}

который показывает, как он может работать с контейнерами с произвольным доступом.