два опорных элемента по цене одного
Sep. 12th, 2009 05:46 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avva(эта запись будет интересна программистам и сочувствующим)
Владимир Ярославский из Сана придумал новый вариант Квиксорта, работающий быстрее обычного. Основная идея проста до безобразия: вместо одного опорного элемента (pivot) выбираем два, распихиваем элементы в три подмассива: меньше первого опорного, между первым и вторым, и больше второго, и спускаемся рекурсивно три раза вместо обычных двух.
Трудно представить, что эта идея до сих пор никому не приходила в голову. И тем не менее, может, это так и есть, и тогда это - прекрасный, особенно убедительный пример "очевидности задним умом". Но может быть и по-другому: многие об этом думали, но никто не доводил дело до серьезного анализа.
Автор алгоритма доказывает, путем довольно сложных и скучных выкладок, которые я не проверял, что его Dual-Pivot Quicksort теоретически должен быть быстрее обычного Quicksort в следующем смысле: он делает - на типичных входных данных - примерно столько же сравнений (comparisons), но на 20% меньше обменов элементами (swaps). Его практические измерения подверждают теорию. Интересно, что он специально упоминает, что не может предоставить простое объяснение, почему это так, т.е. почему два опорных элемента должны быть лучше одного. В чем-то лучше, в чем-то хуже, разные факторы балансируют друг против друга и в итоге - согласно Ярославскому - два опорных выигрывают, но простой картинки нет.
P.S. Обнаружилась заявка на патент 2005-го года, "Multiple Pivot Sorting Algorithm". Основная идея та же, но опорных точек там выбирают много (от 3 до 7), и их надо в свою очередь сортировать между собой. Раскладка элементов по подмассивам требует сравнения каждого элемента со всеми опорными меньше его. Мне это кажется довольно дорогим удовольствием: требует намного больше сравнений, чем в теоретически оптимальном двоичном поиске среди отсортированных опорных элементов, каковой реализовать в данном случае невозможно без дополнительного копирования подмассивов. Поэтому мне кажется маловероятным, что этот алгоритм с большим числом опорных точек лучше алгоритма Ярославского; а в частном случае двух опорных точек он точно хуже его. Но никаких проверок я не запускал.
Владимир Ярославский из Сана придумал новый вариант Квиксорта, работающий быстрее обычного. Основная идея проста до безобразия: вместо одного опорного элемента (pivot) выбираем два, распихиваем элементы в три подмассива: меньше первого опорного, между первым и вторым, и больше второго, и спускаемся рекурсивно три раза вместо обычных двух.
Трудно представить, что эта идея до сих пор никому не приходила в голову. И тем не менее, может, это так и есть, и тогда это - прекрасный, особенно убедительный пример "очевидности задним умом". Но может быть и по-другому: многие об этом думали, но никто не доводил дело до серьезного анализа.
Автор алгоритма доказывает, путем довольно сложных и скучных выкладок, которые я не проверял, что его Dual-Pivot Quicksort теоретически должен быть быстрее обычного Quicksort в следующем смысле: он делает - на типичных входных данных - примерно столько же сравнений (comparisons), но на 20% меньше обменов элементами (swaps). Его практические измерения подверждают теорию. Интересно, что он специально упоминает, что не может предоставить простое объяснение, почему это так, т.е. почему два опорных элемента должны быть лучше одного. В чем-то лучше, в чем-то хуже, разные факторы балансируют друг против друга и в итоге - согласно Ярославскому - два опорных выигрывают, но простой картинки нет.
P.S. Обнаружилась заявка на патент 2005-го года, "Multiple Pivot Sorting Algorithm". Основная идея та же, но опорных точек там выбирают много (от 3 до 7), и их надо в свою очередь сортировать между собой. Раскладка элементов по подмассивам требует сравнения каждого элемента со всеми опорными меньше его. Мне это кажется довольно дорогим удовольствием: требует намного больше сравнений, чем в теоретически оптимальном двоичном поиске среди отсортированных опорных элементов, каковой реализовать в данном случае невозможно без дополнительного копирования подмассивов. Поэтому мне кажется маловероятным, что этот алгоритм с большим числом опорных точек лучше алгоритма Ярославского; а в частном случае двух опорных точек он точно хуже его. Но никаких проверок я не запускал.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2009-09-12 04:44 pm (UTC)http://ru.wikipedia.org/wiki/Quicksort
no subject
Date: 2009-09-12 04:07 pm (UTC)no subject
Date: 2009-09-14 09:12 am (UTC)no subject
Date: 2009-09-12 04:24 pm (UTC)no subject
Date: 2009-09-12 05:14 pm (UTC)(no subject)
From: (Anonymous) - Date: 2009-09-12 06:40 pm (UTC) - Expandno subject
Date: 2009-09-12 04:35 pm (UTC)no subject
Date: 2009-09-12 06:52 pm (UTC)no subject
Date: 2009-09-12 09:31 pm (UTC)no subject
Date: 2009-09-12 04:46 pm (UTC)no subject
Date: 2009-09-12 04:49 pm (UTC)no subject
Date: 2009-09-12 05:19 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2009-09-12 05:59 pm (UTC)(no subject)
From:(no subject)
From:no subject
Date: 2009-09-12 05:29 pm (UTC)no subject
Date: 2009-09-12 05:52 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2009-09-12 05:34 pm (UTC)no subject
Date: 2009-09-12 06:16 pm (UTC)no subject
Date: 2009-09-12 06:45 pm (UTC)no subject
Date: 2009-09-12 07:22 pm (UTC)Забавно, квиксорту ведь уже 40 лет
Date: 2009-09-12 06:56 pm (UTC)Интересно, сколько времени займет у этого нового варианта заменить везде квиксорт (אם בכלל).
Re: Забавно, квиксорту ведь уже 40 лет
Date: 2009-09-12 07:12 pm (UTC)Off
Date: 2009-09-12 07:42 pm (UTC)http://a-future.ru/sistemy-iskusstvennogo-intellekta-zh-l-lorer.html
Re: Off
Date: 2009-09-12 08:08 pm (UTC)Re: Off
From:Re: Off
From:Re: Off
From:Re: Off
From:no subject
Date: 2009-09-12 09:48 pm (UTC)no subject
Date: 2009-09-13 12:45 am (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2009-09-12 11:05 pm (UTC)А я вот как-то выдумал алгоритм в несколько раз быстрее квиксорта
для массивов строк.
Наверное он похож на алгоритм Седжвика, но мне кажется должен быть быстрее.
Идея такая:
Рекурсивно, начиная со старшего байта:
1) вычисляем гистограмму встречающихся байт и сортируем на 256 кусков
в один проход
2) для каждого из 256 покусков повторяем 1) для 2го байта и т.д.
Конечно для ограничения вырождения алгоритм нужно усложнить.
Но вот в самом примитивном уровне как он выглядит на С++:
void ByteSort(char ** data, size_t Num, size_t size, size_t offset=0)
{
size_t i, S[256], // starting index per group
H[256]; // (histogram) number of elements in group
// init historgram:
memset(H, 0, sizeof(H));
// 1st path: make historgram of byte values:
for(i=0; i < Num; i++)
++H[ data[i][offset] ];
// calculate staring index positions:
size_t s = 0;
for(i=0; i < 256; i++)
{ S[i] = s; s += H[i]; }
// sorting by regrouping data:
char ** ds = // array of sorted elements
new char * [ Num ]; // alocate memory for large groups
for(i=0; i < Num; i++)
{
char * d = data[i];
ds[ S[ d[offset] ]++ ] = d; // increment current position and copy element
}
memcpy(data, ds, sizeof(*data)*Num); // copy sorted array back
delete [] ds; // free mem
// make starting indexes again:
s = 0;
for(i=0; i < 256; i++)
{ S[i] = s; s += H[i]; }
// sort recurecively all the groups:
if(--size)
{
++offset;
for(i=0; i < 256; i++)
if(H[i] > 1)
ByteSort(data + S[i], H[i], offset, size);
}
}
Мне интересно, кто-нибудь теоретически может оценить, насколько он быстрее?
По тестам со случайными массивами работает раз в 10 быстрее квиксорта.
Плохие случаи я не исследовал.
no subject
Date: 2009-09-12 11:50 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2009-09-13 02:30 pm (UTC)no subject
Date: 2009-10-07 06:44 pm (UTC)no subject
Date: 2010-12-20 06:02 am (UTC)