Тёмная тема
- 1 frag / 2 deaths
- Участник
Ох, википедия, конечно, жжот. Как оказалось, я сначала криво понял суть алгоритма (это Median of Medians который),
ибо в моем понимании начали вылезать косяки.
И полностью алгоритм удалось понять только объединив русскую и английскую вики.
Написать так непонятно, что в обоих вики отсутствуют важные куски - это еще надо уметь...
Может свою статью запилить по разъяснению этого алгоритма XD
Короче, я пока могу реализовать только рекурсивный вариант MofM на списках.
Т.е. решение есть если можно использовать O(logn) памяти.
TarasB
>я посчитал
>для массива из 5^n элементов гарантируется что 3^n меньше
>это соотношение можно сделать сколь угодно поганым и будет скорее квадрат логарифма
Можешь пример последовательности, для которой найдёт хуже некоторого константного процента (например 5%)?
>local_e не инициализируется до while
Ну так вроде это не проблема.
R.I.P.
>Короче, я пока могу реализовать только рекурсивный вариант MofM на списках.
В той версии вот это:
while((n=std::distance(b,e))>4)
//...
e=dst;
- рекурсия.
(Хвостовая, развёрнутая).
FordPerfect
> Можешь пример последовательности, для которой найдёт хуже некоторого
> константного процента (например 5%)?
Пусть есть 5^n элементов. Алгоритм выбрал элемент ИКС.
Значит, среди 5 элементов из последней итерации было три элемента, которые не больше, чем икс.
Значит, в препоследей итерации (в которой из 25 элементов выбрали 5 самых средних) было 9 элементов, которые не больше, чем икс. Про остальные гарантии нет.
На каждой итерации, двигаясь с конца, число элементов в массиве увеличиваем в 5 раз, число элементов, про которые есть гарантия - лишь в три раза.
Пример для 9/25 привести могу. Для остальных лень)
FordPerfect
> Ну так вроде это не проблема.
А, точно.
FordPerfect
> - рекурсия.
Ты рекурсируешь толкьо функцию из первых 2 пунктов. А в википедии имеется в виду рекурсирование полной функции из 5 пунктов.
TarasB
Ок, похоже на то.
Тупой я сегодня.
FordPerfect
> В той версии вот это:
> while((n=std::distance(b,e))>4)
> //...
> e=dst;
> - рекурсия.
> (Хвостовая, развёрнутая).
Вы не поняли сути MofM (в прочем, не удивительно, я сам все до конца понял, только когда сопоставил русскую и английскую вики и глянул в статью).
Вы просто много раз берете пятерки чисел, ищете в них медианы, потом 4/5 чисел отбрасываете и повторяете снова.
MofM устроен не так. Там есть аж дерево рекурсии (т.е. из каждого состояния 2 рекурсивных вызова).
Одно из них размера 1/5n, а другое - не более 7/10n (ну, это где-то в анализе всплывает).
В вашей реализации этого нет.
> Можешь пример последовательности, для которой найдёт хуже некоторого константного процента (например 5%)?
Вот генератор
int Power = 6;
int p3 = 1, p5 = 1;
for (int a=0; a<Power; a++)
{
p3*=3;
p5*=5;
}
int ii = 0;
for (int a=0; a<p3; a++)
{
int pos = 0, z = a;
for (int b=0; b<Power; b++)
{
pos = pos*5 + z%3;
z/=3;
}
A[pos] = ii++;
}
for (int a=1; a<p5; a++)
if (A[a]==0)
A[a] = ii++;
//for (int a=0; a<p5; a++)
// cout << A[a] << " ";
//cout << "\n";
int pivot = * select_pivot( A, A+p5 );
cout << "pivot=" << pivot << "\n";
cout << "total=" << p5 << "\n";
cout << "percent=" << 100.*pivot/p5 << "\n";Для Power=6 пишет:
pivot=728 total=15625 percent=4.6592
R.I.P.
В Кормене (10.3) описание вроде получше, чем в Википедии.
Правка:
Спасибо за пример.
FordPerfect
> В Кормене (10.3) описание вроде получше, чем в Википедии.
о, он и в кормене есть, видимо у меня старое издание
действительно, в кормене все четко и по существу
и описание там совпадает с моим пониманием
И он есть на русском.
FordPerfect
ну, я на русском и прочитал :3
R.I.P.
Рекурсивная версия примерно так выглядит?
template<typename ForwardIterator> ForwardIterator median5(ForwardIterator b,ForwardIterator e) { ForwardIterator src_b=b,src_e,dst=b; while( src_b!=e) { size_t m; src_e=src_b; for( size_t i=0;i<5&&src_e!=e;++i) src_e=next( src_e); m=std::distance( src_b,src_e); bubble_sort( src_b,src_e); swap( *dst,*( next( src_b,m/2))); src_b=src_e; dst=next( dst); } return dst; } template<typename ForwardIterator> ForwardIterator select( ForwardIterator b,ForwardIterator e,size_t index) { size_t n=distance( b,e); size_t p1,p2; ForwardIterator med; ForwardIterator pivot; pair<ForwardIterator,ForwardIterator> range; if( n<5) { bubble_sort( b,e); swap( *b,*next( b,index)); return b; } med=median5( b,e); pivot=select( b,med,distance( b,med)/2); range=partition_range( b,e,pivot); p1=distance( b,range.first); p2=distance( b,range.second); if( index<p1) return select( b,range.first,index); else if( index<p2) return range.first; else return select( range.second,e,index-p2); } template<typename ForwardIterator> ForwardIterator select_pivot( ForwardIterator b,ForwardIterator e) { return select( b,e,distance( b,e)/2); }
FordPerfect
да, похоже на правду
даже обошел возможные проблемы если вдруг ключей равных пивоту очень много)
А ведь я кажется вижу, как реализовать алгоритм без рекурсии.
Смотрите.
Берём K ~ (log(n))^2.
Отводим первые 2*K элементов под "стек" из K бит (порядок чисел значений в каждой паре кодирует 1 бит). Ищем медиану из остатка.
Нужно чтобы числа в каждой паре были различными. Пытаемся выбрать такие элементы (вроде должно быть возможно за O(n)). Если их выбрать не получается, значит у нас много одинаковых элементов и медиана - всё-равно один из них.
Иначе делаем ровно то, что раньше, только вызов/return это явные push/pop + goto. Push/pop имеют сложность O((log(n))^2).
Глубину стека храним явно (O(1)).
log(n)^2 потому, что нужен стек на log(n) слотов, и log(n) на кодирование значения (т. к. и index и distance(b,e) не имеет смысла быть больше n).
Для маленьких размеров - bubble sort.
То, что мы ищем не честную медиану нам не мешает, т. к. (log(n))^2 по сравнению с n не ухудшит сходимость quicksort'а.
Торможу?
Правка: значения - не обязательно числа.
FordPerfect
о, походу пошли извращения в стиле вот этого: http://habrahabr.ru/post/205290/ )
у меня тоже были мысли насчет кодирования стека чем-нибудь, но у меня там мысли пошли в сторону
"а сколько бит может быть в числе и могу ли я брать многобитные числа и считать, что операции над ними идут за O(1)"
после этих мыслей я забил на дальнейшие рассуждения)
вообще говоря можно всю необходимую инфу по стеку хранить в одном 64-битном числе и этого хватит на все разумные сценарии
но как смотреть с академической точки зрения - я вот хз)
брать для кодирования этого числа сами элементы массива - идея, в принципе, интересная
и вроде бы обходит эту проблему. надо глубже над этим подумать
я щас сам торможу - 5й час ночи местного времени:) с утра (скорее, с дня) на свежую голову подумаю
FordPerfect
Пришли пару мыслей по поводу организации "стека".
А именно - как искать К различных пар элементов и что делать, если таких нет.
(Ну, чтобы еще было за линию и на списке работало)
Пусть нам надо найти K пар таких чисел.
Просто идем и считаем число пар соседних элементов, которые не равны.
Если их хотя бы 2K-1 - вторым проходом перемещаем К пар в начало списка и спокойно ищем медиану в остатке, юзая эти 2K элементов на нужды стека.
Если их < 2K-1 - то, по принципу Дирихле, найдется кусок подряд идущих равных элементов, длина которого не менее O(N/K). Пусть эти элементы равны x.
Поскольку K - это какая-то там степень логарифма, то N/2K > K, для всех N > некоторой константы.
Теперь проходимся по массиву еще раз и считаем сколько элементов, которые не равны x.
Если их хотя бы K, то образуем пары из них и элементов, которые равны x.
Иначе - у нас тупо почти все элементы одинаковые. Ну, аж N-K+1 штук, как минимум.
И вроде бы N-K+1>C*N, где C константа (ну, опять же для бостаточно большого N), поэтому селект для квиксорта назначаем этот самый элемент x.
Тема в архиве.