Losowy Podzbiór Ważonych Elementów

Opis algorytmu

algorytm zakłada, że możliwych priorytetów jest skończona liczba, wstępnie od P1 do P5.

1. Oryginalny zbiór można postrzegać jako elementy ułożone na linii, gdzie waga (priorytet) elementu stanowi jego długość

2. Pogrupować i posortować elementy po ich wadze (priorytecie)
3. Zapisać elementy w oddzielnych listach per waga (priorytet)

4. N razy (gdzie N to liczba elementów jakie chcemy otrzymać):
   1. Wylosować punkt na powyższej linii (liczbę od 0 do sumy wag wszystkich elementów)
   2. Policzyć przedziały list z kroku 3 na linii (count listy razy jej waga)
   3. Znaleźć element który leży w tym punkcie (patrz poniżej)
   4. Skrócić linię (zakres losowania) o wagę wylosowanego elementu

Szczegóły kroku 4.iii

Na podstawie przedziałów z 4.ii określić w której liście jest wylosowany element/punkt.

Rozpatrywać tę listę jako krótszy odcinek na linii.
Odległość wylosowanego punktu od początku tego odcinka, podzielić przez wagę (np. 1.2)
Otrzymujemy indeks elementu na tej liście - to jest nasz wylosowany element.

Benchmark

Method	Job	Runtime	Mean	Error	StdDev	Allocated
Pick50	.NET 6.0	.NET 6.0	384.7 us	2.37 us	2.22 us	625 B
Pick50	.NET 7.0	.NET 7.0	353.6 us	2.95 us	2.76 us	625 B

Rozkład / Distribution

Rozkład wylosowanych elementów, pogrupowane po ich wadze. Wybiera 50 elementów ze zbioru 10 tys.
10 mln powtórzeń:

Random Subset Of Weighted Elements

Algorithm description

the algorithm assumes that there's a finite number of possible priorities - tentatively P1 to P5

1. The original set can be considered as elements laid out on a line, where the element's weight (priority) determines its length

2. Group and sort the elements by their weight (priority)
3. Store the elements in separate lists per weight (priority)

4. N times (where N is the number of elements we wish to retrieve):
   1. Pick a random point on the line (number between 0 and the sum of all elements' weights)
   2. Calculate the ranges of the lists from step 3 (list's count times its weight)
   3. Find out which element lies on this point (see below)
   4. Shorten the line (the randomisation range) by the weight of the picked element

Details of step 4.iii

Based on the ranges from step 4.ii determine on which list the element/point lies. Consider this list as a line segment on the main line.
Divide the distance of the point from this segment's start, by this list's weight (eg. 1.2)
This gives us the index of the element on this list - that's our randomly picked element.