Программистские будни - истории из жизни
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 11:42 am (UTC)В 1988 году пришел я к свому приятелю и говорю - "посмотри, какую я штуку придумал, а? Прелесть!"
"Прелесть," - говорит, - "здорово! Называется - linked list. Молодец!".
В 1989 году пришел я к своему приятелю и говорю - "смотри, новая штука. Сюда пишем тута индексы и интерфейс для запроса..."
"Класс," - говорит, - "здорово задумано. Хорошая вещь - реляционная база данных".
После кольцевого буффера и сортировки слиянием я уехал учиться. Надоело.
Теперь - по существу. Беда в том, что приоритет не всегда нужен. Всаживать приоритет во все очереди - на всякий случай нехорошо. Неэффективно. Все равно, что всаживать муттексы в класс string. Полезно иметь разные очереди: с приоритетом, FIFO и так далее (скажем, мне нужна была очередь, в которой все собщения имели ключ и, если приходило новое сообщение, пока старое с тем же кючом еще не было еще отправлено - его надо было заменить, а не добавлять). Все это - policies. Два варианта: или имплементировать набор разных очередей - для разных задач, или применить "метод Александреску" и делать templates with policy classes.
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% случаев этот приоритет игнорируется.
Дык!
Так вот, в Мотороле эти wrappers никаких приоритетов изначально не предусматривали (бишь дифолт стоял). А когда надо было какие-то мессаджи отправлять вне очереди, я попытался изменить wrappers-интерфейсы, добавив приоритет.
Ни фига. Идея была освистана. Дело кончилось добавлением новой очереди, которая просматривалась первой в цикле, пока сообщения в ней не кончались.
Может, дело в том, что у нас-выходцев известно откуда, совсем другие представления о самом понятии "очередь"? То бишь не может быть очереди без "блата"?
no subject
Date: 2003-05-29 11:57 am (UTC)И кстати блат здесь ни при чем. Я же говорю - бабушка с палочкой!
Re: Дык!
Date: 2003-05-29 01:02 pm (UTC)В их варианте вставить-забрать сообщение в очередь занимает O(ln(m)), где m - количество разных приоритетов. А в Вашем сколько?
no subject
Date: 2003-05-29 01:32 pm (UTC)По-моему, ошибка думать о деталях реализации на этапах дизайна. Если мы увидим, что очередь с приоритетами оказывается слишком медленной - мы будем думать над тем, как ее ускорить. Но обычно, как показывает мой опыт, основной выигрыш в производительности приходит не отсюда, а от выбора правильного алгоритма.
Ну и потом - мы ведь понимаем, что МОЖНО сделать очередь с приоритетами с такой же трудоемкостью, как и без приоритетов, верно?
no subject
Date: 2003-05-29 03:25 pm (UTC)Я не пойму - Вы делаете очередь для какого-то частного случая, или - в библиотеку для использования потом где угодно? :-)
Если для частного, на хрена вообще тратить время на приоритет, если он сейчас не нужен? Вы сначала заделали что-то про запас, возможно потеряли эффективность и усложнили имплементацию - без немедленной нужды. А сами говорите об экономии времени.
Если для общего, то почему Вы так смело расчитываете, сколько в этой очереди будет сообщений? И токуда известно, насколько этот сбереженный час важен? Может, мы ее потом вставим в навигацию самолета, где от кучи датчиков будет нестись хренова туча информации и она захлебенется на ту самую долю секунды?
И что за идея (высказанная там, наверху) - диктовать клиенту своего кода дизайн через интерфейс? Вы же не настаиваете, чтобы класс vector имел функцию "internalMutexLock()", чтобы напомнить разработчику, что иногда и запереть неплохо?
Кстати, каким образом "В случае, когда у меня высокоприоритетных обьектов существенно меньше, чем низкоприоритетных, время их вставки в очередь будет не O(logN), а O(K), где K - количество высокоприоритетных обьектов"? Что там внутре?
В любом случае - суть моих возражений в том, что FIFO и очередь с приоритетом - это разные вещи. Это не есть плохая и хорошая имплементации одной вещи. И использовать одну, где нужна другая - "про запас" странно.
no subject
Date: 2003-05-29 06:56 pm (UTC)Я же обьяснил - речь шла о вполне конкретном коде.
Ок, отвечаю на все претензии сразу. ДА, там нужна именно такая очередь, как я описал. Именно что с приоритетами. ДА, я знаю, что такое FIFO, и что такое LIFO, и FILO, и FINO, и GIGO, и AIGO. Собственно замешательство у Карима было вызвано исключительно тем фактом, что переменная называлась что-то там подчеркивание queue, и что, говоря о ней, я употреблял именно слово queue, и не priority queue или какое-нибудь другое ПРАВИЛЬНОЕ слово. Именно этой мыслью я и хотел поделиться - как неправильно выбранное/употребленное слово начисто отрезает у человека способность воспринимать вполне очевидные детали. При этом для меня, например, очередь и FIFO - это разные вещи. Для кого-то еще - тоже разные. А для Вас - одинаковые. Неужели Вы, рассуждая про себя про очередной алгоритм, каждый раз проговариваете про себя "очередь с приоритетами" вместо просто "очередь"?
Кстати, каким образом "В случае, когда у меня высокоприоритетных обьектов существенно меньше, чем низкоприоритетных, время их вставки в очередь будет не O(logN), а O(K), где K - количество высокоприоритетных обьектов"? Что там внутре?
Ну, ясно что. Неонка, ясный пень... :)
Да O(1) их будет, конечно же. Кстати ниже я про это писал уже.
no subject
Date: 2003-05-30 05:40 pm (UTC)"
Голова идет кругом. Хорошо, для Вас "очередь" - это всегда с приоритетом, но откуда пафос? Я, по простоте душевной, считал, что очередь - это собирательное название нескольких случаев, которые отличаются политикой обслуживания. Я вполне могу понять, что Вы считаете, что, по умолчанию - это очередь с приоритетом. Странно, что Вас удивляет, что у кого-то есть другие "умолчания". Стандарта-то нету?
no subject
Date: 2003-05-31 11:47 am (UTC)Я, как и Вы, считаю, что очередь - это собирательное название нескольких случаев, которые отличаются политикой обслуживания.
Поэтому для меня явилось сюрпризом, что для напарника моего очередь - это вовсе не собирательное название, а только и исключительно FIFO. При этом это так не только для него, а еще для многих других программистов - как, например, в той израильской фирме, про которую я писал.
Я НЕ СЧИТАЮ, что очередь по умолчанию - очередь с приоритетом. Но я ДОПУСКАЮ, что очередь может быть с приоритетом. Меня удивило, когда само употребление термина ОЧЕРЕДЬ автоматически отключает у человека способность воспринимать ее как что бы то ни было отличное от ФИФО. Более того, мне кажется, что такое восприятие очереди исключительно как ФИФО является вредным - поскольку термин этот является широкоупотребляемым, и никакого другого для "очереди вообще" я лично не знаю.
Поэтому, строго говоря, я считаю вредным любое сужение общего понятия до какого-то частного случая по умолчанию. (Возможно, я невнятно выразился - я НЕ ВСЕГДА пишу очередь именно с приоритетами, они у меня всегда разные).
no subject
Date: 2003-07-04 10:18 pm (UTC)Re:
Date: 2003-07-05 05:36 am (UTC)no subject
Date: 2003-05-29 04:18 pm (UTC)Теперь буду спрашивать на интервью, что-такое очередь и как ее реализовать, - что бы таких самопальных горе-программистов-надомников сразу отсекать. Спасибо за науку.
P.S. Кстати, priority queue - совершенно отдельный обьект. В учебниках описан. Временные характеристики и организация данных радикально отличны от queue, deque, list.
no subject
Date: 2003-05-29 06:04 pm (UTC)Поэтому если из соображений дизайне следует что может понадобиться priority queue, то это решение которое должно быть отдельно обдумано.
no subject
Date: 2003-05-29 06:49 pm (UTC)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), где М - количество приоритетов в системе.
no subject
Date: 2003-05-29 11:55 pm (UTC)no subject
Date: 2003-07-16 05:37 am (UTC)Cамые смешные анекдоты
Date: 2011-07-31 10:35 pm (UTC)И вот. Ползу я на коленях по чердаку вдоль кабеля, потолок низкий, темно, по уши в птичьем помете, кругом только кошки дохлые валяются. Вдруг, навстречу мне выползает бомж ужасно грязный и вонючий. Говорит:
- Мужик, ты че тут делаешь?
- Интернет проверяю. - автоматически отвечаю я.
- А коаксиал тестил?
- Да тестил!
- А линк на хабе горит?
- Горит.
- А мастдай у юзера какой?
- 95-й, вроде не глючит.
- А сетевуха трикомовская?
...И тут я понял, что ждет меня в будущем...
Пишу програмку, переворачивающую Norton Commander, всё как обычно, но кверх
ногами. Подходит, значит, препод и выдаёт такое:
- Слушайте, девушка, а может вы дискету другой стороной вставили?
Гогот стоял такой, что до конца пары мы нашего раскрасневшегося от стыда
препода не видели...
Во время лекции заходит в аудиторию студентка:
-Можно?
Профессор:
-А почему Вы опаздываете?
Студентка:
-Вы знаете я вчера легла около двух и поэтому проспала?
Профессор:
-Ну, ладно, проходите и в следующий раз ложитесь около одного....
На приеме у врача:
- Доктор, мне такие кошмары снятся… Представьте: гуляет моя теща с крокодилом по улице. Зубы огромные кривые, изо рта так пахнет, что вообще ужас, кожа зеленая сморщенная страшная, лапищи здоровые с когтями...
- Да, действительно, кошмар...
- Да подождите, я еще про крокодила не рассказал!
Продолжаем тему анекдотов ...
________________
[url=http://hyipinvestment.biz/?a=cust&page=hyip]investment online[/url]