Программистские будни - истории из жизни
May. 29th, 2003 01:42 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
igorbor(История сугубо программистская, предупреждаю сразу. Кто не спрятался, я не виноват).
Сегодня со мной очередной раз приключилась все та же старая история. Мы сидели с напарником и делали ревизию кода. В одном из мест структура данных помещалась в очередь. Функция помещения в очередь получала три аргумента: собственно очередь, обьект, который в нее надо поместить, и третий параметр - ПРИОРИТЕТ.
- Это что? - спросил напарник.
Я как-то даже растерялся. (А как же может быть очередь без приоритетов?) Ну как же, - попытался я ему обьяснить, - вот у нас есть очередь, мы ставим в нее что-то, и если хотим, чтобы оно поместилось не в конец очереди, а поближе к началу, то даем приоритет повыше...
Он не мог меня понять. "Очередь - это First In - First Out, - обьяснял он мне, - а твои приоритеты опошляют светлую идею." "Но ведь это же может понадобиться, верно?" "Да, но это будет уже не очередь!" "ДА КАК ЖЕ НЕ ОЧЕРЕДЬ?!"
Мне в конце концов, конечно, удалось его убедить. Призвав на помощь примеры в виде старушки с палочкой, женщины с ребенком и машины амбуланса на шоссе. Но все равно тень сомнения у него осталась.
Потом я вспомнил, что несколько лет назад точно такой же разговор у меня был в израильской компании, и почти теми же словами. Тогда я еще не поленился и прошелся по комнатам, предлагая всем попавшимся под руку написать сходу прототипы функций для работы с очередью. ВСЕ БЕЗ ИСКЛЮЧЕНИЯ русские программисты добавили приоритет, разве что некоторые добавили к нему еще флаг - использовать его или нет. НИ ОДИН из израильтян этого не сделал.
Я за свою жизнь таких функций написал уже несколько тысяч. Никогда еще мне не приходилось этот приоритет использовать, но ВСЕГДА я его предусматривал. Кто знает, как жизнь повернется, верно?
Update: только что он подошел ко мне. Смотри, говорит, я подумал над твоей идеей и придумал, как ее реализовать внутри ядра. Вот смотри - у нас пакеты все стоят в очереди. Но если приходит очень срочный пакет (тут он начал показывать руками) - то он напирает, и все, которые перед ним стоят и у кого не получается проскочить - те выдавливаются в стороны (тут он стал показывать не только руками, но и всем телом), кто-то успевает потом встать обратно за его спиной, а кто-то нет... таким образом мы препятствуем тому, что очередь будет застаиваться...
"Над моей идеей", как вам это нравится? да моя идея очереди с приоритетами по сравнению с его силовыми приемами - это просто детский сад!
Сегодня со мной очередной раз приключилась все та же старая история. Мы сидели с напарником и делали ревизию кода. В одном из мест структура данных помещалась в очередь. Функция помещения в очередь получала три аргумента: собственно очередь, обьект, который в нее надо поместить, и третий параметр - ПРИОРИТЕТ.
- Это что? - спросил напарник.
Я как-то даже растерялся. (А как же может быть очередь без приоритетов?) Ну как же, - попытался я ему обьяснить, - вот у нас есть очередь, мы ставим в нее что-то, и если хотим, чтобы оно поместилось не в конец очереди, а поближе к началу, то даем приоритет повыше...
Он не мог меня понять. "Очередь - это First In - First Out, - обьяснял он мне, - а твои приоритеты опошляют светлую идею." "Но ведь это же может понадобиться, верно?" "Да, но это будет уже не очередь!" "ДА КАК ЖЕ НЕ ОЧЕРЕДЬ?!"
Мне в конце концов, конечно, удалось его убедить. Призвав на помощь примеры в виде старушки с палочкой, женщины с ребенком и машины амбуланса на шоссе. Но все равно тень сомнения у него осталась.
Потом я вспомнил, что несколько лет назад точно такой же разговор у меня был в израильской компании, и почти теми же словами. Тогда я еще не поленился и прошелся по комнатам, предлагая всем попавшимся под руку написать сходу прототипы функций для работы с очередью. ВСЕ БЕЗ ИСКЛЮЧЕНИЯ русские программисты добавили приоритет, разве что некоторые добавили к нему еще флаг - использовать его или нет. НИ ОДИН из израильтян этого не сделал.
Я за свою жизнь таких функций написал уже несколько тысяч. Никогда еще мне не приходилось этот приоритет использовать, но ВСЕГДА я его предусматривал. Кто знает, как жизнь повернется, верно?
Update: только что он подошел ко мне. Смотри, говорит, я подумал над твоей идеей и придумал, как ее реализовать внутри ядра. Вот смотри - у нас пакеты все стоят в очереди. Но если приходит очень срочный пакет (тут он начал показывать руками) - то он напирает, и все, которые перед ним стоят и у кого не получается проскочить - те выдавливаются в стороны (тут он стал показывать не только руками, но и всем телом), кто-то успевает потом встать обратно за его спиной, а кто-то нет... таким образом мы препятствуем тому, что очередь будет застаиваться...
"Над моей идеей", как вам это нравится? да моя идея очереди с приоритетами по сравнению с его силовыми приемами - это просто детский сад!
no subject
Date: 2003-05-30 10:42 am (UTC)По делу: Вопрос о приоритетах решается на стадии дизайна и редизайна. Их присутствие влечет дополнительный код для аллокации и координации использования, и, -- сквозь систему, -- поддержку обработки обьектов в произвольном порядке вдобавок к отслеживанию приоритетов.
Заметим, что приоритеты есть атрибуты тех или иных обьектов (например, сообщений, нитей исполнения, блоков данных (e.g., messages, threads, I/O blocks)). И очереди состоят из обьектов. В грамотной реализации вместо лишнего параметра (с котороым следует как-то разбираться на каждом вызове, захламляя программу) в очередь идет обьект, а конкретная реализация очереди разбирается с приоритетом, и, возможно, с локальносью кэша, CPU affinity, синхронизацией доступа, и проч. Например, очередь threads в scheduler сильно разнится от очередей сообщений в STREAMS, хотя у обоих есть понятие приоритета.
О добавлении. Цитата из _Algorithms in C_ (3rd. ed., v.1) by Sedgewick: "Implementations of the priority queues ADT have widely varying performance characteristics". В частности, оба heap and binomial queue guarantee worst-case logaritmic insert performance. А несортированный список или массив с O(1) вставкой несет линейную цену на извлечение.
А в остальном, уважаемый собеседник, Вы, конечно, правы, -- следует всемерно споспешествовать разуванию шор в программистском дискурсе.
За кадром остались: влияние менеджеров (и раскол группы на две, с разнящимися представлениями о стандартном обьекте), code reviews, использование механизмов наследования, выбор эффективного языка для прототипирования.
no subject
Date: 2003-05-30 05:54 pm (UTC)Теперь понятно, что без ограничения общности мы можем считать, что у нас только одно данное каждого приоритета (грубо говоря, если мы считаем, что храним не отдельные сообщения, а в виде FIFO для каждого приоритета отдельно, то и - опаньки: FIFO эto O(1) на ввод-вывод).
Таким образом вопрос - надо как-то организовать набор данных, чтобы их можно было извлекать в определенном порядке. Задачка знакомая. Ответ известен: если набор приоритетов конечен, - скажем, целые числа от 0 до 99, то создаем массив размером 100, куда пишем - по индексу. Результат - O(1). Однако, если нам надо поддерживать произвольные приоритеты - О(logM), где М - количество приоритетов в системе.