два опорных элемента по цене одного
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:07 pm (UTC)no subject
Date: 2009-09-12 04:24 pm (UTC)no subject
Date: 2009-09-12 04:35 pm (UTC)no subject
Date: 2009-09-12 04:44 pm (UTC)http://ru.wikipedia.org/wiki/Quicksort
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:14 pm (UTC)no subject
Date: 2009-09-12 05:19 pm (UTC)no subject
Date: 2009-09-12 05:29 pm (UTC)no subject
Date: 2009-09-12 05:34 pm (UTC)no subject
Date: 2009-09-12 05:37 pm (UTC)http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-fourteen/
no subject
Date: 2009-09-12 05:40 pm (UTC)no subject
Date: 2009-09-12 05:52 pm (UTC)no subject
Date: 2009-09-12 05:52 pm (UTC)no subject
Date: 2009-09-12 05:56 pm (UTC)no subject
Date: 2009-09-12 05:59 pm (UTC)no subject
Date: 2009-09-12 05:59 pm (UTC)no subject
Date: 2009-09-12 06:00 pm (UTC)no subject
Date: 2009-09-12 06:16 pm (UTC)no subject
Date: 2009-09-12 06:40 pm (UTC)no subject
Date: 2009-09-12 06:42 pm (UTC)no subject
Date: 2009-09-12 06:45 pm (UTC)no subject
Date: 2009-09-12 06:52 pm (UTC)Забавно, квиксорту ведь уже 40 лет
Date: 2009-09-12 06:56 pm (UTC)Интересно, сколько времени займет у этого нового варианта заменить везде квиксорт (אם בכלל).
Re: Забавно, квиксорту ведь уже 40 лет
Date: 2009-09-12 07:12 pm (UTC)