Комментарии 84
Есть ли реализация на ruby?
Если снять требование к памяти, можно использовать какой-нибудь вариант сортировки подсчетом. Время выполнения может быть равным двум проходам по массиву, а в некоторых случаях и меньше.
А можно глупый вопрос? В чём измеряется «время» и «память»? Просто все эти О(1), О(n) и прочее — немного абстрактны и непонятны.
--О(1) означает что как сильно бы вы не увеличивали размер входных данных — время выполнения всегда константа
О(n) означает что время выполнения растет линейно с ростом размера входных данных
О(n) означает что время выполнения растет линейно с ростом размера входных данных
O большое — количество операций для завершения алгоритма. Число платформенно независимое.
Скажем, если вы тратите 1мс на операцию на своей архитектуре, то на сортировку десяти миллионов элементов массива алгоритмом O(N) вы затратите 10000000*0.001 секунд, алгоритмом O(logN) порядка 16*0.001 секунд.
Подробнее --> в википедию.
Скажем, если вы тратите 1мс на операцию на своей архитектуре, то на сортировку десяти миллионов элементов массива алгоритмом O(N) вы затратите 10000000*0.001 секунд, алгоритмом O(logN) порядка 16*0.001 секунд.
Подробнее --> в википедию.
Если мне не изменяет память, то О (О большое) — термин из математического анализа, который задаёт класс функций, ограниченных относительно заданной.
Что я только что прочитал…
Ну, наверное, минусующие могут объяснить гораздо проще и доступнее и при этом строго показать, что O не связано с числом операций?
Если вам проще накидать минусов, чем помочь спрашивающему яснее, чем сделал я — давайте, ещё накидывайте. Так держать!
«Гики всех стран — разъединяйтесь через презрение!»
Если вам проще накидать минусов, чем помочь спрашивающему яснее, чем сделал я — давайте, ещё накидывайте. Так держать!
«Гики всех стран — разъединяйтесь через презрение!»
Точное знание количества операций, выполненных алгоритмом, не играет существенной роли в анализе алгоритмов. Куда более важным оказывается скорость роста этого числа при возрастании объема входных данных. Она называется скоростью роста алгоритма. Небольшие объемы данных не столь интересны, как то, что происходит при возрастании этих объемов. Интересен только общий характер поведения алгоритмов, а не подробности этого поведения.
В случае сортировки для анализа алгоритмов может иметь значение точное число выполненных операций сравнения и обмена. Мы знаем, что для хороших алгоритмов оно растёт, как C*n*log_2(n), но какова константа C? 1.7? 1.1? Или держится меньше 1?
Для небольших объёмов тоже важно. За сколько сравнений можно найти медиану из 5 чисел? А из 7? От этого сильно зависит, на сколько частей делить массив для алгоритма «медианы медиан».
Для небольших объёмов тоже важно. За сколько сравнений можно найти медиану из 5 чисел? А из 7? От этого сильно зависит, на сколько частей делить массив для алгоритма «медианы медиан».
В случае сортировки любой алгоритм порядка O(NlogN) является наилучшим, и его можно считать оптимальным. Более того, любой алгоритм, решающий задачу сортировки быстрее, чем за O(NlogN) операций, не может работать правильно.
А как же тогда сортировка подсчетом?
Да, тут мне следовало уточнить, что O(NlogN) это нижняя граница для алгоритмов сортировки работающих путем последовательного попарного сравнения элементов списка.
ripatti проблема в том, что сортировка подсчетом требует O(k) дополнительной памяти, где k — размер интервала чисел, которые сортируются. Т.е. если у нас могут быть числа от минус миллиона до плюс миллиона, то нам нужно два миллиона битов (а если мы сортируем словарь, а не просто числа, то нам потребуется гораздо больше, но опять же O(k) памяти). Проблему с памятью можно решить например так:
а) разбиваем интервал 0..k на два (0..k/2 и k/2..k)
б) делаем два прохода сортировок. В первом проходе делаем сортировку для чисел только из первого интервала, во втором делаем сортировку для чисел только из второго интервала
в) объединяем результаты (поскольку у нас интервалы не пересекаются, то это сделать просто)
Если мы все еще не решили проблему, то каждый из полученный подинтервалов делится еще раз на два, для подподинтверала делается два сортировка, результаты подподинтервалов объединяются, потом объединяются результаты подинтервалов. Итого получаем время O(NlogK) если хотим снизить потребление памяти до фиксированного. Ну как-то так.
а) разбиваем интервал 0..k на два (0..k/2 и k/2..k)
б) делаем два прохода сортировок. В первом проходе делаем сортировку для чисел только из первого интервала, во втором делаем сортировку для чисел только из второго интервала
в) объединяем результаты (поскольку у нас интервалы не пересекаются, то это сделать просто)
Если мы все еще не решили проблему, то каждый из полученный подинтервалов делится еще раз на два, для подподинтверала делается два сортировка, результаты подподинтервалов объединяются, потом объединяются результаты подинтервалов. Итого получаем время O(NlogK) если хотим снизить потребление памяти до фиксированного. Ну как-то так.
Да я в курсе как она работает. Мне просто фраза
в глаза бросилась. Это утверждение справедливо только когда мы не знаем дополнительной информации об элементах и умеем только их попарно сравнивать и обменивать. Товарищ Informatik уже исправился.
любой алгоритм, решающий задачу сортировки быстрее, чем за O(NlogN) операций, не может работать правильно
в глаза бросилась. Это утверждение справедливо только когда мы не знаем дополнительной информации об элементах и умеем только их попарно сравнивать и обменивать. Товарищ Informatik уже исправился.
habrahabr.ru/post/247053/#comment_8211603
habrahabr.ru/post/247053/#comment_8211719
habrahabr.ru/post/247053/#comment_8212291
Вот эти комментарии, хотя и не идеальны, но объясняют. Ваш же комментарий попросту математически некорректен, за что и минусы.
habrahabr.ru/post/247053/#comment_8211719
habrahabr.ru/post/247053/#comment_8212291
Вот эти комментарии, хотя и не идеальны, но объясняют. Ваш же комментарий попросту математически некорректен, за что и минусы.
Ну, давайте.
ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое
Читаем: «В частности: фраза «сложность алгоритма есть O(f(n))» означает, что...»
Смотрим, что такое «вычислительная сложность». Оп-па:
ru.wikipedia.org/wiki/Вычислительная_сложность
«Временная сложность алгоритма (в худшем случае) — это функция от размера входных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.»
Ещё раз: «равная максимальному количеству элементарных операций».
Таким образом, сложность вычислений пропорциональна количеству элементарных операций.
Так что, коллеги, реплики по поводу математической безграмотности моего объяснения кое-кто поторопился. Моё пояснение хоть и упрощено, но наглядно и достоверно показывает что означает O.
Указанные «неидеальные комментарии» ничего внятного не проясняют, кроме как жестами показывают «ого-го как сложно!..»
ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое
Читаем: «В частности: фраза «сложность алгоритма есть O(f(n))» означает, что...»
Смотрим, что такое «вычислительная сложность». Оп-па:
ru.wikipedia.org/wiki/Вычислительная_сложность
«Временная сложность алгоритма (в худшем случае) — это функция от размера входных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.»
Ещё раз: «равная максимальному количеству элементарных операций».
Таким образом, сложность вычислений пропорциональна количеству элементарных операций.
Так что, коллеги, реплики по поводу математической безграмотности моего объяснения кое-кто поторопился. Моё пояснение хоть и упрощено, но наглядно и достоверно показывает что означает O.
Указанные «неидеальные комментарии» ничего внятного не проясняют, кроме как жестами показывают «ого-го как сложно!..»
Вы правда не понимаете, в чем разница между этими определениями?
Википедия
фраза «сложность алгоритма есть O(f(n))» означает, что с увеличением параметра n, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f(n)
EndUser
O большое — количество операций для завершения алгоритма. Число платформенно независимое.
Я прекрасно вижу, что семантически фраза означает «когда сложность алгоритма равна O(f(n)), то...» (и далее описываются свойства длительности от n с уже принятой договорённостью «сложность=О»), что фактически означает «Примем сложность равной О. Тогда...»
Я прекрасно понимаю, что такое О.
Я прекрасно понимаю, что такое количество элементарных операций.
Я прекрасно отдаю себе отчёт в том, что в первом приближении, равно как и для прикладного программирования в большинстве случаев полезнее объяснять и понимать O как число элементарных операций алгоритма, нежели академически доказывать равенство О какой-нибудь Гамма-функции Эйлера (и да, я в курсе, что это расширение факториала).
Тем более, что в программировании нет других критериев и способов подгонять длительность под какие-либо континуальные функции, кроме как посчитать количество операций.
Именно поэтому я объяснял молодому спрашивающему, что О большое это примерно количество операций алгоритма.
И да, я знаю, что прикладному математику нужно более строго определение. Но спрашивающий — не математик и математиком скорее всего уже не будет.
Я прекрасно понимаю, что такое О.
Я прекрасно понимаю, что такое количество элементарных операций.
Я прекрасно отдаю себе отчёт в том, что в первом приближении, равно как и для прикладного программирования в большинстве случаев полезнее объяснять и понимать O как число элементарных операций алгоритма, нежели академически доказывать равенство О какой-нибудь Гамма-функции Эйлера (и да, я в курсе, что это расширение факториала).
Тем более, что в программировании нет других критериев и способов подгонять длительность под какие-либо континуальные функции, кроме как посчитать количество операций.
Именно поэтому я объяснял молодому спрашивающему, что О большое это примерно количество операций алгоритма.
И да, я знаю, что прикладному математику нужно более строго определение. Но спрашивающий — не математик и математиком скорее всего уже не будет.
Это не отменяет того факта, что спрашивающему нужно корректное определение. Потому что по вашему выходит, что сложность алгоритма может быть O(2n+5), и это вроде как лучше, чем O(3n+6).
Ну так на вашем примере «2n+5 против 3n+6» это и действительно лучше, начиная от 1 до ∞.
Мы ведь не рассматриваем 0 количество данных? Или отрицательную длину массива?
Так что корректность соблюдается.
Конечно, можно было бы добавить, что _обычно_ берётся наивысшая степень полинома, а остальные _обычно_ отбрасываются. Но для больших чисел это само по себе сработает.
А так, да, я видел записи навроде вашей «O(2n+5)» у нормальных лекторов. Так что запись валидна.
Мы ведь не рассматриваем 0 количество данных? Или отрицательную длину массива?
Так что корректность соблюдается.
Конечно, можно было бы добавить, что _обычно_ берётся наивысшая степень полинома, а остальные _обычно_ отбрасываются. Но для больших чисел это само по себе сработает.
А так, да, я видел записи навроде вашей «O(2n+5)» у нормальных лекторов. Так что запись валидна.
O(2n+5) у нормального лектора может быть написано только как промежуточный результат. И оно ничем не лучше O(3n+6) — потому что и то, и другое строго равно O(n).
Внутри O-нотации, к сведению, отбрасываются не только младшие степени полинома — но и константные множители. И это отбрасывание совершенно не связано с большими числами — и именно в этом ваша ошибка и заключалась.
К примеру, вот это утверждение неверно:
Этот алгоритм может проработать 10000000*0.001 секунд — а может и 10000000*1 лет. Все эти подсчеты вести бесполезно — просто потому что во фразе O(N) не указана константа. Никому не известно, сколько операций делает этот алгоритм.
Внутри O-нотации, к сведению, отбрасываются не только младшие степени полинома — но и константные множители. И это отбрасывание совершенно не связано с большими числами — и именно в этом ваша ошибка и заключалась.
К примеру, вот это утверждение неверно:
Скажем, если вы тратите 1мс на операцию на своей архитектуре, то на сортировку десяти миллионов элементов массива алгоритмом O(N) вы затратите 10000000*0.001 секунд
Этот алгоритм может проработать 10000000*0.001 секунд — а может и 10000000*1 лет. Все эти подсчеты вести бесполезно — просто потому что во фразе O(N) не указана константа. Никому не известно, сколько операций делает этот алгоритм.
Ваша упрощение не отражает того факта, что это лишь оценка сверху, причем с точностью до константы, а не точное значение числа операций. Например, функция 4n принадлежит как к классу (множеству функций) O(n), так и к классам O(n log n), O(n2) и так далее. Не обижайтесь, но по вашим постам складывается ощущение, что вы сами не понимаете (или понимаете очень поверхности), что это понятие значит.
Очень грубо говоря, асимптотика показывает, что сложность вычисления определенной функции не будет расти стремительнее, чем заданная O(). Тоесть, если сложность O(n), то при линейном увеличении объема данных, сложность вычисления ф-ции, которая работает с этим объемом данных, не будет расти быстрее линейной зависимости.
Прошу прощения за дилетантскую форму изложения, я профан в CS.
Прошу прощения за дилетантскую форму изложения, я профан в CS.
Мы не знаем природы элементов, может там какие-нибудь строчки или еще какая жесть.
Хмм… То-есть вот совсем неизвестно что за элементы в массиве? А как можно сравнивать элементы неизвестной природы? Каким образом задается их отношение больше-меньше-равно-несравнимо?
Пользовательским компаратором. Представьте, что вы пишете обобщенную сортировку для стандартной библиотеки. И потом пользователь сможет ей отсортировать, скажем, строчки, в своем компараторе прописав «сравнивай их лексикографически, предварительно развернув задом наперед».
Известно, что все элементы одинаковой длины (например, указатели), и что сравнение транзитивно. Время на сравнение элементов, а также на их копирование считается равным О(1) — вне зависимости от истинной сложности. Сложность сортировки вычисляется в «числе сравнений и копирований». Допустимо ли в память O(1) включать память, достаточную для хранения хотя бы одного элемента — вопрос спорный. qsort из stdlib.h обходится без неё.
qsort из stdlib.h обходится без неё.Сомневаюсь, что это правда, она должна использовать её для обмена двух элементов местами (размер элемента в байтах передается как параметр).
немного xor'овой магии, и можно вообще без выделения памяти обойтись при условии элементов одинакового размера) правда размер все равно пригодится
Нужна память O(1) на индексы и указатели. А xor не нужен (он агрессивнее использует память): два объекта в памяти можно обменять байт за байтом.
ну конкретно для обмена двух элементов местами при сортировке можно обойтись таким:
if( x!=y ) {
x ^= y;
y ^= x;
x ^= y;
}
и никакой памяти дополнительной не надо ) причем даже для указателей на строки должно нормально работать)) речь же шла только о использовании памяти при обмене, понятно что в целом для сортировки доп память понадобится, если совсем не извращаться
if( x!=y ) {
x ^= y;
y ^= x;
x ^= y;
}
и никакой памяти дополнительной не надо ) причем даже для указателей на строки должно нормально работать)) речь же шла только о использовании памяти при обмене, понятно что в целом для сортировки доп память понадобится, если совсем не извращаться
Не очень понятно, как на последовательности выполнять «процедуру разделения»: «все элементы меньше опорного в начало массива, а все элементы больше — в конец.» Обычно элемент, больший опорного, кладут по указателю, изначально указывающему на последний элемент сортируемого участка, а этот указатель сдвигают на предыдущий элемент. Но мы двигаться назад не можем!
Насчёт адаптации InPlaceMergeSort к движению «только вперёд» посмотрю. Похоже, что основная проблема там — обменять фрагмент массива длиной A и следующий за ним свободный кусок длиной B местами (с сохранением порядка в первом фрагменте) в случае, когда A>B.
Насчёт адаптации InPlaceMergeSort к движению «только вперёд» посмотрю. Похоже, что основная проблема там — обменять фрагмент массива длиной A и следующий за ним свободный кусок длиной B местами (с сохранением порядка в первом фрагменте) в случае, когда A>B.
Я использовал 2 прохода: сначала пихаем в начало элементы "<", потом после них элементы "=".
В InPlaceMergeSort я не смог придумать как сортировать подмассивы длиной sqrt(n) друг относительно друга без рандомного доступа к памяти. Причем основная проблема — не обменять массивы, а добежать указателями до их начал.
В InPlaceMergeSort я не смог придумать как сортировать подмассивы длиной sqrt(n) друг относительно друга без рандомного доступа к памяти. Причем основная проблема — не обменять массивы, а добежать указателями до их начал.
Понятно. Получается больше обменов, но двумя бегущими вперёд указателями разделить элементы можно.
Да, с сортировкой блоков проблема. Но есть ещё один алгоритм InPlaceMergeSort, основанный на том факте, что мы можем слить два блока длиной A и B, если рядом с ними есть свободное место длиной min(A,B). В случае списков это делается, когда сначала идёт свободное место, потом короткий фрагмент, потом длинный.
Сортировка всего массива выглядит так. Сначала сортируем фрагмент длиной 2/3*N, используя оставшиеся K=N/3 как свободное место. Это можно сделать без рекурсии, работая с фрагментами длиной, равной степени двойки. Придётся, правда, сортировать все фрагменты длины 2, потом длины 4, потом длины 8…
Теперь в цикле, пока K>1, сортируем массив длиной K/2, используя остальные K/2, как свободное место, а потом сливаем отсортированный кусок с большим отсортированным фрагментом. Записываем в K длину свободного куска.
Проблема обмена отсортированного массива со свободным местом остаётся — в алгоритме свободное место всё время убегает в хвост списка, а перед слиянием надо возвращать его в начало.
Да, с сортировкой блоков проблема. Но есть ещё один алгоритм InPlaceMergeSort, основанный на том факте, что мы можем слить два блока длиной A и B, если рядом с ними есть свободное место длиной min(A,B). В случае списков это делается, когда сначала идёт свободное место, потом короткий фрагмент, потом длинный.
Сортировка всего массива выглядит так. Сначала сортируем фрагмент длиной 2/3*N, используя оставшиеся K=N/3 как свободное место. Это можно сделать без рекурсии, работая с фрагментами длиной, равной степени двойки. Придётся, правда, сортировать все фрагменты длины 2, потом длины 4, потом длины 8…
Теперь в цикле, пока K>1, сортируем массив длиной K/2, используя остальные K/2, как свободное место, а потом сливаем отсортированный кусок с большим отсортированным фрагментом. Записываем в K длину свободного куска.
Проблема обмена отсортированного массива со свободным местом остаётся — в алгоритме свободное место всё время убегает в хвост списка, а перед слиянием надо возвращать его в начало.
Да вроде нету там никаких проблем. Пусть наш массив-список выглядит так: вначале 2К неотсортированных элементов, затем отсортированный кусок. Тогда сортируем первые К элементов слиянием, используя вторые К как буфер, а потом сливаем с отсортированным куском в конце, начиная записывать результат с К+1 элемента. Тогда неотсортированная часть сама собой переедет на место первых К элементов, и тем самым мы свели задачу к исходной, только с К вместо 2К. Со случаем, когда длина неотсортированной части нечетна, надо просто аккуратно побороться, можно, например, банально вставить один элемент в отсортированный кусок и свести её к четной.
Сложно. Придётся использовать обе операции (A, F, B) => (F, A+B) и (F, A, B) => (A+B, F), причём аккуратно. Возможно, один раз всё-таки придётся переставить массив длиной N/3 в конец — но там будет просто обмен со свободным местом.
Если я верно вас понял, то да, но ничего особо сложного. Если не сильно заморачиваться по поводу эффективности, то можно для обоих случаев использовать одну версию процедуры слияния, которая принимает итераторы начала сливаемых кусков и их длины, а также итератор по которому писать ответ, а как они там между собой расположены это не её дело. Или всегда использовать первый вариант, а перед слиянием двух соседних кусков в merge sort вначале обменивать второй кусок с буфером местами, как при слиянии с N/2 дополнительной памяти (но опять же не самый эффективный код).
К слову, мне кажется, в качестве первого шага выгоднее сортировать N/2, а не 2N/3 элементов, потому что сортировка слиянием, когда у нас есть N дополнительной памяти, а не N/2, более эффективна за счет того, что мы можем использовать один кусок в качестве источника, а во второй писать ответ, а на следующем шаге просто делать наоборот.
К слову, мне кажется, в качестве первого шага выгоднее сортировать N/2, а не 2N/3 элементов, потому что сортировка слиянием, когда у нас есть N дополнительной памяти, а не N/2, более эффективна за счет того, что мы можем использовать один кусок в качестве источника, а во второй писать ответ, а на следующем шаге просто делать наоборот.
Возможно я не до конца понял условия, но сортировать списки за O(n log n) времени и O(1) памяти умеет обычная сортировка слиянием. Для слияния двух упорядоченных списков в один в отличии от массивов дополнительная память не нужна.
Да, немного неточно. Подразумевалось, что «и на списках в том числе», и еще «модифицировать список нельзя, только ходить по нему». Попробую эту неточность устранить.
модифицировать список нельзя, только ходить по нему
А ответ куда писать тогда?
Можно менять местами два элемента списка (на которые есть указатели/итераторы).
Т.е. структуру списка ломать нельзя, можно только обменивать пары элементов внутри него.
Т.е. структуру списка ломать нельзя, можно только обменивать пары элементов внутри него.
Это извращенное ограничение, если честно, т. к. инвалидируются указатели на элементы списка + требуется использовать потенциально дорогой обмен элементов вместо гарантированно дешевых манипуляций с указателями. Тогда, как выше написали, помогает inplace merge sort (нестабильная версия).
Никогда не храните указатели на элементы внутри контейнеров. Мало ли как оно потом будет само себя модифицировать. Первая же реаллокация того же вектора инвалидирует все все ваши указатели.
Фраза «и на списках в том числе» означает, что я могу запустить свою сортировку не только на списке, но и на массиве, и на векторе и на фиг знает еще какой структуре данных, которая предоставляет мне нужный для этого интерфейс, в котором перевешивание указателей не предусмотрено.
Фраза «и на списках в том числе» означает, что я могу запустить свою сортировку не только на списке, но и на массиве, и на векторе и на фиг знает еще какой структуре данных, которая предоставляет мне нужный для этого интерфейс, в котором перевешивание указателей не предусмотрено.
Никогда не храните указатели на элементы внутри контейнеров.Просто одно из ключевых свойств списков, что операции с ним не меняют указатели на элементы.
хм… замечание-то дельное, перечитал референс по std::list, по сути там можно сортить только так:
some_list.sort();
сортировка заточена под список, она перекидывает указатели, указатели остаются валидны.
я же подразумевал вариант вроде этого, где вместо some_list, в принципе, может быть другой контейнер
sort( some_list.begin(), some_list.end() );
но для list оно что-то даже не компилируется:(
some_list.sort();
сортировка заточена под список, она перекидывает указатели, указатели остаются валидны.
я же подразумевал вариант вроде этого, где вместо some_list, в принципе, может быть другой контейнер
sort( some_list.begin(), some_list.end() );
но для list оно что-то даже не компилируется:(
Не компилируется, потому что
std::sort() хочет случайный доступ к элементам сортируемой структуры (более строго: итератор должен удовлетворять требованиям random access iterator).Вообще, из всех STL-контейнеров помимо вектора указатели на элементы инвалидирует только
std::deque, и то лишь при добавлении не в начало или конец, все остальные контейнеры их сохраняют.
Извините, что вмешиваюсь, но вы точно понимаете друг друга?
Лично я воспринимаю фразу «можно только обменивать пары элементов внутри него» как раз как обмен указателей, а не содержимого элементов. Если это именно то, что подразумевалось (элементы остаются там же, мы только меняем связку типа NextNode, то ответная претензия «т. к. инвалидируются указатели на элементы списка + требуется использовать потенциально дорогой обмен элементов вместо гарантированно дешевых манипуляций с указателями» несостоятельна.
Или под «обменом пар» подразумевается что-то другое?
Лично я воспринимаю фразу «можно только обменивать пары элементов внутри него» как раз как обмен указателей, а не содержимого элементов. Если это именно то, что подразумевалось (элементы остаются там же, мы только меняем связку типа NextNode, то ответная претензия «т. к. инвалидируются указатели на элементы списка + требуется использовать потенциально дорогой обмен элементов вместо гарантированно дешевых манипуляций с указателями» несостоятельна.
Или под «обменом пар» подразумевается что-то другое?
я подразумеваю под элементами — сами сортируемые данные, без отношения к списку.
то есть сам список — контейнер для элементов, является цепочкой вершин, внутри которых находятся элементы. как-то так.
я мог кое-где ошибиться в обозначениях, ибо четкой терминологии заранее не строил.
но, думаю, мы поняли друг друга верно)
то есть сам список — контейнер для элементов, является цепочкой вершин, внутри которых находятся элементы. как-то так.
я мог кое-где ошибиться в обозначениях, ибо четкой терминологии заранее не строил.
но, думаю, мы поняли друг друга верно)
Скажем, есть список ((a1. b1) (a2. b2)… (an. bn)). Вам нужно отсортировать b1...bn по возрастанию, оставив a1...an в том же порядке, в котором они были. Здесь структуру списка нарушать уже нельзя, придётся переставлять части элементов с помощью setcdr.
Обычная сортировка слиянием работает рекурсивно, и тем самым требует O(log n) памяти.
Если сливать за log(N) проходов, получая сначала отсортированные пары, потом четвёрки и т.д. то рекурсия не нужна. Можно отсортировать даже за один проход, сливая нужные фрагменты при первой возможности. И тоже без рекурсии.
Хм, сортировка слиянием без рекурсии — это и есть «обычная» сортировка слиянием? Не знал…
Сортировка слиянием — это когда мы делим массив/список на две части, добиваемся того, чтобы каждая из них была отсортирована, и сливаем. Всё остальное — на какие части делить, в каком порядке сортировать, где брать дополнительную память для слияния и как её использовать, сливать массивы с начала или с конца — всего лишь детали реализации. И кто будет определять, какую из реализаций считать «обычной»? Википедия?
Ну да, тут разница в том, сверху вниз или снизу вверх строится дерево рекурсии. Когда строим снизу вверх, рекурсия спокойно разворачивается в итерации.
Интересно бы еще узнать практическую задачу. Задумался над массив vs linked-list, оверхеды на хранение указателей в каждой ноде, ограничения на доступ и проход по списку. Возможно, используя другие структуры данных или подготавливая входные данные для сортировки (создание массива из списка и потом обратно?) можно было бы проще сделать… Тогда бы и тесты и бенчмарки прогнать можно было, так сказать, эмпирически померяться :)
Практическая задача — вряд ли, я же оговаривался в статье, что интерес чисто академический. Головоломка на пораскинуть мозгами. Впрочем, первый вариант кода можно где-нибудь использовать, лишней O(logn) памяти, думаю, найдется всегда.
Например, односвязный список из массивов? Или список, возникший в большом графе, где ссылки уже входят в глобальную структуру, а выделить массив за её пределами нельзя (всю память пустили на лес односвязных списков для большой LISP-машины)?
А уже есть тесты, с какого количества элементов эта реализация быстрее сортировки слиянием?
Боюсь, она медленнее сортировки слиянием для любого количества элементов. Даже тесты делать руки опускаются.
Она быстрее всегда, потому что обычные сортировки слиянием в этих условиях работать не будут — им нужен либо прямой доступ к памяти, либо модификация списка, либо стек. Вот необычная сортировка может оказаться быстрее…
Плохое требование тут имхо — это O(n log n) в худшем случае, без него вполне реально написать qsort за O(1) дополнительной памяти с выбором рандомного элемента в качестве pivot'а, который будет неплохое время на практике показывать. Можно впрочем сделать как в introsort и запускать предложенный алгоритм или тот же inplace merge sort (любой алгоритм, работающий за O(n log n) в худшем случае), если у qsort дела плохо идут.
Так ведь другие алгоритмы требуют прямого доступа к элементам, который запрещён.
Не очень вас понял, вы точно верно прочитали, что я написал? Я имел ввиду, что если бы требовалась производительность O(n log n) лишь в среднем, а не в худшем случае, то можно было бы написать специальную версию qsort, которая показывала бы неплохое время на практике.
Скорее, это я не очень вас понял. Вы имели в виду quicksort, или описанную в этой статье нерекурсивную адаптацию с последовательным доступом? Мы ещё не знаем, какое время она будет показывать при случайном выборе — заметим, что там процедура разделения массива не такая, как в классике. Имелся в виду обычный inplace merge sort для массива, или ещё не написанную, и не факт, что существующую адаптацию, опять же, для последовательного доступа?
Да, qsort без стека, реализованный по принципу описанному в начале статьи (или сходному с ним), но без всяких там выборов медианного элемента, выбираем случайный элемент в качестве разделителя. Метод разделения, когда идем не с двух сторон указателями, а только с начала в конец довольно известный, называется Lomuto partition. Оверхеда у такого qsort по сравнению с классическим по сути только дополнительный лишний проход по каждому сортируемому отрезку (чтобы определить его длину + на нем же сразу будем выбирать разделитель). Это должно давать неплохую скорость на практике, во всяком случае гораздо быстрее и inplace merge sort, и конечного алгоритма в статье.
Оверхеда у такого qsort по сравнению с классическим по сути только дополнительный лишний проход по каждому сортируемому отрезку (чтобы определить его длину + на нем же сразу будем выбирать разделитель).
Это получается в два раза больше сравнений (на каждом уровне мы дополнительно дважды проходим по каждому второму отрезку — итого вместо N сравнений на разделение получается 2*N), и в два раза больше обменов — если в классическом qsort перемещать нужно только элементы, которые меньше разделителя, но попали в правую часть отрезка — их в среднем N/4, то в разделении проходом с начала массива придётся двигать каждый элемент, меньший разделителя (кроме самых первых) — а их примерно N/2.
inplace merge sort с прямым доступом легко обгоняет как qsort, так и std::sort (если пускать их в равных условиях — скажем, если в std::sort используется дефолтное сравнение, то в merge sort будем использовать #define, который раскрывается в x<y. А при сравнении с qsort будем вызывать функцию через указатель). Для последовательного доступа ещё не дописал. Думаю, что у merge sort хорошие шансы на выигрыш.
Первоисточник идеи неизвестен, гугл по этому поводу по большей части молчитПо запросу quicksort without stack мне гугл выдал интересную статью Quicksort without a stack, где в довольно странно выглядящей статье (1986 года) описывается очень похожий алгоритм.
Правда, кажется, тот алгоритм лучше в виду отсутствия необходимости искать максимумы в блоках. В самом деле, если включить pivot в левый от него блок, подлежащий сортировке, то он и будет наибольшим.
Если бы к этой статье был бы еще бесплатный доступ… Или я не туда нажимал?
Пока сути алгоритма я совсем не понял, но сразу пару вопросов: корректно ли он ловит случаи, когда элементов равных pivot несколько? и еще когда первый или третий блок после разделения оказываются пустыми?
Пока сути алгоритма я совсем не понял, но сразу пару вопросов: корректно ли он ловит случаи, когда элементов равных pivot несколько? и еще когда первый или третий блок после разделения оказываются пустыми?
Из университетской сети мне показывают полную статью. Неуниверситетского интернета рядом не оказалось, попробовал зайти туда с машинки в Германии — показали полный текст. А так, в интернете, видимо, так просто этот текст не найти.
В самом алгоритме я пока особо не разбирался, лишь мельком посмотрел на описание и попробовал провести параллели с вышеизложенной версией.
В самом алгоритме я пока особо не разбирался, лишь мельком посмотрел на описание и попробовал провести параллели с вышеизложенной версией.
Насколько я понимаю, показывает нахаляву только первые пару страниц.
В общем, вот код inplace merge, адаптированный для последовательного доступа. Надо определить три фунцкии:
void* LNext(void*) — перейти к следующему элементу
bool LLess(void *a,void *b) — сравнить два элемента, вернуть true, если a<b
void LSwap(void *a,void *b) — обменять местами два элемента.
Сейчас в качестве LLess стоит (x^5)<(y^5).
На массивах длиной от 6 млн до 100 млн сортировка работает быстрее, чем std::sort (с той же функцией сравнения), в 1.6-1.7 раза.
void* LNext(void*) — перейти к следующему элементу
bool LLess(void *a,void *b) — сравнить два элемента, вернуть true, если a<b
void LSwap(void *a,void *b) — обменять местами два элемента.
Сейчас в качестве LLess стоит (x^5)<(y^5).
На массивах длиной от 6 млн до 100 млн сортировка работает быстрее, чем std::sort (с той же функцией сравнения), в 1.6-1.7 раза.
Когда вы делаете вот так:
Но даже несмотря на передачу по указателю, на gcc 4.9.0 и 10 миллионах (100 на онлайн-компиляторе не выполняется, чуть попозже дома погляжу)
std::sort(arr,arr+len,myfunction);
std::sort(), в отличии от вашей функции сортировки. Лучше сделайте вот так:std::sort(arr,arr+len,[](int i, int j){ return (i^5)<(j^5); });
Но даже несмотря на передачу по указателю, на gcc 4.9.0 и 10 миллионах (100 на онлайн-компиляторе не выполняется, чуть попозже дома погляжу)
std::sort() чуть быстрее, а с заменой на функциональный объект становится быстрее почти в два раза coliru.stacked-crooked.com/a/9dbe1c48ab675c7a. Это так, первый взгляд, нету много времени разбираться пока.
Алгоритм описан на википедии (ru, en), а также в Кормене, но я немного расскажу про него, поскольку на википедии он описан настолько топорно, что я понял его суть только после сопоставления русской и английской версии (и еще пришлось заглянуть в оригинальную статью).
После этого вы улучшили его описание в русской вики? :)
Подумал о «челлендже» и в голову пришла сортировка Шелла.
Выбираем d, проходим по списку первый раз (за линию, храним 2 указателя).
Уменьшаем d, повторяем.
d выбираем так же, как в классической сортировке Шелла, в зависимости от стратегии зависит сложность.
И достижима сложность O(N * log N * log N) в худшем случае, константная память, список не модифицируется.
Это немного больше, чем O (N * log N) из статьи и я не преуменьшаю заслуги исследования, но что-то итоговый алгоритм сложноват получился здесь. И на практике может получиться, что Шелл работает быстрее (на списках помещающихся в память, например).
Выбираем d, проходим по списку первый раз (за линию, храним 2 указателя).
Уменьшаем d, повторяем.
d выбираем так же, как в классической сортировке Шелла, в зависимости от стратегии зависит сложность.
И достижима сложность O(N * log N * log N) в худшем случае, константная память, список не модифицируется.
Это немного больше, чем O (N * log N) из статьи и я не преуменьшаю заслуги исследования, но что-то итоговый алгоритм сложноват получился здесь. И на практике может получиться, что Шелл работает быстрее (на списках помещающихся в память, например).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сортировка на односвязном списке за O(nlogn) времени в худшем случае с O(1) дополнительной памяти