Перейти к содержимому


Фото

SLEEP сортировка


  • Чтобы отвечать, сперва войдите на форум
13 ответов в теме

#1 wings Опубликовано 27 Февраль 2017 - 2:03

wings
  • Свои
  • 386 Сообщений:
  • Дмитрий Камаев

Недавно услышал про уникальный способ сортировки, который смогут оценить местные программисты. Он был изобретен на 4chan и работает следующим образом. По количеству элементов в массиве n запускается параллельно n потоков, каждый из которых печатает соответствующий элемент массива c временной задержкой равной значению элемента массива.4chan.png


Изменено: wings, 27 Февраль 2017 - 2:24


#2 Сонечка Опубликовано 27 Февраль 2017 - 10:26

Сонечка
  • Свои
  • 1 658 Сообщений:
  • Софья Сазонова

Огонь!)

Ну и да, каждому алгоритму своя область применения))



#3 МакМих Опубликовано 27 Февраль 2017 - 12:14

МакМих
  • Свои
  • 491 Сообщений:
  • Михаил Макаров
Сонь, а ты про область применения что-нибудь понимаешь?
Смекалкой автор порадовал, но оно хоть куда-нибудь будет адекватно смотреться? Или тебе тоже никакие подходящие задачки в голову не приходят?

#4 Сонечка Опубликовано 27 Февраль 2017 - 12:26

Сонечка
  • Свои
  • 1 658 Сообщений:
  • Софья Сазонова

Не, мне кажется, это забавная штука "чисто для себя, чтоб поржать".

Использовать ее, наверное, можно в каком-нибудь очень уж специфическом случае...

Но, учитывая потенциальное время ее исполнение для массивов с большими числами, выгоднее использовать тот же quick-sort за O(n*log n).



#5 wings Опубликовано 27 Февраль 2017 - 12:38

wings
  • Свои
  • 386 Сообщений:
  • Дмитрий Камаев

Сонь, а ты про область применения что-нибудь понимаешь?
Смекалкой автор порадовал, но оно хоть куда-нибудь будет адекватно смотреться? Или тебе тоже никакие подходящие задачки в голову не приходят?

Тут еще проблема в реальном применении связана с тем как thread management реализован. На него не стоит полагаться в том что все потоки по времени будут параллельны



#6 Syrano Опубликовано 27 Февраль 2017 - 12:51

Syrano
  • Свои
  • 8 996 Сообщений:
  • Владимир Зайцев

Вообще-то сложность самого этого алгоритма константа. Так что теоретически, если данные отвечают определенным условиям, оно может быть эффективнее qsort. Проверить, что все данные удовлетворяют этому условию -- N. Так что в итоге получается N + C. Все вполне правдоподобно :-)

Конечно, надо учесть время переключения потоков, задержку на старт потока, количество потоков, при которых система не деградирует и т.п. Но зная архитектуру, можно это все заложить в "проверку того, что данные допускают такую сортировку". Или построить отображение исходного набора в "подходящий". И для какого-то класса данных получится сортировка, более эффективная, чем qsort. Теоретически :-)

 

Тут скорее интересно то, что использован принципиально иной подход к сортировке. Здесь нет операций сравнения и перестановки в принципе, как таковых. Мне это решение напомнило, как оптимальный путь водой искали. Вероятно, где-то среди таких вот "решений в другой плоскости" можно найти и решение NP-полных задач :-)


"Знаете, а я думаю, что он прав."

#7 Сонечка Опубликовано 27 Февраль 2017 - 13:08

Сонечка
  • Свои
  • 1 658 Сообщений:
  • Софья Сазонова

Ну все же согласись, что тут время зависит от данных, поэтому для большого массива с маленькими числами -да, имеет смысл, а для массива с огромными -нет. А что делать, кстати, с массивом типа [1, 1, 1, 1, ......1, 5]. Как обрабатывается одновременное желание потоков писать в один файл/массив -- системными средствами или как-то еще? Если системными, то не факт, что будет соблюдаться правильная очередь (насколько я помню).



#8 Syrano Опубликовано 27 Февраль 2017 - 13:27

Syrano
  • Свои
  • 8 996 Сообщений:
  • Владимир Зайцев

Так я и говорю для определенного класса данных. Огромные можно нормализовать до различимого шага. А вообще, сложность-то не меняется. Константа. Да, очень большая, но не N*log(N) же все равно :-)

А про "кстати" -- да, стабильность сортировки под вопросом. Ну, будет нестабильная. Тоже вполне применимо.

Операционная ситема, да, разруливает одновременность достпуа к разделяемым ресурсам с точностью до размеров буфера. Там есть разного рода артефакты, но это отдельный разговор.


"Знаете, а я думаю, что он прав."

#9 МакМих Опубликовано 28 Февраль 2017 - 1:26

МакМих
  • Свои
  • 491 Сообщений:
  • Михаил Макаров
Спасибо. :)

#10 Денис Опубликовано 28 Февраль 2017 - 3:26

Денис
  • Genius loci
  • 6 507 Сообщений:
  • Денис Сумин

Насчёт оценки сложности, вопрос в том, на каком уровне абстракции этот алгоритм рассматривать. Sleep, в зависимости от реализации, это либо цикл (а это те же сравнения), либо системный вызов, который укажет ОС поставить процесс (поток) в очередь до определённого момента. Очередь получается тогда отображением исходного массива, что по сути является перестановкой. Так что, мне кажется, этот алгоритм только инкапсулирует один из алгоритмов сортировки.

(Я же правильно понял, что вы серьёзно всё это обсуждали?)

 

Но идея, без сомнения, забавная. Кажется, я такого не придумывал никогда.



#11 Syrano Опубликовано 28 Февраль 2017 - 11:32

Syrano
  • Свои
  • 8 996 Сообщений:
  • Владимир Зайцев

Насчёт оценки сложности, вопрос в том, на каком уровне абстракции этот алгоритм рассматривать. Sleep, в зависимости от реализации, это либо цикл (а это те же сравнения), либо системный вызов, который укажет ОС поставить процесс (поток) в очередь до определённого момента. Очередь получается тогда отображением исходного массива, что по сути является перестановкой. Так что, мне кажется, этот алгоритм только инкапсулирует один из алгоритмов сортировки.

(Я же правильно понял, что вы серьёзно всё это обсуждали?)

 

Но идея, без сомнения, забавная. Кажется, я такого не придумывал никогда.

Цикл-то циклом, но количество сравнений в нем напрямую не зависит от количества элементов в массиве. Зависит от максимального элемента. Так что не соглашусь тут с оценкой. Очередь можно рассматривать, как перестановку, но это не обмен местами двух элементов массива, что используется обычно, как оценочная операция, а просто копирование элемента куда-то. Сложность остается N, и, вроде бы я и тут не наврал.

(Да, я более-менее серьезно смотрю на узость возможной сферы применимости данного подхода. Насколько возможно тут говорить про серьезность :-)


"Знаете, а я думаю, что он прав."

#12 KiberGus Опубликовано 28 Февраль 2017 - 15:02

KiberGus
  • Genius loci
  • 6 513 Сообщений:
  • Алексей Гусейнов

Сонь, а ты про область применения что-нибудь понимаешь?
Смекалкой автор порадовал, но оно хоть куда-нибудь будет адекватно смотреться? Или тебе тоже никакие подходящие задачки в голову не приходят?

Для построения пробок надо получить GPS сигналы от машин. Пока сигналы шлются по сети, они могут перемешиваться. А обрабатывать их надо по порядку. И при этом ждать, пока придёт все нельзя - сервис должен работать в режиме реального времени. Вот что-то вроде sleep sort'а для их упорядочивания и применяется. Ну только там не треды т.к. такое количество тредов ОС не потянет.

 

Вообще-то сложность самого этого алгоритма константа.

Не совсем так. Стоимость отправки треда в очередь планировщика - константа. Но планировщику эту очередь надо будет сортировать. Поэтому константа получается исключительно из-за того, что у тебя есть операция "отсортировать все это".


Зато, обладая единственной в мире подводной орбитальной группировкой спутников глонасс...
gentoo.gif

#13 KiberGus Опубликовано 28 Февраль 2017 - 15:04

KiberGus
  • Genius loci
  • 6 513 Сообщений:
  • Алексей Гусейнов

А в плане эзотеричесикх методов сортировки мне больше всего нравится stack overflow sort: алгоритм идет на stack overflow, ищет вопросы по слову sort и выполняет куски кода из ответов до тех пор, пока массив не окажется отсортированным.


Зато, обладая единственной в мире подводной орбитальной группировкой спутников глонасс...
gentoo.gif

#14 Сонечка Опубликовано 28 Февраль 2017 - 15:38

Сонечка
  • Свои
  • 1 658 Сообщений:
  • Софья Сазонова

Вот этот вариант еще ничего:

http://sorting.valem...om/quantum-bog/






0 пользователей читают эту тему

0 пользователей, 0 гостей, 0 невидимых