Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 25
Помимо сомнительной ценности исследования.
1) Диаграммы очень трудно читаются. Тут нужны столбцы, а не линии.
2) Где, например, сортировка Шелла?
1) Диаграммы очень трудно читаются. Тут нужны столбцы, а не линии.
2) Где, например, сортировка Шелла?
Сортировка Шелла от сортировки расчёской почти не отличается.
А вот каким образом увеличение массива до 1000 элементов приводит к увеличению памяти на 400 килобайт — действительно вопрос.
И почему быстрая сортировка, которая проиграла всем конкурентам на всех тестах, кроме одного, объявлена победителем — совершенно неясно.
Да и 500 миллисекунд на сортировку массива из 1000 элементов — что это? За такое время легко сортируется неупорядоченный массив длиной в 2-3 миллиона элементов. Или там делалась тысяча тестов?
А вот каким образом увеличение массива до 1000 элементов приводит к увеличению памяти на 400 килобайт — действительно вопрос.
И почему быстрая сортировка, которая проиграла всем конкурентам на всех тестах, кроме одного, объявлена победителем — совершенно неясно.
Да и 500 миллисекунд на сортировку массива из 1000 элементов — что это? За такое время легко сортируется неупорядоченный массив длиной в 2-3 миллиона элементов. Или там делалась тысяча тестов?
1) Диаграммы очень трудно читаются. Тут нужны столбцы, а не линии.
Ага, график зависимости времени от алгоритма, а не от размера массива — это сильных ход.
Слишком мелкие выборки для такого железа и процессора.
Возьмите миллион элементов, посмотрите что будет.
Кроме того, quicksort без проблем реализуется без рекурсии.
Возьмите миллион элементов, посмотрите что будет.
Кроме того, quicksort без проблем реализуется без рекурсии.
На самом деле, вопрос интересный. Все гонятся за ускорением для большого числа элементов или за сортировочными сетями (для аппаратной реализации) — для малых, а какой алгоритм будет лучшим для 200 элементов? Число уже достаточно большое, чтобы квадратичным алгоритмам было плохо (кроме, возможно, бинарных вставок с быстрой реализацией сдвига массива). Кто победит — расчёска, быстрая сортировка, слияние?
А чем плоха рекурсия для quicksort? Работа с аппаратным стеком может быть быстрее, чем с ручной его реализацией (а тем более, чем с библиотечной).
А чем плоха рекурсия для quicksort? Работа с аппаратным стеком может быть быстрее, чем с ручной его реализацией (а тем более, чем с библиотечной).
Рекурсия плоха тем что стекфрейм при CALL много больше чем индексов диапазона.
Кроме того — 200 элементов это настолько мало при сегодняшних кэшах процессоров, что и говорить нечего. Все упирается в итоге в какие-нить мелочи, вроде эффективности swap операции.
Сортировки — это один из простейших классов алгоритмов. Они изучены вдоль и поперек. Студенты как первые курсовые работы это делают в профильных вузах — взять десяток алгоритмов, реализовать их, оценить вычислительную сложность, построить график зависимости времени работы каждого алгоритма от размера и степени неупорядоченности массива.
Все еще от языка реализации зависит. Одно дело на ассемблере целые числа сортировать, а другое дело — на Scala списки :-)
Кроме того — 200 элементов это настолько мало при сегодняшних кэшах процессоров, что и говорить нечего. Все упирается в итоге в какие-нить мелочи, вроде эффективности swap операции.
Сортировки — это один из простейших классов алгоритмов. Они изучены вдоль и поперек. Студенты как первые курсовые работы это делают в профильных вузах — взять десяток алгоритмов, реализовать их, оценить вычислительную сложность, построить график зависимости времени работы каждого алгоритма от размера и степени неупорядоченности массива.
Все еще от языка реализации зависит. Одно дело на ассемблере целые числа сортировать, а другое дело — на Scala списки :-)
200 элементов — не так уж мало. Если вам нужно сортировать сколько-нибудь миллиардов таких массивов, когда каждый лишний такт, затраченный на сортировку, будет влиять на производительность.
«Первые курсовые в профильных вузах»? Ну и что. Если результат правильно получен и грамотно оформлен, то это результат. И кто-нибудь может им воспользоваться.
Изучены вдоль и поперёк? И каким будет практический ответ на задачу, скажем, «как быстрее всего отсортировать 200 троек 64-битных чисел (при лексикографическом порядке сравнения) на 64-битном же компьютере»? Или хотя бы направление, где его искать (кроме очевидного — напишите десяток специализированных сортировок и сравните").
Задач слишком много, чтобы считать их все решёнными. И условия, в которых они используются, постепенно меняются, так что «какие-нибудь мелочи» могут портить найденные ранее решения.
«Первые курсовые в профильных вузах»? Ну и что. Если результат правильно получен и грамотно оформлен, то это результат. И кто-нибудь может им воспользоваться.
Изучены вдоль и поперёк? И каким будет практический ответ на задачу, скажем, «как быстрее всего отсортировать 200 троек 64-битных чисел (при лексикографическом порядке сравнения) на 64-битном же компьютере»? Или хотя бы направление, где его искать (кроме очевидного — напишите десяток специализированных сортировок и сравните").
Задач слишком много, чтобы считать их все решёнными. И условия, в которых они используются, постепенно меняются, так что «какие-нибудь мелочи» могут портить найденные ранее решения.
Это все ньюансы реализации, а не самих алгоритмов сортировки.
Когда вы сортируете несколько миллиардов объектов, то причем тут внутренняя сложность этих объектов? Массивы они там или нет — это не важно.
А если есть вопрос сортировки массивов малой длины — то вопрос нужно ставить именно так — и изучать практическую реализацию в реальных условиях. И поверьте — сортировка, реализованная на C++ или на Java или на каком-нить Rust даст вам дико разные результаты — как раз потому что ваши массивы — они не сферические в вакууме а имеют тоже внутреннюю организацию.
Я же вижу в этом посте попытку выбора оптимального алгоритма, при том что не понятно вообще что автор сортирует, какие оптимизации компилятора. Как реализованы алгоритмы — может там ошибки реализации — автор думает что у него QuickSort а на деле нет.
Но очевидно, что если у него нет большой разницы на размерах порядка 10^2-10^3 то причина не в алгоритмах, а в реализации и среде исполнения.
А сами алгоритмы изучены вдоль и поперек, откройте Кнута, том третий :-)
Когда вы сортируете несколько миллиардов объектов, то причем тут внутренняя сложность этих объектов? Массивы они там или нет — это не важно.
А если есть вопрос сортировки массивов малой длины — то вопрос нужно ставить именно так — и изучать практическую реализацию в реальных условиях. И поверьте — сортировка, реализованная на C++ или на Java или на каком-нить Rust даст вам дико разные результаты — как раз потому что ваши массивы — они не сферические в вакууме а имеют тоже внутреннюю организацию.
Я же вижу в этом посте попытку выбора оптимального алгоритма, при том что не понятно вообще что автор сортирует, какие оптимизации компилятора. Как реализованы алгоритмы — может там ошибки реализации — автор думает что у него QuickSort а на деле нет.
Но очевидно, что если у него нет большой разницы на размерах порядка 10^2-10^3 то причина не в алгоритмах, а в реализации и среде исполнения.
А сами алгоритмы изучены вдоль и поперек, откройте Кнута, том третий :-)
Внутренняя сложность при том, что у объектов может быть разное время, требующееся на сравнение (относительно времени на пересылку), разные сценарии обращения к памяти при сравнении, разная нагрузка на регистры процессора в ситуации, когда объект помещается в локальную переменную… Иногда выгоднее сортировать сам массив объектов, иногда — массив индексов, ссылающихся на элементы первого массива. Иногда можно разложить операцию сравнения на части (например, сначала отсортировать строки по первому элементу — здравствуй, радикс-сортировка), иногда нельзя.
Я говорил не про сортировку массива из миллиардов объектов, а именно про сортировку большого числа коротких массивов. Например, при построении каких-нибудь дескрипторов точек изображения. И там как раз могли возникать пограничные случаи. Конечно, в первых версиях я воспользуюсь стандартной сортировкой, но если анализ покажет, что она является узким местом — то здесь бы и пригодилась курсовая работа с анализом разных ситуаций и языков…
А то, что автор вполне мог измерять время печати на консоль или вообще запуска программы — бывает и такое. У меня компилятор иногда переставлял обращение к часам с вызовом функции сортировки — получалось нулевое время при любом размере массива. Было весело :)
Я говорил не про сортировку массива из миллиардов объектов, а именно про сортировку большого числа коротких массивов. Например, при построении каких-нибудь дескрипторов точек изображения. И там как раз могли возникать пограничные случаи. Конечно, в первых версиях я воспользуюсь стандартной сортировкой, но если анализ покажет, что она является узким местом — то здесь бы и пригодилась курсовая работа с анализом разных ситуаций и языков…
А то, что автор вполне мог измерять время печати на консоль или вообще запуска программы — бывает и такое. У меня компилятор иногда переставлял обращение к часам с вызовом функции сортировки — получалось нулевое время при любом размере массива. Было весело :)
Да причем тут все это? Вы что хотите измерить — эффективность алгоритмов сортировки? Или вашего алгоритма сравнения или обмена?
Ну да, общее время выполнения зависит от операции сравнения и от операции обмена. Но это и есть «операция» в вычислительной сложности алгоритма, именно в этих «операциях» над элементарными объектам она и измеряется. И она не меняется, какими бы они не были.
Ответ в общем виде очевиден — для общей памяти — quicksort, для внешней памяти (когда данные в память одной машины не влезает) — сортировка слиянием (их тоже не один вид кстати).
Есть разные тонкие случаи вроде сортировки целых чисел подсчетом, но это уже хаки.
Каждый кто открывал хотя-бы Вирта ответ этот знает, т.к. алгоритмы сортировки и поиска — одни из простейших.
Конечно жизнь богаче абстрактных алгоритмов, но на то мы и инженеры чтобы применять правильные алгоритмы в нужных местах.
Данная же «работа» не тянет даже на реферат студента-первокурсника. Задача не описана, результаты не соответствуют теории (которая в общем-то не вызывает сомнения, все эти алгоритмы изучены вдоль и поперек, каждый студент их реализует и не по одному разу)
Ну да, общее время выполнения зависит от операции сравнения и от операции обмена. Но это и есть «операция» в вычислительной сложности алгоритма, именно в этих «операциях» над элементарными объектам она и измеряется. И она не меняется, какими бы они не были.
Ответ в общем виде очевиден — для общей памяти — quicksort, для внешней памяти (когда данные в память одной машины не влезает) — сортировка слиянием (их тоже не один вид кстати).
Есть разные тонкие случаи вроде сортировки целых чисел подсчетом, но это уже хаки.
Каждый кто открывал хотя-бы Вирта ответ этот знает, т.к. алгоритмы сортировки и поиска — одни из простейших.
Конечно жизнь богаче абстрактных алгоритмов, но на то мы и инженеры чтобы применять правильные алгоритмы в нужных местах.
Данная же «работа» не тянет даже на реферат студента-первокурсника. Задача не описана, результаты не соответствуют теории (которая в общем-то не вызывает сомнения, все эти алгоритмы изучены вдоль и поперек, каждый студент их реализует и не по одному разу)
Можно написать сортировку слиянием (без дополнительной памяти), которая будет быстрее быстрой сортировки.
Можно после этого написать быструю сортировку, которая будет быстрее их обеих.
Можно оценить долю одинаковых элементов в массиве, и написать два варианта быстрой сортировки, каждый из которых (для своего случая) будет быстрее предыдущей сортировки.
А потом перейти на компьютер с другими параметрами кэша (или просто на другой компилятор) и обнаружить, что все времена непредсказуемым образом перемешались. Причём различия могут достигать нескольких раз.
Я не хочу измерить эффективность сравнения и обмена. Я хочу, чтобы пользователь ждал результата не 10, а 5 минут (на том же железе). И если ключом к эффективности окажется сортировка — придётся экспериментировать с ней. Или искать способы обойтись вообще без неё.
Можно после этого написать быструю сортировку, которая будет быстрее их обеих.
Можно оценить долю одинаковых элементов в массиве, и написать два варианта быстрой сортировки, каждый из которых (для своего случая) будет быстрее предыдущей сортировки.
А потом перейти на компьютер с другими параметрами кэша (или просто на другой компилятор) и обнаружить, что все времена непредсказуемым образом перемешались. Причём различия могут достигать нескольких раз.
Я не хочу измерить эффективность сравнения и обмена. Я хочу, чтобы пользователь ждал результата не 10, а 5 минут (на том же железе). И если ключом к эффективности окажется сортировка — придётся экспериментировать с ней. Или искать способы обойтись вообще без неё.
В этой статье явно не хватает старого видео с демонстрацией алгоритмов сортировки:
И вот ещё одно, как раз сравнение по скорости: www.youtube.com/watch?v=ZZuD6iUe3Pc
И вот ещё одно, как раз сравнение по скорости: www.youtube.com/watch?v=ZZuD6iUe3Pc
И вот этого видео, конечно: www.youtube.com/watch?v=ywWBy6J5gz8
или не хватает этого сайта sorting.at с демонстрацией семнадацати видов сортировки
Что-то я не понял. У сортировок с O(n^2) почему-то линейно растет время выполнения.
Например, пузырек обработал 200 элементов за 116 мс, а 1000 — за 564, что почти в 5 раз больше. А должно было быть в 25 раз больше!
Вы точно все правильно сделали?
Например, пузырек обработал 200 элементов за 116 мс, а 1000 — за 564, что почти в 5 раз больше. А должно было быть в 25 раз больше!
Вы точно все правильно сделали?
Тут куча вариантов, начиная от неправильной реализации алгоритма сортировки/замеров времени выполнения, и заканчивая измерением не того, что нужно (например, вместе с сортировкой замерялась подготовка данных).
А вообще, приводить исследование скорости работы алгоритмов и не показывать ни сами алгоритмы, ни методику измерения — это как-то не очень. Писал ли автор сортировки сам, или взял готовые решения? На каком языке, как проводились измерения времени выполнения, как подготавливались тестовые данные, ну и так далее.
А вообще, приводить исследование скорости работы алгоритмов и не показывать ни сами алгоритмы, ни методику измерения — это как-то не очень. Писал ли автор сортировки сам, или взял готовые решения? На каком языке, как проводились измерения времени выполнения, как подготавливались тестовые данные, ну и так далее.
Сорцы в студию? Не верю я в то, что стандартный quicksort на 50-элементном массиве занимает 100мс. Вы, случаем, не в Debug ли запускали?
Очень странные результаты, бабл сортировка быстрее и потребляет больше памяти чем qsort, очень странно. Былобы неплохо посмотреть на код. К тому же я сильно подозреваю что тестировалось всё в дебаг режиме с stl контейнерами, пол секунды на 1000 элементов это очень долго.
Сложность алгоритма зависит от входных данных и в лучшем случае будет равняться O(n×2log2n). В худшем случае O(n^2). Существует также среднее значение, это O(n×log2n).
Эм… лучший случай работает медленнее среднего?.. ясно.
Цифры взяты с потолка.
Какая-то отписка ради инвайта.
Какая-то отписка ради инвайта.
> наиболее оптимальным алгоритмом… является быстрая сортировка
А чем «наиболее оптимальный» отличается от просто «оптимального»?
Да, и Comb sort — это просто другое название для сортировки Шелла, или там есть какие-то принципиальные отличия в алгоритме?
А чем «наиболее оптимальный» отличается от просто «оптимального»?
Да, и Comb sort — это просто другое название для сортировки Шелла, или там есть какие-то принципиальные отличия в алгоритме?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сравнение алгоритмов сортировки