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

[igorbor]

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

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

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



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

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

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

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

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

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

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

Comments

[arbat.livejournal.com]

В 1988 году пришел я к свому приятелю и говорю - "посмотри, какую я штуку придумал, а? Прелесть!"
"Прелесть," - говорит, - "здорово! Называется - linked list. Молодец!".

В 1989 году пришел я к своему приятелю и говорю - "смотри, новая штука. Сюда пишем тута индексы и интерфейс для запроса..."
"Класс," - говорит, - "здорово задумано. Хорошая вещь - реляционная база данных".

После кольцевого буффера и сортировки слиянием я уехал учиться. Надоело.

Теперь - по существу. Беда в том, что приоритет не всегда нужен. Всаживать приоритет во все очереди - на всякий случай нехорошо. Неэффективно. Все равно, что всаживать муттексы в класс string. Полезно иметь разные очереди: с приоритетом, FIFO и так далее (скажем, мне нужна была очередь, в которой все собщения имели ключ и, если приходило новое сообщение, пока старое с тем же кючом еще не было еще отправлено - его надо было заменить, а не добавлять). Все это - policies. Два варианта: или имплементировать набор разных очередей - для разных задач, или применить "метод Александреску" и делать templates with policy classes.

Дык!

[wolfichek.livejournal.com]

В Юниксовом IPC, как ты знаешь, тоже есть очереди, с приоритетом в качестве параметра. К ним обычно дописывают аппликативные wrappers.

Так вот, в Мотороле эти wrappers никаких приоритетов изначально не предусматривали (бишь дифолт стоял). А когда надо было какие-то мессаджи отправлять вне очереди, я попытался изменить wrappers-интерфейсы, добавив приоритет.

Ни фига. Идея была освистана. Дело кончилось добавлением новой очереди, которая просматривалась первой в цикле, пока сообщения в ней не кончались.

Может, дело в том, что у нас-выходцев известно откуда, совсем другие представления о самом понятии "очередь"? То бишь не может быть очереди без "блата"?

[(Anonymous)]

Полный мрак.

Теперь буду спрашивать на интервью, что-такое очередь и как ее реализовать, - что бы таких самопальных горе-программистов-надомников сразу отсекать. Спасибо за науку.

P.S. Кстати, priority queue - совершенно отдельный обьект. В учебниках описан. Временные характеристики и организация данных радикально отличны от queue, deque, list.

[trurle.livejournal.com]

Я тоже считаю что очередь сама по себе должна быть без приоритетов. Мертвые параметры вызывают у меня недобрые чувства. Стиль Империи Зла: this parameter is left unused in the current implementation.
Поэтому если из соображений дизайне следует что может понадобиться priority queue, то это решение которое должно быть отдельно обдумано.

[igorbor.livejournal.com]

Ок, если разговор пошел серьезно, то вот что я скажу.

Не нужно меня отсылать к учебникам и не нужно меня пытаться обидеть, называя самопальным горе-программистом-надомником, потому что звучит это действительно обидно, хотя я и в самом деле самопальный программист, и был надомником несколько лет. Начинать сейчас флейм на тему computer science я не желаю, потому что не это было темой моего выступления.


Я все знаю и про трудоемкости, и про неиспользуемые параметры, и про империю зла, и про отдельных ее представителей, и про горе надомников, и про умников из университетов, и про профессоров факультетов computer science, и про королей, и про капусту.

Я хотел поделиться забавным наблюдением. Если же говорить серьезно, то вот что я могу сказать:

Представьте себе, что у нас есть некая задача. В процессе ее работы возникают и обрабатываются сообщения. В подавляющем большинстве случаев они обрабатываются в том же порядке, в каком поступают. У большого процента программистов (особенно самопальных, вроде меня) в этом месте в голове щелкает: "Queue". Если этот проект обсуждается между разработчиками, то это слово - queue - НЕИЗБЕЖНО возникнет на самых ранних этапах обсуждения (ну, если обсуждение идет по-английски). Просто потому, что это - самый близкий, если не единственный их подходящих терминов. Ну не может нормальный человек 20 раз в течение часа произнести "а здесь мы будем доставать сообщение из приоритетной очереди" "а здесь мы будем класть сообщение в приоритетную очередь". Очередь - и баста. По крайней мере, мой опыт говорит именно это. Если нужен будет список - то будут говорить список, не уточняя, двусвязный он или односвязный, если будет нужна хеш таблица - то будут говорить "хеш-таблица" или просто "таблица", не уточняя, открытая она или закрытая.

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

Вот и все. Это соображение показалось мне забавным и интересным. Я подумал, что надо иметь это ввиду, чтобы не попасться при случае в ловушку семантики, и что нужно будет подумать над тем, какие другие похожие потенциальные ямы языка существуют.

И пример Карима, который после разговора на тему очередей вообще немедленно прибежал ко мне с решением проблемы, которую до этого (в рамках старой семантики) просто не мог решить, по-моему, очень хорошо иллюстрирует мою мысль. Если я смог ее внятно обьяснить, конечно.

А добавление в очередь, кстати, никак не будет O(logN), а исключительно O(1). Так уж получается.

[bormor.livejournal.com]

Другими словами, даем бабушке не палочку, а клюку, обучаем основным принципам боя с шестом и посылаем вперед пробиваться сквозь очередь?

[inna-art.livejournal.com]

Очень увлекательная и поучительная история! :)

Cамые смешные анекдоты

[(Anonymous)]

Работаю я монтажником. Подключаю юзеров к Интернет по выделенке.
И вот. Ползу я на коленях по чердаку вдоль кабеля, потолок низкий, темно, по уши в птичьем помете, кругом только кошки дохлые валяются. Вдруг, навстречу мне выползает бомж ужасно грязный и вонючий. Говорит:
- Мужик, ты че тут делаешь?
- Интернет проверяю. - автоматически отвечаю я.
- А коаксиал тестил?
- Да тестил!
- А линк на хабе горит?
- Горит.
- А мастдай у юзера какой?
- 95-й, вроде не глючит.
- А сетевуха трикомовская?
...И тут я понял, что ждет меня в будущем...



Пишу програмку, переворачивающую Norton Commander, всё как обычно, но кверх
ногами. Подходит, значит, препод и выдаёт такое:
- Слушайте, девушка, а может вы дискету другой стороной вставили?
Гогот стоял такой, что до конца пары мы нашего раскрасневшегося от стыда
препода не видели...



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




На приеме у врача:
- Доктор, мне такие кошмары снятся… Представьте: гуляет моя теща с крокодилом по улице. Зубы огромные кривые, изо рта так пахнет, что вообще ужас, кожа зеленая сморщенная страшная, лапищи здоровые с когтями...
- Да, действительно, кошмар...
- Да подождите, я еще про крокодила не рассказал!





Продолжаем тему анекдотов ...

________________
[url=http://hyipinvestment.biz/?a=cust&page=hyip]investment online[/url]