ZWI #4 – jak wylosować elementy bez powtórzeń

Losowanie bez powtórzeń jest chyba jednym z najczęstszych zadań dla początkujących, zarówno uczących się samodzielnie, jak i na studiach. Często przejawia się w zadaniu typu “utwórz program losujący liczby w Lotto”. Równie często spotykam kod z wydajnością O(evil), którego powstydziłbym się nawet w najbezczelniejszym Lawful Evil – mieszanina randów, srandów, sprawdzania w pętli O(n3) czy wartość jest już znaleziona, alokacji pamięci za pomocą new[] itd.

Jest to w dużej mierze pokłosie sposobu nauczania C++. W tym poście przedstawię proste, czytelne i wydajne sposoby uzyskania tego samego efektu.

Małe zbiory/losujemy większość zbioru

W tym przypadku procedura jest trywialna. Aby uzyskać n elementów zbioru bez powtórzeń:

  1. Wymieszaj kontener zawierający możliwe wartości.
  2. Weź n pierwszych elementów kontenera.

Procedura ta sensowna przede wszystkim, gdy losujemy znaczącą część zbioru (np. 800 milionów z miliarda elementów zbioru). Za to w przypadku małych zbiorów1 wejściowych ewentualna różnica w wydajności względem metody przedstawionej niżej będzie niezauważalna.

W kodzie:

shuffle(lotto.begin(), lotto.end(), random);
copy_n(lotto.begin(), 6, ostream_iterator<int>(cout, ", "));

Pełny przykład (używa przedziału <1, 49>, ale zbiór wejściowy może mieć dowolne wartości):

int main()
{
    vector<int> lotto(49);
    iota(lotto.begin(), lotto.end(), 1);
    mt19937 random{random_device{}()};
 
    shuffle(lotto.begin(), lotto.end(), random);
    copy_n(lotto.begin(), 6, ostream_iterator<int>(cout, ", "));
}

[link]
Przykładowy output:

44, 26, 25, 15, 6, 32,

Duży zbiór liczb do losowania

W przypadku, gdy wejściowy zbiór liczb do losowania jest duży1, procedura losowania n elementów wygląda następująco:

  1. Wylosuj wartość i dodaj ją do zbioru unikalnych wartości już wylosowanych.
  2. Jeśli zbiór już wylosowanych elementów ma mniej niż n elementów – idź do punktu 1.

W kodzie (używa przedziału <0, 109>, zamiast dis(random) można podstawić funkcję zwracającą wartości z dowolnego zbioru):

unordered_set<int> selected;
uniform_int_distribution dis(0, 1000000000);
while(selected.size() < 100)
    selected.insert(dis(random));

Pełny przykład:

int main()
{
    mt19937 random{random_device{}()};
 
    unordered_set<int> selected;
    uniform_int_distribution dis(0, 1000000000);
    while(selected.size() < 100)
        selected.insert(dis(random));
 
    copy(selected.begin(), selected.end(), ostream_iterator<int>(cout, "\n"));
}

[link]

1Co jest zbiorem małym, a co dużym należy zbenchmarkować samodzielnie i może być zależne od maszyny wykonującej kod, ale estymuję, że do kilku megabajtów można na współczesnych komputerach uznać za mały zbiór.

12 thoughts on “ZWI #4 – jak wylosować elementy bez powtórzeń

  1. Jako totalny laik C++owy, chciałbym zapytać tylko tak: Jak robiona jest magia Zbioru Unikalnych Wartości?
    Bo jak rozumiem, niskopoziomowo to musi być jakoś sprawdzane. Więc choć logicznie na poziomie kodu C++ nie widać złożoności, bo jest to 1 operacja dodawania elementu do zbioru, to przecież pod tym jakaś mechanika musi działać. I ona ma jakąś złożoność.

    Podobnie wersja pierwsza, z Pomieszaj Zbiór w Losową Kolejność, też ma jakąś mechanikę mieszania, która też nie ma złożoności O(1) chyba.

    1. Jeśli chodzi o pozostałe komentarze – jak najbardziej, nigdzie nie pisałem, że kod jest O(1).

      W tym poście przedstawię proste, czytelne i wydajne sposoby uzyskania tego samego efektu.

      Co do wydajności rozwiązania pierwszego – to całkiem ciekawa sprawa (benchmarkowałem), ale zdecydowałem, że to materiał na osobnego posta. Ten post jest nastawiony na linkowanie nowicjuszom, którzy piszą po 200 linii zaklęć żeby zrobić to co tutaj robię w 3 zrozumiałych liniach.

      1. A ja nie mówię, że pisałeś cokolwiek 🙂 Ja się właśnie nie znam na C++ i dlatego pytam, nie że się czepiam. Bo ciekawi mnie, jak to się dzieje, że to ma mieć niską złożoność. Ja właśnie z takich aspektów jestem cienki i mnie to zastanawia, no bo czemu coś, co ktoś pisze sam, ma być mocno niewydajne, a jednocześnie coś wbudowane w język ma być wydajne. W sumie to jasne – przewaga Mega Zawodowców nad lamerem, ale w sumie tak sobie teoretyzuję, że chyba powinno się dać napisać to „ręcznie” też podobnie, nie?

        1. Dobrze mówisz – moja propozycja nie ma złożoności lepszej, niż poprawnie napisane ręcznie za pomocą pętli itd. To co napisałem o O(n3) piło do konkretnych bardzo błędnych przykładów 🙂

          Postaram się później poprawić posta, aby to było zapisane klarowniej.

          Przy czym, ogromną zaletą zwięzłego (bez przesady) i idiomatycznego kodu jest jego czytelność i łatwość ewentualnej modyfikacji, a dobre języki pozwalają uzyskać to bez straty wydajności.

          1. Powiem ci, że świat programowania jest zakręcony 🙂 Ja jestem jednym z tych znienawidzonych przez Ciebie co uczą w szkole 🙂 Ale rok temu przesiadłem się na Javę, bo jawiści tak nie krzyczą, że kaleczymy język i że to jest paskudne C with classess z lat 80, a nie porządne C++16. 🙂

            Ale ci powiem, że tak ostatnio sobie przeglądam różne rzeczy z dziedziny modnych frameworków itp. i wszystkie one powstały już po tym, jak ja skończyłem studia. Jedna Java już była jak studiowałem 🙂 No JavaScript też, ale wtedy się w nim robiło Zegarek Na WWW 🙂

            30 lat nauki, jak krew w piach, wszystkiego od nowa się trzeba uczyć ciągle. Matematycy mają prościej, 150 lat wciąż to samo, a nawet coraz mniej, bo program się obcina ciągle.

          2. Niestety, ale tych zmian już żaden człowiek nie ogarnia. To poza zasięgiem.

  2. Ja bym się jednak upierał, że przy losowaniu z miliarda opcji to trzeba by było trochę bardziej pokombinować. W konkretnym przypadku może to nie przeszkadzać, ale ogólnie to, że nie można w ten sposób osiągnąć wszystkich możliwych losowań (no chyba, że mamy jakiś dziwny generator pseudolosowy o okresie ponad 2^1.2e6) stanowi sporą przeszkodę.

    1. Np. mt19937_64? 😉 Ogółem, z benchmarka mi wyszło, że przy losowaniu dużej części zakresu, metoda druga jest mało wydajna, bo jest dużo powtórek (duh). Ale szczegółowe wyniki to materiał na osobnego posta.

Leave a Reply

Your email address will not be published.