Сортировки с анимацией

Тема в разделе "WASM.X64", создана пользователем Mikl___, 24 дек 2022.

  1. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    572
    Вот моя версия.
    Добавлено 11 типов сортировок, меняется кнопками Q и A
     

    Вложения:

    • DemoSort.zip
      Размер файла:
      11,3 КБ
      Просмотров:
      87
  2. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.746
    Intro,
    спасибо огромное! :good3:
    Добавил MergeSort написанную целиком и полностью на базе вашей программы
     
  3. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    572
    Думаю ещё надо добавить визуализацию сравнения, ну чтобы столбики подкрашивала рамкой. А то некоторые алгоритмы вводят в заблуждения, думаешь офигенно быстро, а на деле очень много операций сравнения, а видь операция чтения тоже вызывает задержки, ещё хорошо визуально наблюдать как именно эти сравнения происходят, чтобы лучше понимать проблемы. Например, если много сравнений по случайным разбросанным местам, значит будут проблемы с кешем, из-за постоянным подгрузки данных в блоки кеша.
     
  4. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.746
    Intro,
    я думаю, что сначала нужно выложить основные сортировки TimSort, Tree Sort, Bucket Sort, Radix Sort (MSD и LSD), Cubesort и т.д., а дальше (или параллельно) подумаем об оформлении сравнений и обменов, и работе с внешней памятью :)
     
  5. alex_dz

    alex_dz Active Member

    Публикаций:
    0
    Регистрация:
    26 июл 2006
    Сообщения:
    381
    красивая работа, спасибо
    а можно еще кнопочки (больше-меньше) для скорости визуализации?
     
  6. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    572
    Кстати, код можно брать на хабре, вот здесь например.
    https://habr.com/ru/post/335920/
    Я там мердж взял, хотя у Mikl___, некоторые сортировки получше, например CombSort, я это улучшил, но там требования SSE, значит не слабей Athlon XP или Pentium III. Простая, но быстрая, это я к тому, что демка совсем не показывает реальное быстродействия, т.к не визуализирует сравнения.
    Я сейчас делаю тестовые демки на быстродействие.
    PS
    В общем, ещё розета есть. Там и на асме, и даже на МК-61 что-то видел.
    https://rosettacode.org/wiki/Rosetta_Code
     
  7. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    572
    Столкнулся с странной работай функции FillRect, она почему-то не отрисовала столбик, если я выводил только два, ну отрисовала, но иногда и не рисовала, а иногда и совсем не рисовала. Но если задать отрисовку всех столбиков сразу, а не по флагу, то проблем с отрисовкой нет! В общем, я отказался от флагов, эээ типа оптимизация такая, и сейчас, всё время обновляются столбики, и никаких мерцаний нет. Ах да, ещё одна оптимизация, ранее сначала заливала весь столбик чёрным цветом(цвет фона), то сейчас только половину, ну ту часть что не нужна. В общем, теперь и не мерцает, и нет "грязных" столбиков. А ранее они были, что вводило в заблуждения. Всё таки FillRect очень быстрая функция, успевает быстро залить, прежде чем экран обновится.
     
    Mikl___ нравится это.
  8. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    572
    Где-то читал что разработчики AMD видеокарт, удалили аппаратные старые функции типа BitBlt и другие, теперь эти функции на уровне драйверов, занимается директХ(или OpenGL?), возможно именно из-за этого проблемы. Вот не помню где прочитал эту новость, но новость была лет 15 назад, или около того. На старом ноуте установлена radeon 5270 и там тоже такие проблемы.
    Я конечно это обошёл, но это не правильно, когда формально код правильный, но не работает, и приходится думать как это обойти. Так что AMD видеокарты менее стабильные чем от нвидеа, вот 6500ХТ при просмотре ютуба даёт сбои, хотя в играх в два раза лучше 1050ti, но 1050 при просмотре видео не разу не дало сбой, и там есть анкодер(аппаратная запись видео). В общем, при просмотре демки на амд В/К могут быть проблемы, на NVIDIO таких проблем быть не должно, как и на ооочень старых В/К от AMD(больше 15-20 лет).
    ЗЫ
    Не сразу заметил что тема в разделе х64, но переделывать код на х64 не планирую!!!
     
    Последнее редактирование: 30 дек 2022
  9. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    572
    В общем, добавил подсветку сравнения и задержку. Сразу стало видно быстрые и не быстрые сортировки, в некоторых перемещении мало, но много сравнений(на старых версиях это не видно), из-за этого зависимость практически квадратичная, ну да, сравнения протекают быстрей перемещений, особенно если сравнивается с опорным числом, но всё равно, это квадрат в почти 100% случаев.
    ЗЫ
    Добавил вывод сравнений и перемещений, в версии Mikl___ выводила ерунду не понятную.
    ЗЫЫ
    И ещё версия HeapSort странная, ошибка была, выход из-за диапазона, надо переделать.
     

    Вложения:

    alex_dz и Mikl___ нравится это.
  10. alex_dz

    alex_dz Active Member

    Публикаций:
    0
    Регистрация:
    26 июл 2006
    Сообщения:
    381
    вопрос по поводу min-max для сна

    MAX_SLEEP = 5
    MIN_SLEEP = 500
    STEP_SLEEP = 5

    почему так?
    как про меня макс должен стоять 500 (мсек) и мин - 5 мсек?
    и еще -можно 1 мсек а то 5 все еще медленно как для глаза

    спс
     
  11. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.746

    Поразрядная сортировка (Most Significant Digit)

    Radix MSD Sort.gif
    Поразрядная сортировка (radix MSD sort) — алгоритм сортировки, который выполняется за линейное время относится к классу «сортировок распределением». После очередного распределения рекурсивно сортируются подмассивы элементов, сгруппированные по значению старшего разряда.
    Сравнение производится поразрядно: сначала сравниваются значения самого старшего разряда, и элементы массива по результатам этого сравнения разделяют массив пополам, затем сравниваются значения следующего разряда в получившихся половинках массива и элементы либо упорядочиваются по результатам сравнения значений этого разряда внутри образованных на предыдущем проходе половин массива, либо переупорядочиваются в целом, но сохраняя относительный порядок, достигнутый при предыдущей сортировке. Затем продолжаем сравнения и перемещения для следующего разряда, и так пока не дойдем до самого младшего разряда.

    В аттаче asm-/rc-/exe-файлы и курсор
     

    Вложения:

    • RadixSort.zip
      Размер файла:
      9,3 КБ
      Просмотров:
      82
    Alikberov нравится это.
  12. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    572
    Исправил некоторые ошибки, скорость можно регулировать более плавно, но минимальное время 1 мс просто не срабатывает. Ещё не понял как загрузить иконку, чтобы на форме была. Так же заменил код HeapSort на код с розеты, у Mikl___ какая-то ошибка, вроде работает, но есть переполнение, ошибки не вызывает, но это не правильно.
    ЗЫ
    Ещё добавил радикс-сортир.
     

    Вложения:

  13. GRAFik

    GRAFik Active Member

    Публикаций:
    0
    Регистрация:
    14 мар 2020
    Сообщения:
    352
    Mikl___, эти все сортировки вы потом наверное реализуете в виде какой-нибудь библиотеки, для каких-нибудь математических расчетов? Или это не особо важно, сортировки это или какие-нибудь апроксимации, полиномы и т.д. и т.п? Я почему интересуюсь, может вам перейти на что-то другое? Например на интерполяции. За это вам Thetrik, Rel и я были бы по-моему, благодарны. Ну я-то уж точно.
     
  14. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    572
    GRAFik, чаво? Уже давно всё реализовано. Все эти ваши фреймворки. Мне тема зашла что можно визуально отлаживать алгоритм сортировки. А так, квиксорт во всех фреймворках, ну насколько знаю.
     
    Mikl___ нравится это.
  15. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.746

    Блинная сортировка

    Блинная сортировка (Pancake Sort) ― относится к классу «сортировок выбором». Алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае за [math]O(n^{2})[/math]
    Ищем максимальный элемент. Переворачиваем цепочку элементов от левого края до максимума ― в результате максимум оказывается на левом крае. Затем переворачиваем весь неотсортированный подмассив, в результате чего максимум попадает на своё место. Эти действия повторяем с оставшейся неотсортированной частью массива.

    В аттаче asm-/rc-/exe-файлы и курсор


    Intro, спасибо огромное! :good3: "блинная сортировка" написана целиком и полностью на базе вашей программы
     

    Вложения:

    • PancakeSort.zip
      Размер файла:
      9,5 КБ
      Просмотров:
      82
  16. asmlamo

    asmlamo Well-Known Member

    Публикаций:
    0
    Регистрация:
    18 май 2004
    Сообщения:
    1.731
    Mikl___, Отлично. А как можно ускорить ? А то полная сортировка несколько минут идет !
    --- Сообщение объединено, 3 янв 2023 ---
    Неплохо бы визуализацию сети Фейстеля ...как там битики переставляются.
     
  17. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.746
    asmlamo,
    у вас всегда есть выбор:
    1. изменить g_iDelay с 40ms на 4ms и перекомпилировать,
    2. если нет желания компилировать, можно через hiew32, найти адрес параметра , который передается Sleep и изменить его содержимое
    3. если нет желания работать с hiew32, тогда взять ехе-файл из аттача :)
    Надо долго думать, :scratch_one-s_head: мне бы примерчик работающий, тогда было бы быстрее :popcorm1:
     

    Вложения:

    • PancakeSort.zip
      Размер файла:
      9,5 КБ
      Просмотров:
      77
  18. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    572
    asmlamo, у меня можно менять задержку клавишами +/-. Вот только задержка менее 5 мс не работает. Возможно если код переписать линукс, то там это заработает, но в винде 10 такая задержка не работает. Напомню Sleep отпускает поток, ну засыпает т.е., и там есть свои ограничения, возможно есть какие-то хаки, чтобы заставить ОС давать точную задержку в районе 1-5 мс и меньше.
     
    Mikl___ нравится это.
  19. GRAFik

    GRAFik Active Member

    Публикаций:
    0
    Регистрация:
    14 мар 2020
    Сообщения:
    352
    Молодец, Intro, так его гада - будет знать в следующий раз как лезть со своими вопросами куда не надо. :)

    Так алгоритм интерполяции можно тоже визуально отлаживать - будет еще красивее. :)
     
  20. alex_dz

    alex_dz Active Member

    Публикаций:
    0
    Регистрация:
    26 июл 2006
    Сообщения:
    381
    круть! спасибо за труд, теперь на 1 мс то что доктор прописал :)
    еще мааленькое пожелание - добавить кнопки + и - с цифрового блока клавиатуры (сейчас только с основной работают)
    2) интересует почему в кодесе иногда Sleep() идет сам по себе, а иногда в бутерброде вида

    push ecx
    push edx
    Sleep(g_iDelayPause) ;чтобы не нагружало
    pop edx
    pop ecx