Комментарии 47
А для worst-case (когда все объекты легли в одну ячейку) получите O(n * O(алгоритма внутренней сортировки)) и это не считая всей дополнительной возни с памятью.
Об этом написано в недостатках, а также упомянуто, что можно доработать алгоритм.
Не совсем так трагично, как вы описываете, потому что в этом случае объекты будут полностью или частично отсортированы, что на этапе досортировки она произойдет быстро
Ну и потом, там через всю статью протягивается мысль, что этот подход применим для частных случаев, подходящих для этого
То есть базе данных придется сначала определить, подходит ли распределение данных под этот алгоритм, а потом уже его применять :)
А ещё в базах данных чаще всего данные не подходят. Скажем, сортируете по адресам, а там условно по одному Архангельску и Якутску, и тысяча записей Москва. То есть максимально не похоже на строки стопроцентной хаотичности, используемые здесь для тестов.
Ну, вообще-то если все в одной ячейке, то будет O(1 * O(алгоритма внутренней сортировки)).
Но на практике конечно будет медленнее, чем изначально алгоритмом внутренней сортировки, т.к. надо сначала выделить много памяти, очистить ее, затем, каждое значение ранжировать, чтоб знать в какую ячейку засовывать.
Но если мы об объекте сортировки знаем больше, то, выйдя за пределы парадигмы универсальности, открываются новые горизонты для творческого полёта мысли, и становится возможным применять и линейные или специализированные алгоритмы
все правильно, именно так и надо делать, если требования к алгоритму зафиксированы и очевидно что универсальность не нужна.
Но у сортировки подсчетом есть еще один недостаток - то что ей требуется выделение памяти. При разработке библиотечных функций обычно рассуждают таким образом: если программа будет работать немного дольше, то это как-нибудь можно пережить. А вот если в системе кончится память, то тут извините, кранты. Поэтому предпочитают не выделять память почем зря, даже если приходится использовать более медленные алгоритмы.
Еще один момент: да, многопоточная сортировка может сработать быстрее. Но при этом она отнимает вычислительные ресурсы у других процессов, еще и тратясь на синхронизацию и т.п. Поэтому, если мы не говорим о каком-нибудь высоконагруженном сервере, который занимается только этим, то в первую очередь надо оптимизировать однопоточную производительность.
Там ещё БД упоминается в конце, а часто память процесса (ов) БД жёстко задана в настройках, и временно захватить кусок в несколько (десятков) ГБ не получится.
Плюс, если это не цирфы и латиница, и даже не ASCI, то сравнивать всё сложнее.
Автору - а зачем используется Dictionary? Проще и гораздо быстрее использовать int[N], заодно добавив все знаки препинания, пробел и т.д. N тут - итоговое кол-во символов.
Про параллельный вариант, действительно интересно. Если ядер 4-8, а трушных потоков 8-16, то непонятно, почему такое маленькое ускорение.
Также, почему бы не сразу создать массив списков и уже блокировать сам список, а не сторонний объект. Так хотя бы не нужен лишний массив для блокировки.
Ну и что-то подсказывает мне, что автор не первый придумал такой алгоритм..
Как раз для аналитических БД выглядит очень интересным (и исключительно для них, ибо делать большие сортировки силами операционных БД это использование оных не по назначению). Там могут быть и статистики преподсчитаны, и задача распараллелить один большой процесс на все ядра всех машин в кластере актуальна.
Другое дело, что так ли плох вариант каждым отдельным потоком посортировать свой кусочек данных за o(nlogn), после чего сделать merge отсортированных данных сначала в рамках одной машины, потом в рамках всего кластера... Да, алгоритмически менее красиво, но, зато, куда меньше синхронизаций. А, сила MPP именно в минимизации локов и синхронизаций
Дело не в мерности,а в равномерности. Пока у вас значения распределены случайным образом - вы всегда можете быстро их отсортировать таким способом. Реальные значения часто не равномерно распределены.
Всяко бывает. Если, например, в страховую приходят клиенты, то их ФИО будут весьма распределены случайно
Фамилии людей распределены весьма не равномерно.
Неравномерность и случайность - разные вещи, хотя и несколько коррелированы
> Фамилии людей распределены весьма не равномерно.
Если мы заранее знаем, что это будут фамилии, то можно учесть неравномерность распределения, разбив алфавит на
неравные интервалы верхнего уровня
т.е. корректируем "алфавит" так, чтобы распределение фамилий по новым "буквам" стало равномерным. А на этапе распихивания фамилий по "ящикам" (когда нам нужно, чтобы "номер ящика" вычислялся в одно действие) применяем обратную функцию перехода от реального алфавита к вымышленному (на котором распределение равномерное). Для ускорения процедуры эта корректирующая функция может быть максимально простой, т.к. строгая равномерность интервалов не нужна.
P.S. Спасибо автору, что напомнил про этот алгоритм! Я его применял в глубокой древности, генерируя однобайтовые ключи для сравниваемых объектов, и потом распихивая их по 256 значениям ключей. Но сейчас при столкновении с подобной задачкой - уже не факт, что вспомнил бы про такой алгоритм. Теперь не забуду ;-)
А статистику какую будем для этого брать? Фамилии форума мамочек и фамилии разнорабочих имеют радикально разное распределение.
Тут не половозрастной фактор будет существенным, а географический. Наблюдаемая частотность фамилий зависит например от субъекта РФ.
> А статистику какую будем для этого брать?
Во-первых, статистику будем брать от целевого распределения.
А во-вторых, Вы зря думаете, что статистика фамилий радикально отличается для разных социальных групп и профессий. В частности, в обоих упомянутых группах будет гораздо больше фамилий на К или С, чем на Ю или Щ. Думаю, что более точные данные легко можно найти при необходимости.
На мой непросвещенный взгляд (из самых общих соображений), гораздо более сильные различия в частотности фамилий - не профессиональные, а национальные (и, вследствие этого, региональные). Поэтому если мы хотим написать на базе сабжевого принципа более-менее универсальный алгоритм (который будет пригоден для принципиально разных наборов фамилий), то функция коррекции распределения должна вводиться отдельно как настраиваемый параметр алгоритма. Попросту говоря, она должна вычисляться с учетом частотного распределения фамилий в целевой группе.
Таким образом, получается настраиваемый алгоритм: мы один раз анализируем фактическое распределение сортируемых объектов (и это не обязательно фамилии, хотя именно для фамилий выигрыш должен быть очень хорошим), потом строим к нему обратную частотную функцию (приближающую распределение к равномерному), ну а потом можно очень быстро сортировать поступающие списки.
Еще можно время от времени проводить реанализ распределения с учетом обновляющихся данных, и уточнять обратную частотную функцию.
Второй вариант:
Если. к примеру, к нам могут поочередно поступать списки то из Китая, то из Египта, то из Исландии, то тогда заготовим несколько таких корректирующих функций (для каждого региона), а потом применяем соответствующую функцию в зависимости
от источника данных
Если регион заранее неизвестен, но их ограниченное количество, и известно, что смешанных списков почти не бывает, то можно сперва надергать немного (=n-малое) случайных фамилий из поступившего списка, и по ним с хорошей точностью определить регион за O(n-малое)
Короче говоря: вопрос про статистику поставлен правильно, но решается он гораздо проще, чем может показаться на первый взгляд. Если, конечно, нам действительно критична скорость сортировки, и мы готовы заплатить за это усложнением алгоритмов. И, главное, если задача попадает в тот довольно узкий список задач, для которых вся эта оптимизация:
а) эффективна и
б) выигрыш стоит того, чтобы этим всем заморочиться
Я правильно понимаю, что для начала нужно оооочень много памяти? Для unsigned long long int (64 bit) - ексабайт.
Нет, конечно. Буфер выбирается из тех ресурсов, которые вы можете позволить.
А вам жалко, да? Жалко? /s
>> Для unsigned long long int (64 bit) - ексабайт.
> Нет, конечно. Буфер выбирается из тех ресурсов, которые вы можете позволить.
Я что-то туплю: а за что заминусовали ответ про буфер? Вроде бы, там все верно: если у Вас 64-битный ключ, то сперва можно отсортировать по первым 16 (либо 8) битам (т.е. потребуется 65536 либо 256 ящиков=уровней). Потом внутри каждого такого "ящика" - по следующим 16/8 битам. И так далее.
Другой вопрос, что в пределе это и будет та же самая N * logN -сортировка. Ну так никто и не обещал, что предложенный алгоритм годится на все случаи жизни. Это специфическая (но иногда очень выгодная!) оптимизация для специфических случаев.
Например, если у вас 64-битный ключ, но данные по этой шкале раскиданы очень редко (подавляющая часть ключей не используется), то уже после сортировки по первым 16 битам в каждом ящике может оказаться так мало записей, что они за ничтожное время отсортируются другим алгоритмом.
А у меня в реальной жизни (геофизические временные ряды) часто встречаются 64-битные данные (на самом деле обычно 32-битгные, но сейчас это не принципиально), но подавляющая часть из этих значений лежит в середине диапазона, и только малая часть - на краях (= выбросы). А я их хочу упаковать в 16 бит без чрезмерной потери точности (выбросы надо сохранить!). Я для этого делаю log-преобразование, которое приближает распределение к равномерному, после чего трюк с равномерными уровнями прекрасно работает.
Ответить
del
На алгоритм сортировки «Индексацией Ранжирования» зарегистрированы авторские права. Но это никоим образом не ограничивает использование алгоритма любым образом. Это теперь общественное достояние.
Миллениалы они такие изобретательные... Сортировку вон изобретают 8) И зачем я читал книжки по алгоритмам, когда их можно на ходу выдумывать? Только время зря терял.
Альфа-банк, смотрите, какие самородки у вас работают!
Кто не учит физику, для того мир полон чудес ;)
Как будто мы были мудрее... Я в 1981 году изобрел сортировку слиянием. Очень изумлялся, что получилось быстрее n-квадрат. Потом конечно нашел в книжке. Но ведь чукча не читатель....
Большинство "новых прогрессивных идей" в ИТ это хорошо забытые не такие уж старые. Примерно раз в 5-8 лет большинство подходов переоткрываются под новыми именами.
Упс. Не ожидал. Убрал упоминания.
Спасибо!
// печально, но нужны объекты синхронизации. Возможно, тут надо придумать что-то более элегантное.
object[] syncarr = new object[arr.Length];
Для это есть System.Collections.Concurrent, скажем ConcurrentQueue<T>.
Но если есть память, то возможно лучше вообще без синхронизации - каждый поток может вставлять в свою версию arr, а потом при сортировке каждый поток уже работает со своим срезом всех этих массивов. Тогда потоки вообще не конкурируют.
Вообще O(m* (N/m) * log (N/m)), технически это ровно O(N * log(N)).
Bucket сортировки это хорошо, и можно даже верить в какие-то O(N), но фокус в том, что это N также определяется максимальным количеством памяти, которые мы можем выделить под вспомогательные структуры. Так что технически, это O(1) пока данные для сортировки N объектов влезают в память (потому что памяти в фон-неймановской архитектуре всегда О(1)), и не работает вообще, в ином случае. Вроде никого не обманули с оценкой сложности, но вроде бы и обманули.
Многопоточность. Многопоточность правильно делать, разбивая исходные строки по k независимым воркерам. Желательно, разбивать не тем же способом, что бакеты, а каким-нибудь простым хешом, чтобы в случае довольно однородных данных иметь примерно равную нагрузку на поток. А вот в пределах каждого воркера уже можно завести m бакетов, где просто разложить в каждый, а потом посортировать другой сортировкой. Ну и чуть чуть запариться, чтобы все эти куски слить вместе, между воркерами и бакетами. Технически тот же O(m* (N/k/m) * log (N/k/m) ) + O(N/k), но практически, будет куда быстрее. Честная многопоточность, меньшие требования к размеру непрерывной памяти под бакеты.
Крч, давно уже так везде делали.
В идеальном мире (когда памяти ооочень много) сам элемент сортировки является адресом ячейки в которой он размещен. И без коллизий. "Стремление к идеалу" мы и наблюдаем запустив на телефоне очередное "простое" приложение, когда после его работы из памяти оказываются выгруженными практически все до этого спящие приложения (это видно не по горячему их старту при обращении, а по длительному циклу запуска с полной загрузкой, авторизацией).
Зато перед этим, чтобы показать мне остаток средств на карте, передо мной проскакал табун котов, посмотрел олень из леса и взошла луна над Архызом.
На самом деле это очень сильно напоминает концепцию шардирования, когда по какому-то ключу (хешу), определяется, в какой шарде надо искать данные.
Самая большая проблема здесь, как вы сами отметили, неравномерное распределение ключа. Даже единичный случайный выброс (2,1,5,10000) ломает всю картину.
Но если мы по какой-то причине знаем распределение и можем гарантировать его ограниченность и равномерность распространения данных внутри исходного массива, то да, такой подход вполне будет работать.
нагуглил статью про этот hash sort аж с 2004-го года:
и сомневаюсь что это дата рождения этого алгоритма.
Ну а в базах такой подход давно используется, но не совсем в сортировках - в джоинах.
Hash join называется. Как раз этот же принцип. Только что не сами значения, а хэши от них, что позволяет как гибко управлять размером нужной памяти, так и работать с любыми типами данных. Кстати там двойная бакетировка используется когда нужно больше памяти чем доступно, вполне эффективно.
Далее для сравнения список сортируется встроенным сортировщиком (в .NET метод Array.Sort()), где на таком объёме работает алгоритм «Пирамидальная сортировка» (а на меньшем объёме — QuickSort)
Очень удивился. Пошерстил код, кажется как и в gcc там все-таки IntroSort -- сначала quicksort пока не превысили предел вложенности рекурсии, потом heapsort, а на блоках длины <=16 insertion sort
Самое главное, что автор получил удовольствие от своего изобретения. А подходит оно или нет это другой вопрос
Как вам выше уже сказали - это называется Bucket sort.
На практике тут получить хорошее ускорение далеко не всегда можно, ибо вам надо подобрать хорошую функцию ранжирования объектов. Для строк это особенно сложно.
Конкретно ваши сгенерированные строки примерно равномерно распределены по возможноым коротким префиксам - нескольким первым символам. Так что тут ваш прием срабатывает хорошо. В этом случае можно еще отлично работает radix sort, что тоже будет O(N).
По поводу упора в процессор при параллельной сортировке - скорее всего, не совсем так.
Несколько лет назад весьма плотно занимался реализацией радиксной сортировки, в том числе параллельной, с оптимизацией под кэш процессора и всё такое. Результат - заметный рост скорости примерно до 20 потоков и потом резкий выход на плато. Небольшое исследование показало, что упор в контроллер памяти - 6 каналов по 2 регистровых модуля, итого 24 потока доступа, из которых два-три-четыре (в зависимости от фазы Луны) отъедаются операционкой и другими процессами. При этом - вполне ощутимые накладные расходы на синхронизацию. В итоге в прод ушла однопоточная версия, которая обгоняла классику начиная примерно с 10к ключей (ключи 32/64/128 бит или даблы, нагрузка - 32, 2*32 или 3*32 целые числа, SoA, порог обгона от комбинации ключа/нагрузки почти не зависел, у меня шаг размера тестовых массивов был больше).
Сортируем сотни млн строк в разы быстрее библиотечных алгоритмов. А не замахнуться ли нам на ммм… на O(n)?