Problem z piłkami do koszy

Problem piłek do pojemników (lub zrównoważonych alokacji ) jest klasycznym problemem teorii prawdopodobieństwa , który ma wiele zastosowań w informatyce . Problem dotyczy m piłek i n pudełek (lub „pojemników”). Za każdym razem pojedyncza kula jest umieszczana w jednym z pojemników. Gdy wszystkie kule znajdą się w pojemnikach, patrzymy na liczbę piłek w każdym pojemniku; nazywamy ten numer obciążeniem pojemnika . Problem można modelować za pomocą rozkładu wielomianowego i może wymagać zadania pytania takiego jak: Jaka jest oczekiwana liczba pojemników z kulką w środku?

Oczywiście możliwe jest, aby ładunek był tak mały, jak m / n , umieszczając każdą kulkę w najmniej załadowanym pojemniku. Ciekawym przypadkiem jest sytuacja, gdy kosz jest wybierany losowo lub przynajmniej częściowo losowo. Potężny paradygmat „piłki do koszy” to „moc dwóch losowych wyborów”, w której każda kula wybiera dwa (lub więcej) losowe pojemniki i jest umieszczana w mniej obciążonym pojemniku. Ten paradygmat znalazł szerokie praktyczne zastosowania w emulacjach współdzielonej pamięci, wydajnych schematach mieszania, losowym równoważeniu obciążenia zadań na serwerach oraz routingu pakietów w równoległych sieciach i centrach danych.

Przydział losowy

Gdy pojemnik na każdą piłkę jest wybierany losowo, niezależnie od innych wyborów, maksymalne obciążenie może sięgać nawet ${\ displaystyle m}$ . Jednak możliwe jest obliczenie ściślejszego ograniczenia, które zachodzi z dużym prawdopodobieństwem . „Wysokie prawdopodobieństwo” to prawdopodobieństwo , tj. Prawdopodobieństwo dąży do $-o ($$1)}$ , gdy $.$ do nieskończoności

W przypadku maksymalne obciążenie wynosi ${\ displaystyle m = n}$ z prawdopodobieństwem ${\ displaystyle 1-o (1)}$

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

$\ Displaystyle \ Gamma ^ {$ wartości maksymalnego obciążenia, która Γ $-$$i$ , gdzie jest odwrotnością funkcji gamma że ${\ Displaystyle \ Gamma ^ {- 1} (n) = {\ Frac {\ log n} {\ log \ log n}}\cdot (1+o(1))}$ .

Maksymalne obciążenie można również obliczyć dla ${\ Displaystyle m \ neq n}$ i na przykład dla ${\ Displaystyle m> n \ log n}$ jest to ${\ Displaystyle {\ Frac {m} {n}} + \ Theta \ lewo ({\ sqrt {\ Frac {m \ log n} {n}}} \ prawej)} i$ dla ${\ Displaystyle m <n / \ log n}$ to jest ${\ Displaystyle \ Theta \ lewo ({\ Frac {\ log n} {\ log ( n/m)}}\right)}$ , z dużym prawdopodobieństwem.

$\ Displaystyle a (n )}$ prawdopodobieństwa dla małych $\$ jako $Displaystyle a (n) / n ^ {n}}$ za zdefiniowane w OEIS A208250.

Przydział częściowo losowy

Zamiast po prostu wybierać losowy pojemnik dla każdej piłki, można wybrać dwa lub więcej pojemników dla każdej piłki, a następnie umieścić piłkę w najmniej załadowanym pojemniku. Jest to kompromis pomiędzy alokacją deterministyczną, w której sprawdzane są wszystkie przedziały i wybierany jest najmniej obciążony przedział, a przydziałem całkowicie losowym, w którym wybierany jest jeden przedział bez sprawdzania pozostałych. Ten paradygmat często nazywany „siłą dwóch losowych wyborów” był badany w kilku poniższych ustawieniach.

W najprostszym przypadku, jeśli przydziela się $) sekwencyjnie jeden po$ do ${\$ (z $displaystyle m = n}$ i dla każdej piłki wybiera się ${\ displaystyle d \ geq 2}$ losowe pojemniki na każdym kroku, a następnie przydziela piłkę do najmniej załadowanego z wybranych pojemników (remisy zerwane arbitralnie), to z dużym prawdopodobieństwem maksymalne obciążenie wynosi:

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

co jest prawie wykładniczo mniejsze niż przy całkowicie losowej alokacji.

$}$ przypadek ( $z ), gdy z dużym prawdopodobieństwem maksymalne obciążenie wynosi: m ≥ n {$ \ displaystyle

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

która jest ścisła do stałej addytywnej. ( $)$ granice utrzymują się z prawdopodobieństwem ${\ Displaystyle m> n \ log n}$ stałej $n$ dla , proces alokacji losowej daje tylko maksymalne obciążenie ${\ Displaystyle {\ Frac {m} {n}} + O \ lewo (\ log \ log n \ right)}$ z dużym prawdopodobieństwem, więc poprawa między tymi dwoma procesami jest szczególnie widoczna dla dużych wartości ${\ displaystyle m}$ .

Inne kluczowe warianty paradygmatu to „równoległe kulki do pojemników”, w których $,$ wybierają $pojemniki , „ważone kulki do pojemników”$ w których kulki mają wagę inną niż jednostkowa. oraz „piłki do koszy z usunięciami”, w których można dodawać i usuwać piłki.

Nieskończony strumień piłek

Zamiast po prostu umieszczać m piłek, można rozważyć nieskończony proces, w którym w każdym kroku dodawana jest pojedyncza kula i pobierana jedna kula, tak że liczba piłek pozostaje stała. Dla m = n , po wystarczająco długim czasie, z dużym prawdopodobieństwem, maksymalne obciążenie jest zbliżone do wersji skończonej, zarówno przy alokacji losowej, jak i przy alokacji częściowo losowej.

Powtarzające się piłki do koszy

W powtarzanym $wariancie$ procesu są początkowo rozdzielane w $.$ w dowolny sposób, a następnie na każdym kolejnym etapie procesu w czasie dyskretnym z każdego wybierana jest jedna piłka niepusty pojemnik i ponownie przypisany do jednego z $pojemników$ losowo. Kiedy wykazano, że z dużym prawdopodobieństwem proces zbiega się do konfiguracji z maksymalnym obciążeniem, ${\ Displaystyle {\ mathcal {O}} (\ log (n))}$$\ displaystyle m = n} }$ po krokach ${\ Displaystyle {\ mathcal {O}} (n)} .$

Aplikacje

Równoważenie obciążenia online : rozważ zestaw n identycznych komputerów. Jest n użytkowników, którzy potrzebują usług komputerowych. Użytkownicy nie są skoordynowani - każdy użytkownik przychodzi sam i wybiera, z którego komputera chce korzystać. Każdy użytkownik chciałby oczywiście wybrać najmniej obciążony komputer, ale wymaga to sprawdzenia obciążenia każdego komputera, co może zająć dużo czasu. Inną opcją jest losowy wybór komputera; prowadzi to z dużym prawdopodobieństwem do maksymalnego obciążenia ${\ Displaystyle {\ Frac {\ log n} {\ log \ log n}} \ cdot (1+o(1))}$ . Możliwym kompromisem jest to, że użytkownik sprawdzi tylko dwa komputery i użyje mniej obciążonego z nich. Prowadzi to z dużym prawdopodobieństwem do znacznie mniejszego maksymalnego obciążenia ${\ Displaystyle \ log _ {2} \ log n + \ Theta (1)}$ .

Haszowanie : rozważ tablicę skrótów , w której wszystkie klucze zmapowane do tej samej lokalizacji są przechowywane na połączonej liście. Skuteczność dostępu do klucza zależy od długości jego listy. Jeśli użyjemy pojedynczej funkcji skrótu, która wybiera lokalizacje z jednakowym prawdopodobieństwem, z dużym prawdopodobieństwem najdłuższy łańcuch ma ${\ Displaystyle O \ lewo ({\ Frac {\ log n} {\ log \log n}}\right)}$ klucze. Możliwym ulepszeniem jest użycie dwóch funkcji skrótu i ​​umieszczenie każdego nowego klucza na krótszej z dwóch list. $W$ tylko elementy

Uczciwe krojenie tortu : rozważ problem stworzenia częściowo proporcjonalnego podziału heterogenicznego zasobu między $1$ , tak aby każda osoba otrzymała część zasobu, którą ta osoba ceni jako co najmniej $1/an}$$\$$. Protokół$ sumy, gdzie jest wystarczająco dużą stałą Edmondsa -Pruhsa jest losowym algorytmem , którego analiza wykorzystuje argumenty „piłki do kosza”.