Algorytm generowania liczb losowych Open Source w C++?

Question

Potrzebuję generować losowe liczby w zakresie 1 - 10000 w sposób ciągły bez duplikacji. Jakieś rekomendacje?

Opis: budujemy nową wersję dla naszej aplikacji, która utrzymuje rekordy w Sqlite DB. w ostatniej wersji naszej aplikacji nie mieliśmy unikalnego klucza dla każdego rekordu. Ale teraz, gdy mamy nową ulepszoną wersję, musimy obsługiwać funkcję importu z DB ostatniej wersji. Czyniąc to, czytamy każdy rekord ze starego DB i generujemy losową liczbę dla unikalnego klucza i przechowujemy go w nowym DB. Tutaj musimy importować do 10 000 rekordów w sposób ciągły.

Answer 1

Cóż, w końcu musisz albo przestać je generować, albo zamierzasz je duplikować gwiazdą.

Na komputerze opcje są ograniczone do Pseudo losowych generatorów liczb (PRNG), i biorąc pod uwagę ograniczenia, których nigdy nie powtarzają, PRNG jest najlepszą opcją - rzeczywiste losowe dane będą czasami duplikować numer.

W twoim przypadku rozważę użycie dużego PRNG (32-bitowego lub większego) do przetasowania 10 000 numerów, a następnie wysłanie numerów w kolejności losowej.

Po zużyciu można ponownie przetasować - ponieważ PRNG jest tak duży, że będziesz w stanie wielokrotnie przeliczyć numery 10k przed powtórzeniem sekwencji.

Daj nam więcej informacji o tym, co robisz, a my możemy wymyślić lepszą odpowiedź.

-Adam

Answer 2

Mersenne Twister jest obecny najlepiej (choć może być kilka tygodni po sobie żadnych nowych odkryć naprawdę). Źródło w prawie każdym języku jest dostępne gdzieś tam, a MT jest również w Boost here

Answer 3

Boost.Random to dobry wybór i działa dobrze dla mnie. Jeśli jednak nie potrzebujesz wielu generatorów liczb losowych i dystrybucji, możesz poszukać innej biblioteki, aby nie instalować całego pakietu Boost.

Answer 4

Jak losowo? Oczywiście jest tam rand(), są też rzeczy specyficzne dla OS (na przykład Windows ma coś w CryptoAPI). Czy piszesz coś (nie jest to zalecane) lub szukasz już istniejącej funkcji do użycia?

Answer 5

TR1 ma dobrą obsługę liczb losowych - jeśli twój kompilator ją obsługuje.

Inaczej Boost

Jest to w zasadzie to, co stało się TR1.

Jeśli nie otrzymujesz duplikatów - potrzebujesz shuffle. Może to być całkiem proste, ale są pewne pułapki, jeśli nie robisz tego dobrze. Jeff Atwood zrobił piękny napisać jakiś czas temu:

http://www.codinghorror.com/blog/archives/001015.html

Answer 6

mtrand jest miły.

Answer 7

Zwiększenie prawdopodobnie robi coś, co nie gwarantuje żadnych powtarzających się liczb. Ale dla odrobiny zabawy tutaj jest mój pomysł.

Uwaga: nie próbuję generować mojego randa w tym kierunku, ponieważ polega na szaleństwie.

#include <iostream> 
#include <vector> 
#include <algorithm> 


class GaranteedNoRepeatRandom 
{ 
    public: 
     GaranteedNoRepeatRandom(int limit) 
      :data(limit) 
      ,index(0) 
     { 
      for(int loop=0;loop < limit;++loop) 
      { data[loop] = loop; 
      } 
      // Note: random_shuffle optionally takes a third parameter 
      // as the rand number generator. 
      std::random_shuffle(&data[0],&data[0]+limit); 
     } 

     unsigned int rand() 
     { 
      unsigned int result = data[index]; 
      index = (index+1) % data.size(); 

      // Add code to re-shuffle after index wraps around 
      return result; 
     } 
    private: 
     std::vector<unsigned int>    data; 
     std::vector<unsigned int>::size_type index; 
}; 

int main() 
{ 
    GaranteedNoRepeatRandom  gen(10000); 

    for(int loop =0;loop < 10;++loop) 
    { 
     std::cout << gen.rand() << "\n"; 
    } 
} 

Answer 8

Numerical Recipes in C ma cały rozdział poświęcony generowaniu liczb losowych. Jest tam kilka implementacji. Od prostych i prostych do złożonych z dobrymi właściwościami statystycznymi.

Answer 9

Czy można kwestionować cały pomysł wykorzystania liczby losowej jako unikalnego klucza do rekordu bazy danych? Nie jestem zaznajomiony z sqlite, ale warto sprawdzić, czy obsługuje wewnętrznie jakiś unikalny identyfikator kolumny. SQL Server ma na przykład kolumny "tożsamości", a Oracle ma "sekwencje", z których obie służą temu samemu celowi.

Answer 10

Generowanie dużych liczb losowych. Powiedz 128 bitów. Szansa, że ​​dwie takie liczby są takie same w zbiorze 10000, jest śmiesznie mała (rzędu n^2/2^b, gdzie n = liczba potrzebnych liczb i b = liczba użytych bitów). Biorąc pod uwagę wystarczającą liczbę bitów, szanse na to, że twój baran ulegnie uszkodzeniu przez promień kosmiczny, zmniejszy się w porównaniu do szansy, że twój algorytm się nie powiedzie. Uważaj, że przestrzeń, z której losujesz liczby losowe, rzeczywiście ma liczbę bitów, których szukasz. Łatwo mylnie generuje liczby 128-bitowe z puli 32-bitowej (tj. Istnieją tylko 2^32 możliwości, nawet jeśli generujesz numery od 1 do 2^128). Generatory liczb losowych w bibliotece boost mogą zrobić to za Ciebie. BTW: jeśli nie lubisz 128 bitów, użyj 256 bitów lub więcej, aż poczujesz się komfortowo, że nie ma praktycznej szansy na kolizję haszującą. Jeśli musisz zrobić to tylko raz, po prostu użyj metody shuffle wspomnianej już w poprzedniej odpowiedzi. To będzie miało tę zaletę, że generuje doskonały skrót.

Answer 11

http://random.org/ jeśli trzeba naprawdę losowe numery

Answer 12

Choć może masz wymóg generowania sekwencji wartości, które nie powtarzają, nie można nazwać wynik „random”. Prawdziwa losowość ma mniej wspólnego z brakiem powtórzeń, niż z rozkładem wartości w sekwencji.

Answer 13

Jeśli rzeczywiście musi zawierać się w przedziale od 1 do 10,0000 bez powtórzeń, ale nie sekwencyjnie, najlepiej byłoby najpierw utworzyć sekwencyjną tablicę 10000 elementów, a następnie przetasować je.

Muszę jednak zgodzić się z uwagami na oryginalne pytanie. Nie widzę żadnej wartości, czyniąc je niesekwencyjnymi.

Alternatywnie, w unikalnych & niesekwencyjne są ważne, wtedy zakres od 1 do 10 000 staje się wątpliwy. Najlepiej byłoby po prostu użyć GUID.

Answer 14

Generowanie liczb losowych jest zbyt ważne, aby pozostawić je przypadkowi. - Robert R. Coveyou, Krajowe Laboratorium Oak Ridge