Чёрная магия программирования: сортировки и всё такое
Программированием я занимаюсь уже довольно немалое время, дело это люблю и добился на этой ниве определённых успехов. И сейчас с высоты своего ЧСВ буду страшно плеваться. :-)
Итак, сортировки. Практически в любой книге по программированию они упомянуты, и практически каждый программист в своей жизни хоть раз сортировку писал сам - пусть даже и самый примитивный «пузырёк».
Всё предельно просто: у нас есть данные и мы хотим их отсортировать...
Но прежде, чем хотя бы посмотрим в сторону сортировки, ПЛЕВОК ПЕРВЫЙ:
С++ (на котором я и пишу последнее время) старательно пинает всех к схеме представления данных через объекты (инкапсуляция и вот это вот всё), что транслируется в «массив структур», который потом и сортируется. В этом ему активно пособничает библиотека STL, которая, при всех её достоинствах, работать по-другому не умеет концептуально.
Этот подход мало того, что не единственный - он даже не лучший! В смысле, в программировании - та-дам! - НЕТ лучшего подхода «вообще», в каждом конкретном случае мы должны тщательно взвесить плюсы и минусы РАЗНЫХ подходов и выбрать правильный.
Например, во многих случаях оказывается гораздо лучше использовать отдельно массив ключей и массив полезной нагрузки - и вручную обеспечивать их консистентность, ага. Чтобы такую конструкцию засунуть в STL - необходимо писать собственные хитрые итераторы (это даже не очень сложно).
А вот теперь - сортировки! :-)
У нас есть данные и мы хотим их отсортировать - разумеется, побыстрее... И первое, что вспоминают в этом случае - это «О-большое от какой-нибудь хтони». В смысле, то самое О(н*лог(н)), например... и тут же получают палкой по голове до полного просветления от великого гуру меня. :-)
Ибо! И это - ПЛЕВОК ВТОРОЙ. Прежде, чем хвататься за сферических коней в вакууме, необходимо разобраться, что же у нас есть в действительности.
Пункт первый: нет ничего практичнее хорошей теории.
Пункт второй: разница между теорией и практикой в том, что теоретически её нет, а на практике она есть.
И вот эти вот две активно борющиеся противоположности программисту и надо диалектически объединить. Чёрная магия, как она есть. :-)
Итак, самый-самый главный вопрос: ЧТО МЫ ДЕЛАЕМ?
Если мы делаем «просто чтобы работало» - мы делаем стандартные объекты, стандартный подход «массив структур», STL и не паримся. КАК-ТО «просто работать» оно будет. Именно так и делают всякие MVP, если что.
Если же мы хотим сделать «чтобы работало быстро» - мы в жопе, господа! Потому что тогда нам надо ДУМАТЬ. Всерьёз и много.
Сколько и чего именно мы сортируем, и как именно мы это МОЖЕМ хранить и ХОТИМ хранить - потому, что «массив структур», привычный и понятный для любого насильника, существенно отличается от «структуры массивов» (чисто для справки: если вы слышали про «столбчатые СУБД» и какие они шустрые на своих задачах - вот это как раз оно, «структура массивов»).
А дальше... А дальше, внезапно, всё становится довольно просто (да-да, чёрная магия, как она есть: после того, как добыл глаз тритона, чешуйку русалки и волос с задницы гиганта - надо просто кинуть всё в котел и варить до готовности, помешивая против часовой стрелки берцовой костью 90-летней девственницы).
Если мы гарантированно сортируем некоторое малое количество объектов (до 20-30) - мы берём стандартные компаративные сети (те самые, для которых доказано, что за меньшее число сравнений отсортировать Н данных нельзя). Собственно, за исключением случаев, когда у нас какой-то совершенно забубенный ключ (или оператор сравнения для этого ключа) - нам вообще пофиг, как сортировать на таких объёмах, хоть тем самым пузырьком, ибо это будет всё равно БЫСТРО (не в относительных величинах, а в абсолютных). Но компаративные сети - быстрее всех. К слову, насколько я знаю, они и в std::sort() используются, глубоко внутри - это если кто-то вдруг сомневается.
Если мы гарантированно сортируем миллионы объектов и у нас ключ фиксированного размера (например, число с плавающей точкой) - мы берём радиксную сортировку.
Если же размер наших данных стремится попасть куда-то между этими крайностями - нам надо реализовать оба алгоритма, добавить std::sort (или вы думали, что я к STL плохо отношусь? хорошо отношусь! просто знаю про её недостатки) и провести стресс-тест и определить границы диапазонов, на которых каждый из вариантов будет быстрее.
И вот тут летит ПЛЕВОК ТРЕТИЙ! Ибо, внезапно, то самое О(хтонь) - НИЧЕГО нам не говорит о реальной скорости работы, хотя многие люди, где-то эти волшебные слова подцепившие (руки мыть надо было!), готовы с пеной у рта что-то доказывать и спорить...
Можно было бы сказать, что это оценка, как алгоритм масштабируется по размеру данных, в смысле, как увеличивается время работы с увеличением количества объектов, как бы математика за этим именно такая... Вот только, как я уже упомянул, разница между теорией и практикой в том, что нет её исключительно в теории, а на практике - примерно каждый раз.
Ибо на практике у нас не какая-то «теоретическая абстрактная машина фон Неймана», а совершенно конкретный сервер с совершенно конкретным процессором с совершенно конкретными объёмами кэшей разного уровня и совершенной конкретной оперативной памятью.
Ибо если мы делаем ВНЕШНЮЮ сортировку - то это совсем отдельная грустная песня и петь её мы не будем.
А кэш - это такая ИНТЕРЕСНАЯ материя, которая имеет очень конечный объём, и данные, которые в этом объём помещаются ведут себя СОВСЕМ не так, как те, которые не поместились.
В смысле, когда объём данных начинает подбираться к объёму кэша (и тут «структура массивов» радостно подпрыгивает и машет руками, ибо не страдает лишним ожирением паддингом) - скорость работы с этими данными начинает заметно снижаться. И именно поэтому те самые вышеупомянутые границы диапазона очень сильно привязаны не только к тому, ЧТО мы сортируем - но и на какой платформе.
Так что если вы не хотите думать, а хотите чтобы «просто работало» - да, STL, инкапсуляция и вот это вот всё...
...но диплом шамана придётся покупать в переходе между мирами чужой готовый, а не курить свой с нуля. ;-)
ПыСы: а новый редактор в ЖЖ - кака, верхние индексы, например, не умеет... :-(