Sleep sort

Радикальное улучшение o(n*log(n)) для сортировки чисел
 
EE Татарин #17.01.2012 03:47
+
-
edit
 

Татарин

координатор
★★★★☆


Сначала хотел в юмор... А теперь даже и не знаю. :) Но прикольно!
code text
  1. #!/bin/bash
  2. function f() {
  3.     sleep "$1"
  4.     echo "$1"
  5. }
  6. while [ -n "$1" ]
  7. do
  8.     f "$1" &
  9.     shift
  10. done
  11. wait
...А неубитые медведи делили чьи-то шкуры с шумом. Боюсь, мы поздно осознали, к чему всё это приведёт.  1515
RU Balancer #17.01.2012 03:50  @Татарин#17.01.2012 03:47
+
-
edit
 

Balancer

администратор
★★★★★
Жесть :D

Круче только вариант получения завтрашней даты :)
 
EE Татарин #17.01.2012 03:53  @Balancer#17.01.2012 03:50
+
-
edit
 

Татарин

координатор
★★★★☆
Balancer> Круче только вариант получения завтрашней даты :)
sleep(86400000); cout<<date();
?
...А неубитые медведи делили чьи-то шкуры с шумом. Боюсь, мы поздно осознали, к чему всё это приведёт.  1515
RU Balancer #17.01.2012 03:56  @Татарин#17.01.2012 03:53
+
-
edit
 

Balancer

администратор
★★★★★
Татарин> sleep(86400000);

Ну да, типа того :) Только обычно в секундах. Есть вариант с последующим sleep(-86400) :)
 
EE Татарин #17.01.2012 04:32  @Balancer#17.01.2012 03:56
+
-
edit
 

Татарин

координатор
★★★★☆
Татарин>> sleep(86400000);
Balancer> Ну да, типа того :)
Ну это уже явный курьёз, а вот с этой сортировкой меня уже час никак не покидает дикая мысль, что можно придумать хардвару, которая бы реально давала на этом принципе выигрыш. :)
Применения бы, думаю, нашлись.
...А неубитые медведи делили чьи-то шкуры с шумом. Боюсь, мы поздно осознали, к чему всё это приведёт.  1515
RU Balancer #29.01.2012 01:59  @Татарин#17.01.2012 04:32
+
-
edit
 

Balancer

администратор
★★★★★
Татарин> а вот с этой сортировкой меня уже час никак не покидает дикая мысль, что можно придумать хардвару, которая бы реально давала на этом принципе выигрыш. :)

Да чего там, делаешь
array[2*n] = n;
array[2*n+1] = true;

потом читаешь вподряд все не пустые ячейки :)
 
EE Татарин #29.01.2012 18:57  @Balancer#29.01.2012 01:59
+
-
edit
 

Татарин

координатор
★★★★☆
Balancer> Да чего там, делаешь
Balancer> array[2*n] = n;
Balancer> array[2*n+1] = true;
Balancer> потом читаешь вподряд все не пустые ячейки :)
Не понял. А смысл?

Если у меня есть пары типа "имя-рост", "Петя - 2", "Вася - 5", "Маша - 3", то слипсорт их отсортирует, достаточно лишь "спать" по росту - получишь имена в верном порядке. Это реально работающий алгоритм. А как тут поможет массив с чтением подряд?
...А неубитые медведи делили чьи-то шкуры с шумом. Боюсь, мы поздно осознали, к чему всё это приведёт.  16.0.912.7716.0.912.77
RU Balancer #29.01.2012 19:05  @Татарин#29.01.2012 18:57
+
-
edit
 

Balancer

администратор
★★★★★
Татарин> Не понял. А смысл?

Такой же, как и sleep sort.

Татарин> Если у меня есть пары типа "имя-рост", "Петя - 2", "Вася - 5", "Маша - 3", то слипсорт их отсортирует, достаточно лишь "спать" по росту - получишь имена в верном порядке. Это реально работающий алгоритм. А как тут поможет массив с чтением подряд?

Именно так.

data[2] = 'Петя'
data[5] = 'Вася'
data[3] = 'Маша'

for(data as key => value) print key, value

:)

Ну, разве что писать лучше не значение, а массив (ключ сортировки может совпадать) структур (сразу от NULL отличать)

Практичность не меньшая, чем у sleep sort :)
 9.09.0
EE Татарин #29.01.2012 19:11  @Balancer#29.01.2012 19:05
+
-
edit
 

Татарин

координатор
★★★★☆
Balancer> Ну, разве что писать лучше не значение, а массив (ключ сортировки может совпадать) структур (сразу от NULL отличать)
Balancer> Практичность не меньшая, чем у sleep sort :)
А, ОК. Но в теории алгоритмов этот трюк (размен памяти на быстродействие) известен, его минусы очевидны: за память нужно платить. Слипсорт красив тем, что он пользует как бы почти на халяву доставшееся нам измерение.
За увеличение площади памяти, растяжение по любой координате - платить нужно. А за растяжение по времени - нет, это халява.
...А неубитые медведи делили чьи-то шкуры с шумом. Боюсь, мы поздно осознали, к чему всё это приведёт.  16.0.912.7716.0.912.77
RU Balancer #29.01.2012 19:13  @Татарин#29.01.2012 19:11
+
-
edit
 

Balancer

администратор
★★★★★
Татарин> За увеличение площади памяти, растяжение по любой координате - платить нужно. А за растяжение по времени - нет, это халява.

Ну, тут, скажем, sleep(2e9) — это сколько? ;)
 9.09.0
EE Татарин #29.01.2012 20:15  @Balancer#29.01.2012 19:13
+
-
edit
 

Татарин

координатор
★★★★☆
Татарин>> За увеличение площади памяти, растяжение по любой координате - платить нужно. А за растяжение по времени - нет, это халява.
Balancer> Ну, тут, скажем, sleep(2e9) — это сколько? ;)
Ну, сортируются же не только 32-бит числа и аргумент не обязан быть в секундах. Скажем, кондёр (1 бит ДОЗУ), который задаёт время, полный разряд - детерминированно за миллисекунду.
При этом сортировка даже не обязана быть гарантированой: скорости многих алгоритмов зависят от "качества" исходных данных.
...А неубитые медведи делили чьи-то шкуры с шумом. Боюсь, мы поздно осознали, к чему всё это приведёт.  16.0.912.7716.0.912.77
US Mishka #29.01.2012 21:06  @Татарин#29.01.2012 19:11
+
-
edit
 

Mishka

модератор
★★★

Татарин> А, ОК. Но в теории алгоритмов этот трюк (размен памяти на быстродействие) известен, его минусы очевидны: за память нужно платить.

Да — bucket sort
Татарин> Слипсорт красив тем, что он пользует как бы почти на халяву доставшееся нам измерение.
Но-но. Никаких бесплатностей. Это кажется, что бесплатно, на самом деле организация процесса, оценка максимума, дополнительная аппаратура.

Татарин> За увеличение площади памяти, растяжение по любой координате - платить нужно. А за растяжение по времени - нет, это халява.

Плюс никакой не должен начинать отсчёт времени до последнего слипа — иначе попа возможна. Т.е. приведённый пример не корректен. Можно легко высчитать на расходы на запуск шела/слипа и дать данные, когда напечатает чушь.
 5.05.0
BG Реконструктор #30.01.2012 02:16
+
-
edit
 
Это будет работать только если разница между первым и последним запуском нити будет меньше 1 мс или тем чем этот конкретный слийп работает.
 

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru