Для ЯПматематиков пост: визуализация работы 19 алгоритмов сортировки

 [ Версия для печати ]
Добавить в Telegram Добавить в Twitter Добавить в Вконтакте Добавить в Одноклассники
Страницы: (3) 1 2 [3]   К последнему непрочитанному [ ОТВЕТИТЬ ] [ НОВАЯ ТЕМА ]
48576719297
13.04.2020 - 22:24
0
Статус: Offline


Юморист

Регистрация: 1.03.20
Сообщений: 409
Звук похож на zx spectrum

Размещено через приложение ЯПлакалъ
 
[^]
Tipakrut
13.04.2020 - 22:28
1
Статус: Offline


Шутник

Регистрация: 19.01.15
Сообщений: 57
Цитата (pupch @ 13.04.2020 - 15:25)
это ж разве визуализация? учитесь у цыган

Неплохо, ещё в курсе cs50 неплохо объясняют.

Размещено через приложение ЯПлакалъ
 
[^]
АйфонФеррари
13.04.2020 - 22:40
2
Статус: Offline


Ярила

Регистрация: 27.04.16
Сообщений: 2793
Сижу себе, никого не трогаю, примус починяю массивы сортирую
 
[^]
Стамп
13.04.2020 - 23:21
0
Статус: Online


а ты не ной

Регистрация: 7.02.13
Сообщений: 16130
Цитата (b0bo4ka @ 13.04.2020 - 15:05)
Волшебно!
Про большую часть методов даже не слышал.

о да !! доставило
 
[^]
plotnick
13.04.2020 - 23:41
0
Статус: Offline


Ярила

Регистрация: 14.03.12
Сообщений: 2884
Да прикольно посмотреть, но нужно внимательно за таймингом следить, некоторая визуализация выглядит быстрее прочих, а по таймингу намного медленнее. Например gravity sort.

Размещено через приложение ЯПлакалъ
 
[^]
Сугроб61
13.04.2020 - 23:49
0
Статус: Offline


Ярила

Регистрация: 6.02.19
Сообщений: 1029
Рамштайн? шото новое?

Размещено через приложение ЯПлакалъ
 
[^]
Готтфрид
14.04.2020 - 00:10
0
Статус: Offline


Юморист

Регистрация: 6.11.16
Сообщений: 550
Ну дык квиксторт на то и квик
 
[^]
Юрковский
14.04.2020 - 08:45
-1
Статус: Offline


Юморист

Регистрация: 7.03.09
Сообщений: 494
Цитата (riv1329 @ 13.04.2020 - 18:02)
Цитата (Eymerich @ 13.04.2020 - 15:16)
Круто. Сколько плохих методов оказывается есть.

зы а, забыл. Я так венду писал (par9)


В защиту "пузырька".

Не все так просто. Скорость каждого алгоритма очень сильно зависит от объема и типа данных. У умных алгоритмов делается меньше шагов, чем у тупого пузырька в пересчете на единицу данных, но сам шаг длиннее.

По этому тупенький пузырек на небольшой выборке может обогнать почти любой алгоритм. Но его скорость падает пропорционально квадрату количества данных. Каким бы быстрым не был он, найдется такое число, после которого он отстанет от более прогрессивных алгоритмов.

И чем больше объем данных, тем оправданее усложнение алгоритма, с целью снизить количество шагов.

Но дело не только в скорости. Бывает что ситуация накладывает ограничения на возможность использования дополнительной памяти. Для пузырька нужна лишь одна лишняя ячейка. Рекурсивные алгоритмы потребляют память на стек тем больше, чем больше выборка (но не пропорционально больше). Для некоторых алгоритмов вообще заранее невозможно подсчитать необходимое количество памяти, что согласитесь, "не айс": программа может "вылететь" из-за нехватки доступной памяти раньше чем закончит сортировку.

Не поверишь, но после института "пузырёк" не пригодился в жизни ни разу. На небольших массивах даже вульгарный полный перебор работает быстрее. На больших или динамических массивах - "дерево" наше всё. Квик-сорт хорош, без всякого сомнения, но в тени его не запустишь, приходится отрубать запись в массив.
 
[^]
ssmsska
14.04.2020 - 09:12
1
Статус: Offline


Балагур

Регистрация: 1.12.15
Сообщений: 933
Странное видео. Массив разбивался то на 100 частей то на 650, то еще на сколько-то, постоянно разное количество. То скорость была в реальном времени, то в перемотке. При чем нигде это не акцентировалось. И зачем было сделано категорически не понятно.
Сиди с лупой разбирайся где сколько фрагментов и сколько времени было затрачено на массив, потом доставай калькулятор и выводи коэффициент скорости.

Это не для математиков, а для гуманитариев ИМХО. Картинка красивая просто.

Это сообщение отредактировал ssmsska - 14.04.2020 - 09:12
 
[^]
gods02
14.04.2020 - 11:17
0
Статус: Offline


Ярила

Регистрация: 28.08.18
Сообщений: 3268
Цитата (artivenom @ 13.04.2020 - 22:07)
Цитата (gods02 @ 13.04.2020 - 19:00)
Цитата (Уфимский @ 13.04.2020 - 16:22)
Цитата (denisg2 @ 13.04.2020 - 15:49)
Обычно доверяю сортировку SQL серверу. "order by" решает.

Ну-ну... Давай из жителей Москвы, например, сделай сортировку по ИНН. Просто интересно: насколько сервер зависнет... shum_lol.gif

А сервер так и работает.
Фактически, он создает временный индекс по полю "ИНН", сортирует его, и, затем, на основании этого индекса расставляет результаты.
Так что специфический подбор метода сортировки для конкретного массива вряд ли будет более эффективней, чем стандартный метод сервера.
Ну, и откровенно говоря, 20 млн. записей - не такая уж большая база cool.gif
думаю, на современном сервере результат будет в районе 1 секунды.

Ну хз на счёт именно БД, всё же там реализовано дерево, а не хэш, в том числе и в индексе. Возможно там есть спец. оптимизация для чисел. Но по общему правилу сортировка дерева будет всегда сложнее и медленнее, чем вставить записи в 1 проход в массив по очереди. Смысл именно в том, что индекс элемента массива = значению ИНН. 1 обход побитого массива и всё отсортировано. Быстрее варианта не может существовать просто. даже с индексом.

там свой оптимизатор работает.
В данном конкретном случае, нужно смотреть план выполнения и там будет описано, какой индекс строится, почем и какого типа.
Кстати, инн , возможно, будет сортироваться как строковая переменная длиной 12 символов, с ведущими " "
 
[^]
ichthyandr
14.04.2020 - 11:31
0
Статус: Offline


водоплавающий

Регистрация: 20.02.15
Сообщений: 1857
Цитата (Уфимский @ 13.04.2020 - 15:20)
Сортировка пузырьком / Bubble sort
...

там еще такое было

Сортировка «Американский флаг» :: American Flag Sort

тыц
 
[^]
ichthyandr
14.04.2020 - 11:33
1
Статус: Offline


водоплавающий

Регистрация: 20.02.15
Сообщений: 1857
Цитата (Юрковский @ 14.04.2020 - 08:45)
Цитата (riv1329 @ 13.04.2020 - 18:02)
Цитата (Eymerich @ 13.04.2020 - 15:16)
Круто. Сколько плохих методов оказывается есть.

зы а, забыл. Я так венду писал (par9)


В защиту "пузырька".

Не все так просто. Скорость каждого алгоритма очень сильно зависит от объема и типа данных. У умных алгоритмов делается меньше шагов, чем у тупого пузырька в пересчете на единицу данных, но сам шаг длиннее.

По этому тупенький пузырек на небольшой выборке может обогнать почти любой алгоритм. Но его скорость падает пропорционально квадрату количества данных. Каким бы быстрым не был он, найдется такое число, после которого он отстанет от более прогрессивных алгоритмов.

И чем больше объем данных, тем оправданее усложнение алгоритма, с целью снизить количество шагов.

Но дело не только в скорости. Бывает что ситуация накладывает ограничения на возможность использования дополнительной памяти. Для пузырька нужна лишь одна лишняя ячейка. Рекурсивные алгоритмы потребляют память на стек тем больше, чем больше выборка (но не пропорционально больше). Для некоторых алгоритмов вообще заранее невозможно подсчитать необходимое количество памяти, что согласитесь, "не айс": программа может "вылететь" из-за нехватки доступной памяти раньше чем закончит сортировку.

Не поверишь, но после института "пузырёк" не пригодился в жизни ни разу. На небольших массивах даже вульгарный полный перебор работает быстрее. На больших или динамических массивах - "дерево" наше всё. Квик-сорт хорош, без всякого сомнения, но в тени его не запустишь, приходится отрубать запись в массив.

вы путаете две задачи:
1. Задача сортировки
2. Задача поиска

Поиск производится или по сортированному массиву или по дереву. На видео "древесных" структур нет

Это сообщение отредактировал ichthyandr - 14.04.2020 - 11:35
 
[^]
ichthyandr
14.04.2020 - 11:50
0
Статус: Offline


водоплавающий

Регистрация: 20.02.15
Сообщений: 1857
Цитата (Zeugl1271 @ 13.04.2020 - 21:45)
std::sort(std::begin(),std::end(),[](const &){...}); и ебись оно конём!

ооо, вижу лямду тут! pray.gif
 
[^]
sobor
14.04.2020 - 11:52
-1
Статус: Offline


Ярила

Регистрация: 23.05.10
Сообщений: 8320
Только что дошло, что сортировка произошла от слова сортир
 
[^]
OTMOPO3OK
14.04.2020 - 15:11
0
Статус: Offline


Ветеран Япа

Регистрация: 11.10.04
Сообщений: 20952
Надо было ещё статью скопировать


https://habr.com/ru/post/335920/
 
[^]
Юрковский
14.04.2020 - 20:14
0
Статус: Offline


Юморист

Регистрация: 7.03.09
Сообщений: 494
Цитата (ichthyandr @ 14.04.2020 - 11:33)
Цитата (Юрковский @ 14.04.2020 - 08:45)
Цитата (riv1329 @ 13.04.2020 - 18:02)
Цитата (Eymerich @ 13.04.2020 - 15:16)
Круто. Сколько плохих методов оказывается есть.

зы а, забыл. Я так венду писал (par9)


В защиту "пузырька".

Не все так просто. Скорость каждого алгоритма очень сильно зависит от объема и типа данных. У умных алгоритмов делается меньше шагов, чем у тупого пузырька в пересчете на единицу данных, но сам шаг длиннее.

По этому тупенький пузырек на небольшой выборке может обогнать почти любой алгоритм. Но его скорость падает пропорционально квадрату количества данных. Каким бы быстрым не был он, найдется такое число, после которого он отстанет от более прогрессивных алгоритмов.

И чем больше объем данных, тем оправданее усложнение алгоритма, с целью снизить количество шагов.

Но дело не только в скорости. Бывает что ситуация накладывает ограничения на возможность использования дополнительной памяти. Для пузырька нужна лишь одна лишняя ячейка. Рекурсивные алгоритмы потребляют память на стек тем больше, чем больше выборка (но не пропорционально больше). Для некоторых алгоритмов вообще заранее невозможно подсчитать необходимое количество памяти, что согласитесь, "не айс": программа может "вылететь" из-за нехватки доступной памяти раньше чем закончит сортировку.

Не поверишь, но после института "пузырёк" не пригодился в жизни ни разу. На небольших массивах даже вульгарный полный перебор работает быстрее. На больших или динамических массивах - "дерево" наше всё. Квик-сорт хорош, без всякого сомнения, но в тени его не запустишь, приходится отрубать запись в массив.

вы путаете две задачи:
1. Задача сортировки
2. Задача поиска

Поиск производится или по сортированному массиву или по дереву. На видео "древесных" структур нет

Никак не пойму, за что мне влепили шпалу. Нет, я ничего не путаю. Есть такой метод сортировки массива, метод "дерева". При этом создаётся полная новая версия массива, и память, да, кушается прилично. Преимущества этого метода в том, что отключать режим записи в исходный массив нужно только в самый последний момент перед компоновкой нового.

Дерево данных от массива данных я таки отличаю с 1988-го года, честно. Не надо уж всех присутствующих за дурачков то считать, я думал, в этой теме собралось приличное общество ))
 
[^]
Понравился пост? Еще больше интересного в Телеграм-канале ЯПлакалъ!
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии. Авторизуйтесь, пожалуйста, или зарегистрируйтесь, если не зарегистрированы.
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) Просмотры темы: 12598
0 Пользователей:
Страницы: (3) 1 2 [3]  [ ОТВЕТИТЬ ] [ НОВАЯ ТЕМА ]


 
 



Активные темы






Наверх