Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте Sergeem, Вы писали:
S>>Ой-ой-ой! А есть ли строгое матеметическое доказательство??? WH>Ключевые слова: константная глубина рекурсии.
не совсем. Если с установленным битом окажется только одно число, то рекурсия дальше не пойдет. Единственное что можно сказать, так это то, что число рекурсий точно больше 1 и не больше числа бит. По определению получается O(N).
MS>Даа, товарищь Atilla. Подобные вещи надо проверять прежде чем постить. Ну хотя бы простейшим стресс-тестированием, как у VVV. Ну это так, замечание на будущее.
Каюсь! Больше так не буду! программил с большого недосыпа
MS>На самом деле, если на практике способ работает медленнее, то что с него толку?
как же медленнее?? По моим прикидкам, для массивов с N=250 млн. они уже должны сравняться. А для short'ов мой алгоритм выигрывает уже при размерах в несколько миллионов.
MS>Вот например, сложность quick sort равна O(N^2).
У qsort и heapsort средняя сложность O(N*log(N)) И это можно доказать.
Вот только максимальная сложность у первого O(N^2), а у второго O(N*log(N)).
MS>А вообще-то, все от задачи зависит. Не бывает идеальной сортировки, так же как и не бывает универсального растворителя.
Абсолютно с Вами согласен! Но я сразу предупредил, что область применимости этого алгоритма — очень большие массивы.
А задумывалось это вообще, почти как шутка и контрпример на утверждение, что в лучшем случае отсортировать можно за O(N*log(N)), а за O(N) невозможно.
Здравствуйте, Atilla, Вы писали:
A>А задумывалось это вообще, почти как шутка и контрпример на утверждение, что в лучшем случае отсортировать можно за O(N*log(N)), а за O(N) невозможно.
Да я говорил уже — bit_set. Ровно O(N), ураган, сказка, пуля! Только не ясно, что делать потом с этими битами. Обычно предполагается наличие некоего ключа сортировки, с ассоциированным с ним значением. Здесь же связь "ключ-значение" полностью теряется. Тем не менее, область применения метода есть, и весьма обширная.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, McSeem2, Вы писали:
MS>Да я говорил уже — bit_set. Ровно O(N), ураган, сказка, пуля! Только не ясно, что делать потом с этими битами. Обычно предполагается наличие некоего ключа сортировки, с ассоциированным с ним значением. Здесь же связь "ключ-значение" полностью теряется. Тем не менее, область применения метода есть, и весьма обширная.
А что за bit-set? Похоже, я чего-то недопонимаю...
Здравствуйте, Atilla, Вы писали:
A>А что за bit-set? Похоже, я чего-то недопонимаю...
Просто битовый вектор, длинный. Размером max_val-min_val+1 в сортируемом массиве. Выставляем в 1 биты, номера которых соответствуют сортируемым числам. Все. Массив отсортирован, но информация потеряна — во-первых, дублирующиеся значения будут слиты в одно, во-вторых, невозможно восстановить связку "ключ-значение". Впрочем, для такой задачи это неважно: http://www.rsdn.ru/forum/Message.aspx?mid=138606&only=1
Здравствуйте, McSeem2, Вы писали:
MS>Действительно инетересно. Вместо O(N*32) получаем O(N*5) при небольшом фиксированном объеме дополнительной памяти. Кто поиграться горазд?
небольшой объем — это второй массив размером с первый.
Если памяти выделить 1>>sizeof(T), то вобще в 2 прохода выполнится, но ведь идея была сделать без выделения новых массивов: как в пузырьке, qsort'е и т.п.
Здравствуйте, Atilla, Вы писали:
A>А задумывалось это вообще, почти как шутка и контрпример на утверждение, что в лучшем случае отсортировать можно за O(N*log(N)), а за O(N) невозможно.
На самом деле, сложность ksort = O(N*M), где M — разрядность. Очевидно, для множества из N чисел разрядность оных (без повторений) будет не менее log2(N).
Законы комбинаторики не объедешь!
Есть же теорема о сложности сортировки: поскольку число C комбинаций из N элементов равно N! --> (N/e)^N,
то достаточно log2(C) = log2(N!) --> N*log2(N/e) сравнений и N-1 парных перестановок.
A>Сортировка за O(N) операций. Сортирует, правда, только массивы целых (это принципиально). Можно и для signed, но это немного посложнее будет. Можно и строки сортировать, но тогда это уже будет bucket sort A>- вроде бы пашет A>Можно, конечно, оптимизировать — и будет еще быстрее работать
A>Так что теперь, если вашу задачу проще решать на сортированном массиве, но от вас требуют линейного времени, можете смело сортировать!
Если я не ошибаюсь, господин Atilla, это обычная побитовая сортировка.
Просто смешно как это ученый человек может подумать, что он нагора может за день выдать новый метод сортировки за O(n).
Здравствуйте, cpp, Вы писали:
cpp>Если я не ошибаюсь, господин Atilla, это обычная побитовая сортировка.
наверное обычная Я на всякий случай тогда пробежался по поисковикам и ничего такого не нашел (были сортировки, когда не бит брался, а несколько разрядов). Вот и сейчас яндекс с рамблером на слова "побитовая сортировка" ничего не выдает...
cpp>Просто смешно как это ученый человек
спасибо
cpp> может подумать, что он нагора может за день выдать новый метод сортировки за O(n).
Вообще-то ветка называется "Исходники", а не "Алгоритмы". Метод новый наверное слабо будет, а вот исходники за часок состряпать — вполне
Здравствуйте, Atilla, Вы писали:
A>Здравствуйте, cpp, Вы писали:
cpp>>Если я не ошибаюсь, господин Atilla, это обычная побитовая сортировка.
A>наверное обычная Я на всякий случай тогда пробежался по поисковикам и ничего такого не нашел (были сортировки, когда не бит брался, а несколько разрядов). Вот и сейчас яндекс с рамблером на слова "побитовая сортировка" ничего не выдает...
cpp>>Просто смешно как это ученый человек A>спасибо
cpp>> может подумать, что он нагора может за день выдать новый метод сортировки за O(n).
A>Вообще-то ветка называется "Исходники", а не "Алгоритмы". Метод новый наверное слабо будет, а вот исходники за часок состряпать — вполне
Я вот тут почитал соседние ветки и задумался.
Господин Atilla, здесь что все серьезно уверены, что асимптотическая скорость Вашего алгоритма O(n)???
Я начинаю впадать в депрессию, так как разница между qsort и bit_sort только в том, что bit_sort не выполняет непосредственных операций сравнения между элементами массива, а использует булеву логику для сравнения с некоторым эталоном. Скорость в данном случае увеличивается только за счет реализации операций булевой логики на x86. Алгоритмическая сложность вашего вновь придуманного велосипеда (см. Яндекс — битовая сортировка) от этого НЕ МОЖЕТ ПАДАТЬ, а именно алгоритмическую сложность и показывает Big-Oh-Notation. (спасибо McSeem2)
Здравствуйте, cpp, Вы писали:
cpp>Я вот тут почитал соседние ветки и задумался. cpp>Господин Atilla, здесь что все серьезно уверены, что асимптотическая скорость Вашего алгоритма O(n)???
а Вы серьезно уверены, что асимптотическая сложность этого алгоритма O(N*log2(N)) ???
Ну сами подумайте: глубина рекурсии ограничена числом sizeof(value_type)*8 ! На каждой глубине сравнений (или битовых and'ов) может быть N или немного меньше. Итого сравнений примерно 32*N (для unsigned long'ов). У qsort'а же глубина рекурсии может доходить до N! ну а в лучшем случае — log2(N), поэтому и получается такая асимптотика. Другое дело что в большинстве случаев log2(N) < 32 но это уже к асимптотике не имеет отношения
Здравствуйте, Atilla, Вы писали:
A>Здравствуйте, cpp, Вы писали:
cpp>>Я вот тут почитал соседние ветки и задумался. cpp>>Господин Atilla, здесь что все серьезно уверены, что асимптотическая скорость Вашего алгоритма O(n)???
A>а Вы серьезно уверены, что асимптотическая сложность этого алгоритма O(N*log2(N)) ???
A>Ну сами подумайте: глубина рекурсии ограничена числом sizeof(value_type)*8 ! На каждой глубине сравнений (или битовых and'ов) может быть N или немного меньше. Итого сравнений примерно 32*N (для unsigned long'ов). У qsort'а же глубина рекурсии может доходить до N! ну а в лучшем случае — log2(N), поэтому и получается такая асимптотика. Другое дело что в большинстве случаев log2(N) < 32 но это уже к асимптотике не имеет отношения
Стандартный qsort без либ наворотов, т.е. сравнений через функцию:
void Hoar(int C[], int l, int k)
{
int i = l, j = k, X = C[(k + l) / 2], T;
while(i <= j) {
while(C[i] < X) i++;
while(X < C[j]) j--;
if(i <= j) {
T = C[i]; C[i] = C[j]; C[j] = T;
i++; j--;
}
}
if(l < j) Hoar(C, l, j);
if(i < k) Hoar(C, i, k);
}
Здравствуйте, Atilla, Вы писали:
A>Здравствуйте, cpp, Вы писали:
cpp>>Я вот тут почитал соседние ветки и задумался. cpp>>Господин Atilla, здесь что все серьезно уверены, что асимптотическая скорость Вашего алгоритма O(n)???
A>а Вы серьезно уверены, что асимптотическая сложность этого алгоритма O(N*log2(N)) ???
A>Ну сами подумайте: глубина рекурсии ограничена числом sizeof(value_type)*8 ! На каждой глубине сравнений (или битовых and'ов) может быть N или немного меньше. Итого сравнений примерно 32*N (для unsigned long'ов). У qsort'а же глубина рекурсии может доходить до N! ну а в лучшем случае — log2(N), поэтому и получается такая асимптотика. Другое дело что в большинстве случаев log2(N) < 32 но это уже к асимптотике не имеет отношения
Сразу извиняюсь, прости меня Atilla! что так резко отвечал, просто сортировки оченя долго изулали. A> Другое дело что в большинстве случаев log2(N) < 32
да, но где столько взять!
с остальным согласен...
еще раз сорри.
Здравствуйте, Atilla, Вы писали:
cpp>>Я вот тут почитал соседние ветки и задумался. cpp>>Господин Atilla, здесь что все серьезно уверены, что асимптотическая скорость Вашего алгоритма O(n)???
A>а Вы серьезно уверены, что асимптотическая сложность этого алгоритма O(N*log2(N)) ???
A>Ну сами подумайте: глубина рекурсии ограничена числом sizeof(value_type)*8 ! На каждой глубине сравнений (или битовых and'ов) может быть N или немного меньше. Итого сравнений примерно 32*N (для unsigned long'ов). У qsort'а же глубина рекурсии может доходить до N! ну а в лучшем случае — log2(N), поэтому и получается такая асимптотика. Другое дело что в большинстве случаев log2(N) < 32 но это уже к асимптотике не имеет отношения
А что такое 32?! Это -- число бит.
А что такое число бит? Это, елы-палы, log2(ULONG_MAX).
Поэтому O(N*32) >= O(N*log2(N)), если числа уникальны
Что же касается асимптотики — то есть другие сортировки, например, heapsort — которые гарантируют скорость и глубину, в отличие от qsort.
Наконец, можно модифицировать qsort (к примеру, рандомизировать массив), чтобы улучшить его характеристики.
Здравствуйте, Кодт, Вы писали:
К>А что такое 32?! Это -- число бит. К>А что такое число бит? Это, елы-палы, log2(ULONG_MAX). К>Поэтому O(N*32) >= O(N*log2(N)), если числа уникальны
К>Что же касается асимптотики — то есть другие сортировки, например, heapsort — которые гарантируют скорость и глубину, в отличие от qsort. К>Наконец, можно модифицировать qsort (к примеру, рандомизировать массив), чтобы улучшить его характеристики.
Да понимаю я все это Просто формально, сложность алгоритма O(N) и тут уж ни к чему не придерешься.
Чем еще хорош этот алгоритм, так это тем, что является примером, когда алгоритм быстрый в асимптотике на практике работает медленнее алгоритмов с более медленной асимптотикой. Обычно бытует мнение, что O(N) это лучше чем O(N*log(N)), который лучше чем O(N^2), и это утверждение легко опровергается моим "велосипедом"
Здравствуйте, cpp, Вы писали:
cpp>Сразу извиняюсь, прости меня Atilla! что так резко отвечал, просто сортировки оченя долго изулали.
Да ничего, со всеми бывает
A>> Другое дело что в большинстве случаев log2(N) < 32 cpp> cpp>да, но где столько взять!
ну на самом деле ненавороченный qsort дает в среднем глубину рекурсии 1.5*log2(N) (у heap_sort в сумме больше операций получается, чем у qsort), навороченный меньше, но все равно не log2(N). Т.е. в принципе битовая сортировка должна приближаться (и приближается) к qsort уже на миллионных массивах. А при N>=1E+9 должна уже обгонять.
Учитывая, что еще 10 лет назад массивы в 100 мегабайт были фантастикой.....
Кр-ть — с.т.
программил с большого недосыпа
как же медленнее?? По моим прикидкам, для массивов с N=250 млн. они уже должны сравняться. А для short'ов мой алгоритм выигрывает уже при размерах в несколько миллионов.
Перекуём баги на фичи!
но это уже к асимптотике не имеет отношения
