Программистские будни - истории из жизни

[igorbor]

(История сугубо программистская, предупреждаю сразу. Кто не спрятался, я не виноват).

Сегодня со мной очередной раз приключилась все та же старая история. Мы сидели с напарником и делали ревизию кода. В одном из мест структура данных помещалась в очередь. Функция помещения в очередь получала три аргумента: собственно очередь, обьект, который в нее надо поместить, и третий параметр - ПРИОРИТЕТ.

- Это что? - спросил напарник.



Я как-то даже растерялся. (А как же может быть очередь без приоритетов?) Ну как же, - попытался я ему обьяснить, - вот у нас есть очередь, мы ставим в нее что-то, и если хотим, чтобы оно поместилось не в конец очереди, а поближе к началу, то даем приоритет повыше...

Он не мог меня понять. "Очередь - это First In - First Out, - обьяснял он мне, - а твои приоритеты опошляют светлую идею." "Но ведь это же может понадобиться, верно?" "Да, но это будет уже не очередь!" "ДА КАК ЖЕ НЕ ОЧЕРЕДЬ?!"

Мне в конце концов, конечно, удалось его убедить. Призвав на помощь примеры в виде старушки с палочкой, женщины с ребенком и машины амбуланса на шоссе. Но все равно тень сомнения у него осталась.

Потом я вспомнил, что несколько лет назад точно такой же разговор у меня был в израильской компании, и почти теми же словами. Тогда я еще не поленился и прошелся по комнатам, предлагая всем попавшимся под руку написать сходу прототипы функций для работы с очередью. ВСЕ БЕЗ ИСКЛЮЧЕНИЯ русские программисты добавили приоритет, разве что некоторые добавили к нему еще флаг - использовать его или нет. НИ ОДИН из израильтян этого не сделал.

Я за свою жизнь таких функций написал уже несколько тысяч. Никогда еще мне не приходилось этот приоритет использовать, но ВСЕГДА я его предусматривал. Кто знает, как жизнь повернется, верно?

Update: только что он подошел ко мне. Смотри, говорит, я подумал над твоей идеей и придумал, как ее реализовать внутри ядра. Вот смотри - у нас пакеты все стоят в очереди. Но если приходит очень срочный пакет (тут он начал показывать руками) - то он напирает, и все, которые перед ним стоят и у кого не получается проскочить - те выдавливаются в стороны (тут он стал показывать не только руками, но и всем телом), кто-то успевает потом встать обратно за его спиной, а кто-то нет... таким образом мы препятствуем тому, что очередь будет застаиваться...

"Над моей идеей", как вам это нравится? да моя идея очереди с приоритетами по сравнению с его силовыми приемами - это просто детский сад!

Comments

[igorbor.livejournal.com]

Я не пойму - Вы делаете очередь для какого-то частного случая, или - в библиотеку для использования потом где угодно? :-)

Я же обьяснил - речь шла о вполне конкретном коде.

Ок, отвечаю на все претензии сразу. ДА, там нужна именно такая очередь, как я описал. Именно что с приоритетами. ДА, я знаю, что такое FIFO, и что такое LIFO, и FILO, и FINO, и GIGO, и AIGO. Собственно замешательство у Карима было вызвано исключительно тем фактом, что переменная называлась что-то там подчеркивание queue, и что, говоря о ней, я употреблял именно слово queue, и не priority queue или какое-нибудь другое ПРАВИЛЬНОЕ слово. Именно этой мыслью я и хотел поделиться - как неправильно выбранное/употребленное слово начисто отрезает у человека способность воспринимать вполне очевидные детали. При этом для меня, например, очередь и FIFO - это разные вещи. Для кого-то еще - тоже разные. А для Вас - одинаковые. Неужели Вы, рассуждая про себя про очередной алгоритм, каждый раз проговариваете про себя "очередь с приоритетами" вместо просто "очередь"?

Кстати, каким образом "В случае, когда у меня высокоприоритетных обьектов существенно меньше, чем низкоприоритетных, время их вставки в очередь будет не O(logN), а O(K), где K - количество высокоприоритетных обьектов"? Что там внутре?

Ну, ясно что. Неонка, ясный пень... :)

Да O(1) их будет, конечно же. Кстати ниже я про это писал уже.

[arbat.livejournal.com]

"При этом для меня, например, очередь и FIFO - это разные вещи. Для кого-то еще - тоже разные. А для Вас - одинаковые. Неужели Вы, рассуждая про себя про очередной алгоритм, каждый раз проговариваете про себя "очередь с приоритетами" вместо просто "очередь"?
"

Голова идет кругом. Хорошо, для Вас "очередь" - это всегда с приоритетом, но откуда пафос? Я, по простоте душевной, считал, что очередь - это собирательное название нескольких случаев, которые отличаются политикой обслуживания. Я вполне могу понять, что Вы считаете, что, по умолчанию - это очередь с приоритетом. Странно, что Вас удивляет, что у кого-то есть другие "умолчания". Стандарта-то нету?

[igorbor.livejournal.com]

Насчет пафоса я не очень понял, что Вы имеете ввиду. Я думал, что сумел обьяснить, но попытаюсь еще раз.

Я, как и Вы, считаю, что очередь - это собирательное название нескольких случаев, которые отличаются политикой обслуживания.

Поэтому для меня явилось сюрпризом, что для напарника моего очередь - это вовсе не собирательное название, а только и исключительно FIFO. При этом это так не только для него, а еще для многих других программистов - как, например, в той израильской фирме, про которую я писал.

Я НЕ СЧИТАЮ, что очередь по умолчанию - очередь с приоритетом. Но я ДОПУСКАЮ, что очередь может быть с приоритетом. Меня удивило, когда само употребление термина ОЧЕРЕДЬ автоматически отключает у человека способность воспринимать ее как что бы то ни было отличное от ФИФО. Более того, мне кажется, что такое восприятие очереди исключительно как ФИФО является вредным - поскольку термин этот является широкоупотребляемым, и никакого другого для "очереди вообще" я лично не знаю.

Поэтому, строго говоря, я считаю вредным любое сужение общего понятия до какого-то частного случая по умолчанию. (Возможно, я невнятно выразился - я НЕ ВСЕГДА пишу очередь именно с приоритетами, они у меня всегда разные).

[syarzhuk.livejournal.com]

AIGO???

Re:

[igorbor.livejournal.com]

Anything In Garbage Out :)