18 января 2023 г.

Еще один сценарий для waiting time paradox

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

Сейчас по работе пишу небольшую странично-организованную структуру данных. Записи в ней случайного размера – т.е. не выровнены по границам страниц. Если очередная запись не влезает место, оставшееся на текущей странице, то надо либо разделить ее на две страницы, либо полностью перенести на новую страницу, а на старой оставлять padding-record.

Вариант "переносить полностью" – проще, но часть места непроизводительно теряется. Мне захотелось оценить: насколько большая эта потерянная часть? Если средний размер записи X, то сколько, в среднем, на страницу будет теряться на padding-record?

Интуитивно кажется, что в среднем будет теряться половина средней записи, X/2. Но первая же симуляция показала, что больше X/2.

И тут я вспомнил, где такое видел – это же waiting time paradox. Чтобы увидеть аналогию, пришлось немного переформулировать задачу: пусть случайные размеры записей отложены подряд на прямой. Мы тыкаем в случайную точку на этой прямой ("конец страницы"), и спрашиваем: какое, в среднем, расстояние до предыдущей границы записи?

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

(Еще в той задаче нас интересовало время до следующего автобуса, а здесь время от границы предыдущей записи – но это практически ничего не меняет в вычислениях)

Ответ получается тот же: в среднем теряется $$\frac{E[X]}{2}(1+\frac{D[X]}{E[X]^2})$$ – то есть всегда больше половины среднего размера записи. Если распределение размера записи Пуассоновское, то, в среднем, будет теряться ровно средний размер записи на страницу. Для распределений с бОльшей вариацией – и того больше.