Про быструю сортировку, SORT DOS и ассемблер

shufps, Indy_ и UbIvItS, спасибо Вам за подробные комментарии и ценную информацию!

Позже выложу переделанный на базе DOS-овской команды sort алгоритм сортировки массива строк различной длины (разделители строк CrLf).

 

Я не программист, но тоже свою точку зрения (практическую) имею.
Если подходить с практической стороны вопроса, то у меня сложилась в плане сортировок патовая ситуация. Пока сортируемый массив занимает десятки-сотни мегабайт (видимо массивы реально умещается в оперативке), то совершенно плевать каким из способов идет сортировка. Даже переборы в лоб, без всяких интеллектуальных изысков дают сравнительно быстрый результат. В том плане что на практике это может и будет десятикратная маржа в производительности, однако даже 100 секунд ожидания против 2 с точки зрения здравого смысла приемлем цена для того что бы пренебречь потерянным на ожидание временем.
Однако как только объем сортируемых данных превышает какой то размер (видимо по достижению оттопыркой системой всяких подкачек. буферов и пр. виртуальной памятью) как тут же сортировка уходит в такие тайминги, которые совершенно не коррелируют с размерами. Т.е. всё тупо упирается в железо, которое в сотни, если не в тысячи раз медленнее самого тупого алгоритма. Никакие фенечки в виде проекций файлов на память и прочие кучи кардинально картину не меняют.

Срезюмирую. Всё что имеет размер превышающий реальную память будет своим временем выполнения упираться в железо, а не в алгоритм.

 

Полный 30h

Проведите эксперимент. Выделите 100М регион и обращайтесь к нему, к каждой странице. Измерьте тайминг - вы удивитесь

> Всё что имеет размер превышающий реальную память

Такого понятия в нт нет. Есть рабочий набор. В произвольный момент времени физически данные могут быть, могут не быть - выгружены в хранилище(в своп), выполняться транзит - сброс рабочего набора, загрузка в своп, манипуляции с системной базой данных pfn etc.

 

Полный 30h, Полный 30h,

Экспериментов проведено в избытке. Вплоть до того, что в ущерб скорости доставлялся код для фиксации производительности. Картина всегда одна и та же. Сначала алгоритм самолётом чешет по массиву. Но лишь до тех пор, пока т.н. выделенный (неважно как) регион на самом деле находится в оперативной памяти. Но стоит ему упереться в физические размеры системы, как скорость сортировки падает к плинтусу и начинает на прямую зависеть от возможностей настроения винчестера. Если вы с вашим регионом на такое не попадали, то думаю лишь потому, что он физически не превышал объем выделенной под него реальной оперативной памяти. Чудес на свете не бывает. Условно ОГРОМНЫЙ массив рано или поздно упрется в скорость железа. Разумеется если он не на столько неэффективен, что по своей скорости не может догнать винт.

 

Полный 30h

Есчо раз говорю, реальной памяти нет, она виртуальная.

> скорость сортировки падает к плинтусу и начинает на прямую зависеть от возможностей настроения винчестера.

Свопается буфер, что тут не ясно.

 

Развинтите свой системный блок и я вас уверяю, вы обязательно найдете там реальную память. Более того, она даже выделяется вашим программам. И можно называть всё это различными сленговыми терминами, которыми я не очень владею, но факт остаётся фактом, по большому счёту на уровне железа компьютер имеет всего два вида вида памяти - оперативную и жесткий диск. В том виде что вы её видите, буфер, куча, файл и т.п. абстракция. Всё что я хотел сказать в этой теме, что алгоритм не всегда определяет скорость. Размер имеет значение(с)

 

Полный 30h

Код из под оси с железом не работает(оно абстрагировано/виртуализируется). Курите матчасть

 

Вы наверное основной упор как раз таки на курение делаете. Поэтому как некурящий могу посоветовать поменьше увлекаться абстракциями. Ось это код, который работает параллельно-последовательно (в зависимости от числа ядер) с вашим кодом. Некоторым образом диспетчеризуя ваш код. И в тот момент когда работает ваш код он работает на РЕАЛЬНОМ железе. И вот то. какое железо он вам в данный момент может предоставить и играет немаловажную роль в скорости выполнения операций. Если не верите мне, то обратите внимание на такой раздел системы как "Производительность" И из чего она складывается. возможно для вас это будет открытием.

 

глупый/неэффективный алгоритм сожрёт любое железо. но с другой стороны ==>> оптимизация тоже имеет свой потолок. Вот и вся недолга.. Давай простой расчёт проведём -- дано:

1. массив чисел == 1000 000 000 элементов
2. используются две сортировки: оптимальная по времени O(nlogn) и тупая O(n^2) {n == число элементов}.
3. среднее время на сортировку одного элемента 12нс.
4. в обоих случаях свопа не требуется.
====================================
Вот и считай сколько времени уйдёт на тупую. Ещё один момент: куча сортировок, теоретически оптимальных, на практике непригодны, ибо их нельзя распараллелить и/иль у них бешеный оверхед по памяти. Например, пирамидальная жутко лагает. QSort -- почти идеал: она сравнительно проста, её можно затачивать под железку/размер массива/размер элемента. Короче, шустрей QSort мб токЪ QSort

 

UbIvItS, немного разверну свою мысль в предложенном тобой направлении. Глупый/неэффективный алгоритм есть понятие тоже абстрактное если рассматривать задачу не только с математической точки зрения, но и железа. Пока ситуация развивается в оперативной памяти, быстрым будет алгоритм с минимальным числом перемещением элементов. И это очевидно. Но как только дело доходит до работы с магнитным носителем так эта стройная математика начинает разбиваться о тупую геометрию магнитного носителя. И если для оперативной памяти перенос (условно) из первой ячейки одинаков как во вторую, так и тысячную. То для магнитного носителя это спонтанные переносы головки требуют не иллюзорного по меркам процессора времени простоя. и тут уже идут в ход алгоритмы менее эффективные математически, но наиболее приспособленные под специфику оборудования.
косвенным подтверждением моим мыслям могу привести цитату из вики по поводу всё того же QuickSort

Конечно винчестер не магнитная лента, но полностью от её недостатков избавиться не удалось.

 

Полный 30h
Товарищ, алгосов (абстрагированных от железки) не существует.. вся муйня современной школы прогеров в том и заключается, что их учат "элегантным кодам" ==>> вот подай им портабельность и абстрагирование. увидят в коде оператор goto и сразу начинают биться в паранойе ))

 

Напрасно ты так думаешь. Тот же алгоритм сортировки, в классическом виде, как раз таки преподносится как математическая модель не опирающаяся на специфику железа. Потому как хлопоты железного плана берут на себя драйвера. Которые в свою очередь так же могут быть слепы, так как в свою упираются в микропрограммы конечных устройств. За всё приходится платить, в том числе и за унификацию.
И да. Напомню, что на смену дороговизне машинного времени пришла дороговизна (относительная) времени программиста. поэтому зачастую при выборе оптимизировать алгоритм/нарастить мощность упор делается на второе.

З.Ы. кажется я своим вбросом увёл спор о насущном в досужий # на тему глобализации. Поэтому возьму на себя смелость первым свалить из темы по тихому. Разумеется не прощаясь окончательно
Как дети со своей предмодерацией, ейбогу.

 

есть такая поговорка: хорошее словно невидимка, а плохое хорошо запоминается ))

 

Ложка, каша, рот. На докритичных объемах, не превышающих объем оперативной памяти выделенной осью в натуре под задачу, рулит алгоритм с минимальным числом перестановок элементов неважно на какие расстояния (адреса). Однако если размер массива(ов) сильно превышает размер памяти и роль оперативной памяти берет на себя диск, то алгоритм упомянутый выше (минимальное число сдвижек) не обязательно оптимален. В силу специфики железа, в первую очередь механической головки и даже энергосберегающих, ухоберегущих, ресурсосберегающих фенечек на прямую с алгоритмом не связанных. Так надеюсь понятнее я свою мысль изложил.

Сильно удивитесь, но кажется я совершенно случайно, (только что) одного такого встретил.

 

TermoSINteZ, меня ничего не мучает и не путает. Чего и вам желаю.
Что до ваших советов по поводу проектированию решений, то с удовольствием им воспользуюсь когда предоставится такая возможность. Однако существует определенный круг вопросов где конечный результат, до начала выполнения расчётов, не очевиден. Всех благ.

 

Полный 30h
Товарищ, ты рассматриваешь две разные машины:

1. цпу + озу.
2. цпу + озу + диск(и).
==========================
№2 характерен для БД и там тоже вполне себе имеют место быть оптимальные решение с условием кол-ва параллельных потоков и используемой фс.

 

в экспериментах -- ДА. а для конечного решения такое НЕДОПУСТИМО в штатном режиме работы.

 

Разумеется. Забыл предупредить. Это и был эксперимент. Конечный результат так и не достигнут. Массив не только сортируется но и модифицируется по результатам сортировки. Теоретически и практически на определенных проходах сокращается. Но растёт. Собственно ради этого эксперимента я и сел за ассемблер. Изначально задача мне показалась решаемой в экселе. Всё что я здесь написал касается тех, кто как и я полагаясь на популярную литературу, принял за чистную монету утверждение о прекрасных перспективах открываемых виртуальным адресным пространством. Виртуально оно лишь до той поры, пока не наступает так сказать преломление сред.
Всё, я спать. Всем спасибо за приятное общение.