LINUX.ORG.RU

И все-таки, почему «спящая сортировка» работает?

 , , , ,


1

3

Вопрос по сабжу. Беру пример, положим, отсюда — https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort#C

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
 
int main(int c, char **v)
{
        while (--c > 1 && !fork());
        sleep(c = atoi(v[c]));
        printf("%d\n", c);
        wait(0);
        return 0;
}

Вопрос, что является сортирующим механизмом в данном случае, планировщик ОС?

Ведь исходный ввод намеренно может быть случайно упорядочен.

Милости прошу в тред.

★★★★★

sleep же, можно сказать, что планировщик. Сначала будут выведены меньшие числа, а потом большие (их процессы всё ещё будут спать).

xaizek ★★★★★ ()

планировщик ОС?

Он самый. Правда работает это до тех пор, пока частота системного таймера выше шага между сортируемымм значениями, а то начнет ошибаться.

devl547 ★★★★★ ()
Ответ на: комментарий от superuser

А вот это и есть комические куплеты,гы :-)

А то хороших тредов по сишке не было. А царюша, наверно, уже выписался.

Twissel ★★★★★ ()
Ответ на: комментарий от devl547

Ты прав.

If you worry about time efficiency of this sorting algorithm (ha!), you can make it a 100 times faster by replacing the sleep(... with usleep(10000 * (c = atoi(v[c]))). The smaller the coefficient, the faster it is, but make sure it's not comparable to your kernel clock ticks or the wake up sequence will be wrong.

Twissel ★★★★★ ()
Ответ на: комментарий от superuser

блять че это за наркомания и где тут сортирока и вабще вы кто?

./a.out $(seq 1 10 | shuf | xargs)

vvviperrr ★★★★★ ()
Ответ на: комментарий от xaizek

Просто я сразу рассматриваю крайние случаи.

Оно же не «понимагией» сортируется, а вполне материальными вычислительными объектами.

Вот самая мякотка в том, когда эти механизмы (объекты) потеряют понимагию и проявят свою природу.

Twissel ★★★★★ ()
Ответ на: комментарий от Twissel

В крайнем случае промежуточные форки могут занять времени больше чем ждёт sleep(последнее число) и порядок не совпадёт так как числа в начале последовательности пропустят своё время вывода. А вообще sleep гарантирует только нижнюю границу, но не ограничен сверху (т.е. может ждать и две секунды, когда попросили одну).

xaizek ★★★★★ ()
Ответ на: комментарий от xaizek

Хотелось бы видеть рабочие примеры.

Зачем же я тред создавал? :-)

Twissel ★★★★★ ()
Ответ на: комментарий от fornlr

На самом деле планировщику ОС всё равно придётся выполнять внутри себя нормальную сортировку, ибо надо же как-то определить когда будить потоки. Каждый тик таймера бегать по списку спящий тредов и проверять, не пришло ли чьё-то время не рационально, поэтому обычно список спящих тредов сортируется по порядку пробуждения и проверяется только первый в списке (если ему не настало время просыпаться - остальным тем более). Соответственно, по факту сложность алгоритма не O(n), просто основная нагрузка переносится из кода приложения в код ядра.

KivApple ★★★★★ ()
Ответ на: комментарий от KivApple

Именно это я имел ввиду, просто не знал как сформулировать в терминах предметной области.

Спасибо!

Twissel ★★★★★ ()
Ответ на: комментарий от fornlr

а я думал, что линейная сортировка - это наркомания...

Да чё, иногда самое то.

vombat ()

Спасибо, славный подход (ушел читать).

vombat ()

А можно вопрос, не понимаю почему переменная с - перезаписывается значением из аргументов? Разве мы не потеряем количество входящих аргументов и разве не рискуем выйти за границы массива? В версии для с++ - там отдельная переменная для времени сна берется? Объясните, пожалуйста, механизм.

Silerus ★★★ ()
Ответ на: комментарий от Silerus

Все дело в волшебных пузырьках системном вызове fork(), я так думаю.

Twissel ★★★★★ ()
Ответ на: комментарий от NextGenenration

Да, ходят слухи, что старина Билл лично ручками сортирует, ручная работа, так сказать.

И теперь старое-доброе выражение «Это работает через Билла Гейтса» приобретает особый смысл :-D

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

Twissel ★★★★★ ()
Ответ на: комментарий от fornlr

насколько я понимаю, тут она таки не линейная, потому что планировщику всё равно надо сортировать по времени.

а так линейные сортировки для частных случаев существуют — counting sort и radix sort

f1u77y ★★★ ()

Было бы прикольно, если бы это ещё и оказывалось быстрее. А так это просто то же самое неявно записано.

anonymous ()
Ответ на: комментарий от anonymous

Это верно, да. Но в итоге уже получается нелинейная сложность.

KivApple ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.