Программистские будни - истории из жизни
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}
Re:
Date: 2003-05-29 11:54 am (UTC)В данном же случае код, который писался, является исследовательским, и в плане работ у меня была, в частности, мысль о том, что приоритеты могут пригодиться (может, еще и пригодятся). Опять же - запас карман не тянет, а ломать - не строить.
Но основная мысль не о том, а о том, что для меня, например, слово "очередь" в первую очередь ассоциируется с приоритетом, а очередь без приоритета - это частный случай. Для него же - как раз наоборот. Default, так сказать, разный.
no subject
Date: 2003-05-29 12:20 pm (UTC)Re:
Date: 2003-05-29 12:30 pm (UTC)no subject
Date: 2003-05-29 12:35 pm (UTC)Re:
Date: 2003-05-29 12:56 pm (UTC)Скажем, в очереди стоят 2 молодых человека. Появляются 3 бабушки с палочками. Все они пропускаются вперед благородными молодыми людьми, стоящими в очереди, а так как время обслуживания одной бабушки ненулевое, то вторая бабушка оказывается не "пропущенной без очереди", а "помещенной в голову очереди", а третья бабушка оказывается помещенной на второе место в очереди (если не считать стоящей в очереди ту бабушку, которая в настоящее время обслуживается), а за ней по-прежнему стоят двое молодых людей. Таким образом, бабушка оказывается примерно в середине очереди (2 из 4) %)
Заметьте, что все бабушки приняты для простоты рассмотрения одинаковыми. А если в этот момент подойдет бабушка с двумя палочками или с маленьким ребенком, словом, с приоритетом большим, чем у третьей бабульки?
Ваш подход другими словами предполагает, что приоритетов существует только два. Такой подход существует в большой массе современных аппликаций, например, в TCP/IP стеке, с которым я сейчас вожусь. В результате возникают всякие нехорошие артефакты - к примеру, приоритет пакета на retransmission и syn-пакета оказывается одинаковым, и syn-flood вызывает тайм-аут уже открытых соединений. По хорошему же, как мне представляется, если применить старый советский подход - "тех, которые без очереди, пропускать через одного", например - то аппликация становится гораздо более жизнеспособной.
Хотя, конечно, в каждом конкретном случае надо смотреть отдельно, да.
no subject
Date: 2003-05-29 12:56 pm (UTC)Ну-ка, дайте подумать. Если Вы добавляете приоритет, то Вам надо сохранять двойной порядок: по приоритету, затем - по времени. Если Вы захотите все это в один контейнер совать, то у Вас вставка будет в лучшем случае О(logN). Плохо. Если приоритет временно не нужен, то FIFO дает О(1). Иначе можно создать по одному отдельной очереди на каждое значение приоритета и внутри очередей изпользовать какой-нибудь простой (кольцевой? deque?) буффер с О(1) вставкой. Тогда добавление будет О(m), где m - количество приоритетов, которое Вы сейчас используете.
Хмммм...
Re:
Date: 2003-05-29 01:26 pm (UTC)- при небольших значениях M и N все эти прикидки не работают. Как Вы знаете, например, линейный поиск в массиве из трех элементов, скорее всего, будет не медленнее, а быстрее, чем метод половинного деления.
- В случае, когда у меня высокоприоритетных обьектов существенно меньше, чем низкоприоритетных, время их вставки в очередь будет не O(logN), а O(K), где K - количество высокоприоритетных обьектов.
- собственно говоря, никто не утверждал, что внутри очередь организована как массив. Если мне известно заранее число различных приоритетов (а оно, как правило, известно и невелико), то вставка обьекта происходит даже не за O(m), а за O(1) - а как это реализовать, не очень важно, например, так, как Вы сказали.
- и самое главное - совершенно не факт, что вставление и удаление из очереди - то место кода, которое надо оптимизировать :)
Использование приоритета как одного из аргументов важно, на мой взгляд, не для того, чтобы немедленно начать думать о деталях реализации, а скорее для того, чтобы напоминать разработчику, что обьекты МОГУТ ИМЕТЬ РАЗЛИЧНЫЙ приоритет. Чтобы он непрерывно об этом помнил и учитывал в своем дизайне. Пусть даже в 99% случаев этот приоритет игнорируется.