C++ поиск медианы
Каждые следующие 100 чисел не зависят от предыдущих?
нет, никак не зависят...
По аналогии с квиксортом можно. Выбираем кандидата, разделяем на 2 части. Ищем в той части, куда должна попасть честная медиана. Правда, возможно std::nth_element так и делает, я хз.
Он, по идее, делает Quick Partition, так что, видимо, что ты говоришь.
Обычно - да, но стандарт не требует такой реализации:
template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
Complexity: Linear on average.
Доброго всем времени суток. Вобщем случилось так, что в программе нужно очень много раз считать медиану (выборка из ~100 float-ов). Можете что-нить посоветовать, что работает побыстрее, чем std::nth_element и др. стандартные сортировки, может быть что-то из intel mkl?http://en.wikipedia.org/wiki/BFPRT, но на 100 элементах выигрыша может и не быть.
Что-то известно о распределении этих чисел?
Но ведь результат даже не будет медианой
upd. А не, будет.
upd. А не, будет.
Про распределение можно сказать следующее:1. числа положительные 2.по порядку медиана для всех ансамблей примерно одинакова, так же большая часть чисел отличается от медианы не более, чем на порядок и есть числа, которые сильно превосходят медиану (на несколько порядков)
Моя идея в том, чтобы оптимизировать все поиски сразу, а не каждый.
Из первых поисков попробовать выделить какое-то множество bucket-ов, 0<x1<x2<...<xN и разложить множество по этим bucket-ам. Потом сразу искать k-ю порядковую статистику в правильном bucket-е.
Наверно, если данные более-менее однородные, то можно подобрать {x_i} так, что оверхед на bucketization будет меньше выигрыша от отсеивания. Ну гарантировать не могу, конечно.
Из первых поисков попробовать выделить какое-то множество bucket-ов, 0<x1<x2<...<xN и разложить множество по этим bucket-ам. Потом сразу искать k-ю порядковую статистику в правильном bucket-е.
Наверно, если данные более-менее однородные, то можно подобрать {x_i} так, что оверхед на bucketization будет меньше выигрыша от отсеивания. Ну гарантировать не могу, конечно.
если нужно разом посчитать медианы для каждого 100-мерного вектора из массива длины N, где N велико, то это надо делать на CUDA, копать в сторону radixsort, но не реализации через thrust, а того, который в CUDA SDK. Я такое уже проворачивал
Оставить комментарий
IVAN26
Доброго всем времени суток. Вобщем случилось так, что в программе нужно очень много раз считать медиану (выборка из ~100 float-ов). Можете что-нить посоветовать, что работает побыстрее, чем std::nth_element и др. стандартные сортировки, может быть что-то из intel mkl?