Программистские будни - истории из жизни
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: только что он подошел ко мне. Смотри, говорит, я подумал над твоей идеей и придумал, как ее реализовать внутри ядра. Вот смотри - у нас пакеты все стоят в очереди. Но если приходит очень срочный пакет (тут он начал показывать руками) - то он напирает, и все, которые перед ним стоят и у кого не получается проскочить - те выдавливаются в стороны (тут он стал показывать не только руками, но и всем телом), кто-то успевает потом встать обратно за его спиной, а кто-то нет... таким образом мы препятствуем тому, что очередь будет застаиваться...
"Над моей идеей", как вам это нравится? да моя идея очереди с приоритетами по сравнению с его силовыми приемами - это просто детский сад!
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2003-05-29 06:47 pm (UTC)Не нужно меня отсылать к учебникам и не нужно меня пытаться обидеть, называя самопальным горе-программистом-надомником, потому что звучит это действительно обидно, хотя я и в самом деле самопальный программист, и был надомником несколько лет. Начинать сейчас флейм на тему computer science я не желаю, потому что не это было темой моего выступления.
Я все знаю и про трудоемкости, и про неиспользуемые параметры, и про империю зла, и про отдельных ее представителей, и про горе надомников, и про умников из университетов, и про профессоров факультетов computer science, и про королей, и про капусту.
Я хотел поделиться забавным наблюдением. Если же говорить серьезно, то вот что я могу сказать:
Представьте себе, что у нас есть некая задача. В процессе ее работы возникают и обрабатываются сообщения. В подавляющем большинстве случаев они обрабатываются в том же порядке, в каком поступают. У большого процента программистов (особенно самопальных, вроде меня) в этом месте в голове щелкает: "Queue". Если этот проект обсуждается между разработчиками, то это слово - queue - НЕИЗБЕЖНО возникнет на самых ранних этапах обсуждения (ну, если обсуждение идет по-английски). Просто потому, что это - самый близкий, если не единственный их подходящих терминов. Ну не может нормальный человек 20 раз в течение часа произнести "а здесь мы будем доставать сообщение из приоритетной очереди" "а здесь мы будем класть сообщение в приоритетную очередь". Очередь - и баста. По крайней мере, мой опыт говорит именно это. Если нужен будет список - то будут говорить список, не уточняя, двусвязный он или односвязный, если будет нужна хеш таблица - то будут говорить "хеш-таблица" или просто "таблица", не уточняя, открытая она или закрытая.
При этом если при слове "хеш-таблица" у большинства программистов все-таки остается в голове воспоминание о том, что таблицы бывают разные, то само слово "очередь", как мы тут только что наблюдали, вызывает самим своим звучанием весьма ограниченный набор соображений. То есть, будучи употреблено однажды, слово это не может не влиять на процесс дальнейшего принятия решений - просто потому, что мы весьма ограничены в терминах, а мыслить вне их, видимо, не можем.
Вот и все. Это соображение показалось мне забавным и интересным. Я подумал, что надо иметь это ввиду, чтобы не попасться при случае в ловушку семантики, и что нужно будет подумать над тем, какие другие похожие потенциальные ямы языка существуют.
И пример Карима, который после разговора на тему очередей вообще немедленно прибежал ко мне с решением проблемы, которую до этого (в рамках старой семантики) просто не мог решить, по-моему, очень хорошо иллюстрирует мою мысль. Если я смог ее внятно обьяснить, конечно.
А добавление в очередь, кстати, никак не будет O(logN), а исключительно O(1). Так уж получается.
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), где М - количество приоритетов в системе.