Waiting time paradox #4: aftermath

(продолжение серии про парадокс времени ожидания)

…Мне кажется, это поразительный эффект: добавка sleep(5) в цикл обработки задач может уменьшать среднее время обработки. Даже после того, как я уже разобрался с этим эффектом на примере автобусной остановки, я все еще не мог поверить, что такой же эффект будет и в системе с очередью. И, несмотря на все формулы, разобранные примеры и симуляции, на интуитивном уровне я все еще ощущаю это как какой-то трюк. Это и поразительно: хотя логически я все понимаю, могу объяснить, и симуляцию написать, и картинку нарисовать – но моя интуиция все равно отказывается воспринимать это как очевидное.

И ведь происходит все в очень обыденной системе, с которой мы регулярно сталкиваемся в жизни. В математике есть множество выносящих мозг результатов, но многие из них выносят мозг просто потому, что относятся к системам, для которых в повседневной жизни нет аналогов. Парадокс Банаха-Тарского гораздо круче парадокса времен ожидания – но кто из нас в жизни сталкивается с разрезанием сферы на не-измеримые куски? Сама постановка задачи уже далеко выходит за рамки повседневного опыта и бытовой интуиции – не удивительно, что результат получается не интуитивный. Но очередь в Сбербанк, и кассир, который делает между клиентами минутную паузу, а иногда выбегает перекурить на 5 минут, а иногда попить чай на 15 – это обыденная ситуация. И оказывается, что в этой обыденной ситуации скрыто такое нетривиальное поведение!

Waiting time paradox #3: сервера и их очереди

Если происходит что-то странное, значит, где-то рядом автобусная остановка
(Народная мудрость)

(Продолжение серии про парадокс времени ожидания. Персонажи выдуманы, цифры получены из симуляции, формулы выведены специально сделанными людьми. В общем, все не по-настоящему, не пытайтесь повторить)

Представьте себе сервер, на который приходят заявки, и очередь, где заявки могут чуток обождать, пока сервер занят с другими заявками. Не хочется тратить CPU на постоянный опрос очереди busy-loop-ом, поэтому сервер обрабатывает те заявки, которые уже накопились в очереди, а как только заявки в очереди заканчиваются – сервер переключается на какие-то фоновые задачи, а потом на sleep(5). Отоспавшись, сервер возвращается к очереди, и если там что-то накопилось – то все это разгребает, и опять уходит заниматься фоновыми делами + sleep(5), а если ничего не накопилось – так сразу уходит заниматься фоновыми делами и спать. Поддерживает разумный work-life balance:

while( true ){
    task = queue.poll()
    if( task != null ) {
        task.doTheNeedful()
    } else {
        doBackgroundJobs()
        sleep(5)
    }
}

(Полный java-код тут, можно поиграться)

Waiting time paradox #2: почему успешный поиск в хэш-таблице дольше не успешного?

…Продолжение предыдущей статьи про waiting time paradox: на этот раз разберемся, почему успешный поиск в хэш-таблице обычно дольше, чем не-успешный

Возьмем классическую хэш-таблицу с разрешением коллизий цепочками: K пар ключ-значение, B корзинок со связными списками для разрешения коллизий, вот это все. Мы ищем в этой таблице разные ключи (а зачем еще нужна хэш-таблица?). Для каких-то ключей в таблице находится соответствие, для каких-то – нет.

Вопрос: что больше – среднее количество сравнений при успешном поиске, или среднее количество сравнений при неуспешном поиске?

Waiting time paradox #1: автобусы, очереди, и хэш-таблицы

Ничего не доводи до крайности: человек, желающий трапезовать слишком поздно, рискует трапезовать на другой день поутру.
(Козьма Прутков)

…парадокс времен ожидания, или почему автобуса приходится ждать дольше, чем казалось бы, почему успешный поиск в хэш-таблице скорее всего медленнее, чем неуспешный, и почему иногда среднее время обработки запроса можно уменьшить, если добавить в цикл обработки паузу (но сегодня только про автобус)

Теория разбитых окон в применении к разработке

В социальной психологии есть такая "теория разбитых окон". Она утверждает, если упрощенно, что бардак который не исправляют — воспроизводит вокруг еще больший бардак. Точнее, утверждается, что человек смотрит на то, в каком состоянии находится его окружение, и интуитивно выводит отсюда неформальные социальные нормы (“как здесь можно себя вести”) — в противовес формальным социальным нормам ("как положено себя вести"). И если окружение показывает, что “здесь можно” бить окна, мусорить, другими способами нарушать формальные нормы, и это никого не волнует (окна не вставляют, мусор не убирают, нарушителей не штрафуют) — человеку психологически проще становится разбить еще одно окно, бросить жевачку на пол, припарковаться в неположенном месте.