Проблема с мячами в контейнерах

« шары в корзины » (или сбалансированное распределение ) Задача — классическая задача теории вероятностей , имеющая множество приложений в информатике . В задаче участвуют m шаров и n коробок (или «корзин»). Каждый раз в одну из корзин помещается один мяч. После того, как все шары оказались в ящиках, мы смотрим на количество шаров в каждом ящике; мы называем это число нагрузкой на бункер. Задачу можно смоделировать с помощью полиномиального распределения и включить в нее такой вопрос, как: каково ожидаемое количество ящиков с мячом в них?

Очевидно, что можно сделать загрузку минимальной, равной m / n , поместив каждый шар в наименее загруженный контейнер. Интересен случай, когда бин выбирается случайным образом или, по крайней мере, частично случайным образом. Мощная парадигма «шары в мусорные ведра» — это «сила двух случайных выборов». «где каждый шар выбирает две (или более) случайные ячейки и помещается в менее загруженную корзину. Эта парадигма нашла широкое практическое применение в эмуляции общей памяти, эффективных схемах хеширования, рандомизированной балансировке нагрузки задач на серверах и маршрутизации пакеты внутри параллельных сетей и центров обработки данных.

Случайное распределение

Когда контейнер для каждого шара выбирается случайным образом, независимо от других вариантов, максимальная загрузка может достигать $m$. Однако можно вычислить более точную оценку, которая выполняется с высокой вероятностью . «Высокая вероятность» — это вероятность $1-o(1)$, т.е. вероятность стремится к $1$ когда $n$ растет до бесконечности.

Для случая $m=n$, с вероятностью $1-o(1)$ максимальная нагрузка составляет:

${\frac {\log n}{\log \log n}}\cdot (1+o(1))$.

Гонне дал точную оценку ожидаемого значения максимальной нагрузки, которая для $m=n$ является $\Gamma ^{-1}(n)-{\frac {3}{2}}+o(1)$, где $\Gamma ^{-1}$ является обратной гамма -функцией , и она известна что $\Gamma ^{-1}(n)={\frac {\log n}{\log \log n}}\cdot (1+o(1))$.

Максимальная нагрузка также может быть рассчитана для $m\neq n$и, например, для $m>n\log n$ это ${\frac {m}{n}}+\Theta \left({\sqrt {\frac {m\log n}{n}}}\right)$и для $m<n/\log n$ это $\Theta \left({\frac {\log n}{\log(n/m)}}\right)$, с большой вероятностью.

Точные вероятности для малых $m=n$ может быть вычислено как $a(n)/n^{n}$ для $a(n)$ определено в OEIS A208250.

Частично случайное распределение

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

В простейшем случае, если выделить $m$ шары в $n$ контейнеры (с $m=n$) последовательно по одному и для каждого шара выбирают $d\geq 2$ случайные ячейки на каждом шаге, а затем распределяет шар в наименее загруженную из выбранных ячеек (связи разрываются произвольно), тогда с высокой вероятностью максимальная загрузка составит:

${\frac {\log \log n}{\log d}}+\Theta (1)$

что почти экспоненциально меньше, чем при полностью случайном распределении.

Этот результат можно обобщить на случай $m\geq n$ (с $d\geq 2$), когда с большой вероятностью максимальная нагрузка составит:

${\frac {m}{n}}+{\frac {\log \log n}{\log d}}+\Theta (1)$

которая точна с точностью до аддитивной константы. (Все оценки выполняются с вероятностью не менее $1-1/n^{c}$ для любой константы $c>0$.) Обратите внимание, что для $m>n\log n$, процесс случайного распределения дает только максимальную нагрузку ${\frac {m}{n}}+O\left(\log \log n\right)$ с высокой вероятностью, поэтому улучшение между этими двумя процессами особенно заметно при больших значениях $m$.

Другими ключевыми вариантами парадигмы являются «параллельные шары в контейнеры», где $n$ шары выбирают $d$ случайные ячейки параллельно, «взвешенные шары в контейнеры», когда шары имеют неединичный вес, и «шары в контейнеры с удалениями», где мячи можно как добавлять, так и удалять.

Бесконечный поток шариков

Вместо того, чтобы просто класть m шаров, можно рассмотреть бесконечный процесс, в котором на каждом временном шаге добавляется один шар и берется один шар, так что количество шаров остается постоянным. При m = n через достаточно долгое время с высокой вероятностью максимальная нагрузка аналогична конечному варианту, как при случайном распределении, так и при частично случайном распределении.

Повторные попадания мячей в контейнеры

При повторном варианте процесса $m$ шары первоначально распределяются в $n$ ячейками произвольным образом, а затем на каждом последующем шаге процесса с дискретным временем из каждой непустой ячейки выбирается один шар и переназначается в одну из ячеек. $n$ контейнеры равномерно в случайном порядке. Когда $m=n$, показано, что с большой вероятностью процесс сходится к конфигурации с максимальной нагрузкой ${\mathcal {O}}(\log(n))$ после ${\mathcal {O}}(n)$ шаги.

Приложения

Онлайн-балансировка нагрузки : Рассмотрим набор из n одинаковых компьютеров. Имеется n пользователей, которым необходимы вычислительные услуги. Пользователи не скоординированы - каждый пользователь приходит сам и выбирает, какой компьютер ему использовать. Каждому пользователю, конечно, хотелось бы выбрать наименее загруженный компьютер, но для этого необходимо проверять загрузку каждого компьютера, что может занять много времени. Другой вариант — выбрать компьютер наугад; это приводит с большой вероятностью к максимальной нагрузке в ${\frac {\log n}{\log \log n}}\cdot (1+o(1))$. Возможный компромисс заключается в том, что пользователь будет проверять только два компьютера и использовать менее загруженный из двух. Это приводит, с высокой вероятностью, к гораздо меньшей максимальной нагрузке $\log _{2}\log n+\Theta (1)$.

Хеширование : рассмотрим хеш-таблицу , в которой все ключи, сопоставленные с одним и тем же местоположением, хранятся в связанном списке. Эффективность доступа к ключу зависит от длины его списка. Если мы используем одну хэш-функцию, которая выбирает местоположения с одинаковой вероятностью, с высокой вероятностью самая длинная цепочка будет иметь $O\left({\frac {\log n}{\log \log n}}\right)$ ключи. Возможным улучшением является использование двух хэш-функций и помещение каждого нового ключа в более короткий из двух списков. В этом случае с большой вероятностью самая длинная цепочка имеет только $O(\log \log n)$ элементы.

Справедливое разрезание торта : рассмотрим задачу создания частично пропорционального разделения разнородного ресурса между $n$ людей, так что каждый человек получает часть ресурса, который этот человек ценит как минимум $1/an$ от общей суммы, где $a$ — некоторая достаточно большая константа. Протокол Эдмондса-Пруса представляет собой рандомизированный алгоритм , в анализе которого используются аргументы «шары в ячейки».