Posted 26 February 2017 - 23:03 PM
Недавно услышал про уникальный способ сортировки, который смогут оценить местные программисты. Он был изобретен на 4chan и работает следующим образом. По количеству элементов в массиве n запускается параллельно n потоков, каждый из которых печатает соответствующий элемент массива c временной задержкой равной значению элемента массива.
Edited by wings, 26 February 2017 - 23:24 PM.
Posted 27 February 2017 - 7:26 AM
Огонь!)
Ну и да, каждому алгоритму своя область применения))
С нами сила Алхазашвили!
Posted 27 February 2017 - 9:14 AM
Posted 27 February 2017 - 9:26 AM
Не, мне кажется, это забавная штука "чисто для себя, чтоб поржать".
Использовать ее, наверное, можно в каком-нибудь очень уж специфическом случае...
Но, учитывая потенциальное время ее исполнение для массивов с большими числами, выгоднее использовать тот же quick-sort за O(n*log n).
С нами сила Алхазашвили!
Posted 27 February 2017 - 9:38 AM
Сонь, а ты про область применения что-нибудь понимаешь?
Смекалкой автор порадовал, но оно хоть куда-нибудь будет адекватно смотреться? Или тебе тоже никакие подходящие задачки в голову не приходят?
Тут еще проблема в реальном применении связана с тем как thread management реализован. На него не стоит полагаться в том что все потоки по времени будут параллельны
Posted 27 February 2017 - 9:51 AM
Вообще-то сложность самого этого алгоритма константа. Так что теоретически, если данные отвечают определенным условиям, оно может быть эффективнее qsort. Проверить, что все данные удовлетворяют этому условию -- N. Так что в итоге получается N + C. Все вполне правдоподобно :-)
Конечно, надо учесть время переключения потоков, задержку на старт потока, количество потоков, при которых система не деградирует и т.п. Но зная архитектуру, можно это все заложить в "проверку того, что данные допускают такую сортировку". Или построить отображение исходного набора в "подходящий". И для какого-то класса данных получится сортировка, более эффективная, чем qsort. Теоретически :-)
Тут скорее интересно то, что использован принципиально иной подход к сортировке. Здесь нет операций сравнения и перестановки в принципе, как таковых. Мне это решение напомнило, как оптимальный путь водой искали. Вероятно, где-то среди таких вот "решений в другой плоскости" можно найти и решение NP-полных задач :-)
С нами сила Алхазашвили!
Posted 27 February 2017 - 10:08 AM
Ну все же согласись, что тут время зависит от данных, поэтому для большого массива с маленькими числами -да, имеет смысл, а для массива с огромными -нет. А что делать, кстати, с массивом типа [1, 1, 1, 1, ......1, 5]. Как обрабатывается одновременное желание потоков писать в один файл/массив -- системными средствами или как-то еще? Если системными, то не факт, что будет соблюдаться правильная очередь (насколько я помню).
С нами сила Алхазашвили!
Posted 27 February 2017 - 10:27 AM
Так я и говорю для определенного класса данных. Огромные можно нормализовать до различимого шага. А вообще, сложность-то не меняется. Константа. Да, очень большая, но не N*log(N) же все равно :-)
А про "кстати" -- да, стабильность сортировки под вопросом. Ну, будет нестабильная. Тоже вполне применимо.
Операционная ситема, да, разруливает одновременность достпуа к разделяемым ресурсам с точностью до размеров буфера. Там есть разного рода артефакты, но это отдельный разговор.
С нами сила Алхазашвили!
Posted 27 February 2017 - 22:26 PM
Posted 28 February 2017 - 0:26 AM
Насчёт оценки сложности, вопрос в том, на каком уровне абстракции этот алгоритм рассматривать. Sleep, в зависимости от реализации, это либо цикл (а это те же сравнения), либо системный вызов, который укажет ОС поставить процесс (поток) в очередь до определённого момента. Очередь получается тогда отображением исходного массива, что по сути является перестановкой. Так что, мне кажется, этот алгоритм только инкапсулирует один из алгоритмов сортировки.
(Я же правильно понял, что вы серьёзно всё это обсуждали?)
Но идея, без сомнения, забавная. Кажется, я такого не придумывал никогда.
Posted 28 February 2017 - 8:32 AM
Насчёт оценки сложности, вопрос в том, на каком уровне абстракции этот алгоритм рассматривать. Sleep, в зависимости от реализации, это либо цикл (а это те же сравнения), либо системный вызов, который укажет ОС поставить процесс (поток) в очередь до определённого момента. Очередь получается тогда отображением исходного массива, что по сути является перестановкой. Так что, мне кажется, этот алгоритм только инкапсулирует один из алгоритмов сортировки.
(Я же правильно понял, что вы серьёзно всё это обсуждали?)
Но идея, без сомнения, забавная. Кажется, я такого не придумывал никогда.
Цикл-то циклом, но количество сравнений в нем напрямую не зависит от количества элементов в массиве. Зависит от максимального элемента. Так что не соглашусь тут с оценкой. Очередь можно рассматривать, как перестановку, но это не обмен местами двух элементов массива, что используется обычно, как оценочная операция, а просто копирование элемента куда-то. Сложность остается N, и, вроде бы я и тут не наврал.
(Да, я более-менее серьезно смотрю на узость возможной сферы применимости данного подхода. Насколько возможно тут говорить про серьезность :-)
С нами сила Алхазашвили!
Posted 28 February 2017 - 12:02 PM
Сонь, а ты про область применения что-нибудь понимаешь?
Смекалкой автор порадовал, но оно хоть куда-нибудь будет адекватно смотреться? Или тебе тоже никакие подходящие задачки в голову не приходят?
Для построения пробок надо получить GPS сигналы от машин. Пока сигналы шлются по сети, они могут перемешиваться. А обрабатывать их надо по порядку. И при этом ждать, пока придёт все нельзя - сервис должен работать в режиме реального времени. Вот что-то вроде sleep sort'а для их упорядочивания и применяется. Ну только там не треды т.к. такое количество тредов ОС не потянет.
Вообще-то сложность самого этого алгоритма константа.
Не совсем так. Стоимость отправки треда в очередь планировщика - константа. Но планировщику эту очередь надо будет сортировать. Поэтому константа получается исключительно из-за того, что у тебя есть операция "отсортировать все это".
Posted 28 February 2017 - 12:04 PM
А в плане эзотеричесикх методов сортировки мне больше всего нравится stack overflow sort: алгоритм идет на stack overflow, ищет вопросы по слову sort и выполняет куски кода из ответов до тех пор, пока массив не окажется отсортированным.
Posted 28 February 2017 - 12:38 PM
0 members, 2 guests, 0 anonymous users
