Sequenz von einzigartigen Integers generieren

SeppJ

TGGC schrieb:

std::vector<bool> mit N mal false befuellen. Solange Zufallszahlen erzeugen und ggf. den Eintrag im vector kippen, bis man m Bits gekippt hat. Dann nochmal ueber den vector iterieren und die Zahlen einsammeln. Leider langsam, wenn der vector nicht mehr in den Cache passt.

Großartig. Das vereint alle Nachteile und keine der Vorteile der beiden schon genannten Methoden.

TGGC

Mach einfach mal einen Benchmark...

SeppJ

TGGC schrieb:

Mach einfach mal einen Benchmark...

Wozu Zeit verschwenden?

Solange Zufallszahlen erzeugen und ggf. den Eintrag im vector kippen, bis man m Bits gekippt hat.

Das heißt, wir sind in dem Bereich, wo der random_sample-Code von oben gut wäre, das heißt wir ziehen wenige Zahlen aus einer großen Menge. Aber genau in dem Fall ist

Dann nochmal ueber den vector iterieren und die Zahlen einsammeln.

unendlich schlecht

Ich muss sagen, dass bei dem random_sampling-Code das unordered_set für manche Wertebereiche etwas unglücklich gewählt ist (aber es ist eine exzellente Wahl für die Bereiche, wo dieser Algorithmus gut ist!), vector<bool> wäre da sicherlich besser. Daher kombinieren wir das beste beider Welten:

template <typename Distribution, typename OutIt, typename URNG>
void bobw_random_sample(Distribution&& pool, std::size_t k, OutIt out, URNG g) {
  std::vector<bool> marks(pool.max() + 1);
  std::size_t counter = 0;
  while(counter < k)
    {
      auto elem = pool(g);
      if (!marks[elem])
        {
          ++counter;
          marks[elem] = true;
          *out++ = std::move(elem);         
        }
    }
}

Und da ich tatsächlich zu viel Zeit habe und du mir sonst nicht glauben würdest, mach ich auch einen Benchmark :

#include <random>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <numeric>
#include <iterator>
#include <iostream>
#include <chrono>

template <typename RandomIt, typename URNG>
void partial_shuffle(RandomIt first, RandomIt mid, RandomIt last, URNG&& g) {
  auto n = last - first;
  auto k = mid - first;
  for (decltype(n) i{}; i < k; ++i) {
    auto j = std::uniform_int_distribution<decltype(i)>(i, n - 1)(g);
    using std::swap;
    swap(first, first[j]);
  }
}

template <typename Distribution, typename OutIt, typename URNG>
void random_sample(Distribution&& pool, std::size_t k, OutIt out, URNG g) {
  std::unordered_set<decltype(pool(g))> sample;
  while (sample.size() < k) {
    auto elem = pool(g);
    if (sample.insert(elem).second)
      *out++ = std::move(elem);
  }
}

template <typename Distribution, typename OutIt, typename URNG> 
void tggc_random_sample(Distribution&& pool, std::size_t k, OutIt out, URNG g)
{
  std::vector<bool> marks(pool.max() + 1);
  std::size_t counter = 0;
  while(counter < k)
    {
      auto elem = pool(g);
      if (!marks[elem])
        {
          ++counter;
          marks[elem] = true;
        }
    }
  for (std::size_t i = 1; i < marks.size(); ++i)
    if(marks[i])
      *out++ = i;
}

template <typename Distribution, typename OutIt, typename URNG>
void bobw_random_sample(Distribution&& pool, std::size_t k, OutIt out, URNG g) {
  std::vector<bool> marks(pool.max() + 1);
  std::size_t counter = 0;
  while(counter < k)
    {
      auto elem = pool(g);
      if (!marks[elem])
        {
          ++counter;
          marks[elem] = true;
          *out++ = std::move(elem);         
        }
    }
}

int anti_optimizer;

struct DummyIterator : public std::iterator<std::input_iterator_tag, int>
{
  DummyIterator& operator++(int) { return *this; }
  DummyIterator& operator++() { return *this; }
  int &operator*() { return anti_optimizer; } 
  bool operator==(DummyIterator) {return true;}
  bool operator!=(DummyIterator) {return true;}
};

int main()
{
  size_t Ns[] = {100, 10000, 1000000};
  double k_fractions[] = {0.00001, 0.01, 0.1, 0.3, 0.5, 0.99, 1};
  const size_t total_values_per_measurement = 1000000;

  for (size_t N : Ns)
    {
      for(double fraction : k_fractions)
        {
          size_t k = std::max(1., N * fraction);
          size_t num_measurements = total_values_per_measurement / k;
          std::cout << "Sampling " << k << " values from a set of " << N << ", " << num_measurements << " runs.\n";

          std::chrono::time_point<std::chrono::high_resolution_clock> start, end;
          std::chrono::duration<double> diff;

          std::cout << "Partial shuffle, only one initialization: " << std::flush;
          start = std::chrono::high_resolution_clock::now();
          {
            std::mt19937 rng;
            std::vector<int> v(N);
            std::iota(v.begin(), v.end(), 0);
            for (size_t i = 0; i < num_measurements; ++i)
              {
                partial_shuffle(v.begin(), v.begin()+k, v.end(),
                                rng);
                std::copy(v.begin(), v.begin() + k, DummyIterator());
              }
          }
          end = std::chrono::high_resolution_clock::now();
          diff = end -start;
          std::cout << diff.count() << " s\n";

          std::cout << "Partial shuffle, " << num_measurements << " initializations: " << std::flush;
          start = std::chrono::high_resolution_clock::now();
          {
            std::mt19937 rng;
            for (size_t i = 0; i < num_measurements; ++i)
              {
                std::vector<int> v(N);
                std::iota(v.begin(), v.end(), 0);
                partial_shuffle(v.begin(), v.begin()+k, v.end(),
                                rng);
                std::copy(v.begin(), v.begin() + k, DummyIterator());
              }
          }
          end = std::chrono::high_resolution_clock::now();
          diff = end -start;
          std::cout << diff.count() << " s\n";

          std::cout << "Random sample: " << std::flush;
          start = std::chrono::high_resolution_clock::now();
          {
            std::mt19937 rng;
            for (size_t i = 0; i < num_measurements; ++i)
              {
                random_sample(std::uniform_int_distribution<int>(0, N),
                              k,
                              DummyIterator(),
                              rng);
              }
          }
          end = std::chrono::high_resolution_clock::now();
          diff = end -start;
          std::cout << diff.count() << " s\n";

          std::cout << "TGGC random sample: " << std::flush;
          {
            start = std::chrono::high_resolution_clock::now();
            {
              std::mt19937 rng;
              for (size_t i = 0; i < num_measurements; ++i)
                {
                  tggc_random_sample(std::uniform_int_distribution<int>(0, N),
                                     k,
                                     DummyIterator(),
                                     rng);
                }
            }
            end = std::chrono::high_resolution_clock::now();
            diff = end -start;
            std::cout << diff.count() << " s\n";
          }

          std::cout << "BOBW random sample: " << std::flush;
          start = std::chrono::high_resolution_clock::now();
          {
            std::mt19937 rng;
            for (size_t i = 0; i < num_measurements; ++i)
              {
                bobw_random_sample(std::uniform_int_distribution<int>(0, N),
                                   k,
                                   DummyIterator(),
                                   rng);
              }
          }
          end = std::chrono::high_resolution_clock::now();
          diff = end -start;
          std::cout << diff.count() << " s\n";

          std::cout << '\n';
        }
    }
}

Dabei gehe ich noch nicht einmal in Bereiche, wo der vector<bool> nicht mehr in den Cache passt, da dein Code bereits vorher ewig lang braucht und derart viel Zeit habe ich nun auch nicht.

Auf Intel Xeon E5-2630, Linux, GCC 4.8.2, -O3, -march=native:

Sampling 1 values from a set of 100, 1000000 runs.
Partial shuffle, only one initialization: 0.0351468 s
Partial shuffle, 1000000 initializations: 0.120982 s
Random sample: 0.920079 s
TGGC random sample: 0.990427 s
BOBW random sample: 0.866338 s

Sampling 1 values from a set of 100, 1000000 runs.
Partial shuffle, only one initialization: 0.0301358 s
Partial shuffle, 1000000 initializations: 0.143935 s
Random sample: 1.06762 s
TGGC random sample: 1.13095 s
BOBW random sample: 0.857736 s

Sampling 10 values from a set of 100, 100000 runs.
Partial shuffle, only one initialization: 0.0252646 s
Partial shuffle, 100000 initializations: 0.0353536 s
Random sample: 0.172217 s
TGGC random sample: 0.140645 s
BOBW random sample: 0.113565 s

Sampling 30 values from a set of 100, 33333 runs.
Partial shuffle, only one initialization: 0.0287533 s
Partial shuffle, 33333 initializations: 0.0327869 s
Random sample: 0.152243 s
TGGC random sample: 0.0695046 s
BOBW random sample: 0.0674652 s

Sampling 50 values from a set of 100, 20000 runs.
Partial shuffle, only one initialization: 0.0288363 s
Partial shuffle, 20000 initializations: 0.0312335 s
Random sample: 0.165383 s
TGGC random sample: 0.0570109 s
BOBW random sample: 0.053697 s

Sampling 99 values from a set of 100, 10101 runs.
Partial shuffle, only one initialization: 0.0256634 s
Partial shuffle, 10101 initializations: 0.0268395 s
Random sample: 0.300453 s
TGGC random sample: 0.159784 s
BOBW random sample: 0.152899 s

Sampling 100 values from a set of 100, 10000 runs.
Partial shuffle, only one initialization: 0.0286215 s
Partial shuffle, 10000 initializations: 0.0299062 s
Random sample: 0.302661 s
TGGC random sample: 0.14455 s
BOBW random sample: 0.131451 s

Sampling 1 values from a set of 10000, 1000000 runs.
Partial shuffle, only one initialization: 0.0250974 s
Partial shuffle, 1000000 initializations: 3.37695 s
Random sample: 0.962589 s
TGGC random sample: 12.2757 s
BOBW random sample: 0.836378 s

Sampling 100 values from a set of 10000, 10000 runs.
Partial shuffle, only one initialization: 0.025808 s
Partial shuffle, 10000 initializations: 0.0581827 s
Random sample: 0.13377 s
TGGC random sample: 0.133567 s
BOBW random sample: 0.0335073 s

Sampling 1000 values from a set of 10000, 1000 runs.
Partial shuffle, only one initialization: 0.0240312 s
Partial shuffle, 1000 initializations: 0.0272194 s
Random sample: 0.134308 s
TGGC random sample: 0.0404197 s
BOBW random sample: 0.0306364 s

Sampling 3000 values from a set of 10000, 333 runs.
Partial shuffle, only one initialization: 0.0255193 s
Partial shuffle, 333 initializations: 0.0295867 s
Random sample: 0.177201 s
TGGC random sample: 0.0453135 s
BOBW random sample: 0.0413618 s

Sampling 5000 values from a set of 10000, 200 runs.
Partial shuffle, only one initialization: 0.0294282 s
Partial shuffle, 200 initializations: 0.0294346 s
Random sample: 0.188878 s
TGGC random sample: 0.0531995 s
BOBW random sample: 0.0512393 s

Sampling 9900 values from a set of 10000, 101 runs.
Partial shuffle, only one initialization: 0.0286714 s
Partial shuffle, 101 initializations: 0.0295238 s
Random sample: 0.335118 s
TGGC random sample: 0.134744 s
BOBW random sample: 0.146386 s

Sampling 10000 values from a set of 10000, 100 runs.
Partial shuffle, only one initialization: 0.0286799 s
Partial shuffle, 100 initializations: 0.0295326 s
Random sample: 0.48584 s
TGGC random sample: 0.255721 s
BOBW random sample: 0.246279 s

Sampling 10 values from a set of 1000000, 100000 runs.
Partial shuffle, only one initialization: 0.0323859 s
Partial shuffle, 100000 initializations: 41.7274 s
Random sample: 0.169453 s
TGGC random sample: 105.731 s
BOBW random sample: 0.531802 s

Sampling 10000 values from a set of 1000000, 100 runs.
Partial shuffle, only one initialization: 0.0272863 s
Partial shuffle, 100 initializations: 0.0629503 s
Random sample: 0.146155 s
TGGC random sample: 0.124736 s
BOBW random sample: 0.0274358 s

Sampling 100000 values from a set of 1000000, 10 runs.
Partial shuffle, only one initialization: 0.0256908 s
Partial shuffle, 10 initializations: 0.029186 s
Random sample: 0.19917 s
TGGC random sample: 0.0457376 s
BOBW random sample: 0.0346712 s

Sampling 300000 values from a set of 1000000, 3 runs.
Partial shuffle, only one initialization: 0.0278852 s
Partial shuffle, 3 initializations: 0.0287048 s
Random sample: 0.267522 s
TGGC random sample: 0.0383906 s
BOBW random sample: 0.044275 s

Sampling 500000 values from a set of 1000000, 2 runs.
Partial shuffle, only one initialization: 0.0323308 s
Partial shuffle, 2 initializations: 0.0316727 s
Random sample: 0.367058 s
TGGC random sample: 0.0540272 s
BOBW random sample: 0.0523345 s

Sampling 990000 values from a set of 1000000, 1 runs.
Partial shuffle, only one initialization: 0.0317248 s
Partial shuffle, 1 initializations: 0.0306744 s
Random sample: 0.968446 s
TGGC random sample: 0.174604 s
BOBW random sample: 0.137099 s

Sampling 1000000 values from a set of 1000000, 1 runs.
Partial shuffle, only one initialization: 0.0314126 s
Partial shuffle, 1 initializations: 0.0278218 s
Random sample: 2.7555 s
TGGC random sample: 0.383866 s
BOBW random sample: 0.36989 s

Lehren die wir daraus ziehen können:*

** partial_shuffle ist immer ungefähr gleich schnell, sofern man die Einmalkosten vernachlässigt. Offensichtlicherweise, denn so ist das Ding gebaut.

Es gibt ein paar Eingabemengen, wo dein Code schneller ist als der random_sample-Code, weil das unordered_set diesen Vorschlag in diesen Bereichen runter zieht.
** In diesen Fällen ist der random_sample-Code mit vector<bool> aber stets besser als dein Vorschlag (überhaupt ist dieser Code [i]immer besser als dein Vorschlag).
vector<bool> ist aber nicht immer besser als unordered_set. Das unordered_set wird gut, wenn N groß ist. Was auch genau der Fall ist, wo dieser Code sowieso gut ist (sofern k klein bleibt), daher will ich die Wahl von unordered_set nicht runter machen, sie ist bloß ungeschickt für kleine bis mittlere N. Aber dann nimmt man ohnehin besser den partial_shuffle.
Wenn dein Code langsam ist, dann ist er richtig langsam, selbst langsamer als der random_sample bei einmaliger Anwendung in den Bereichen, wo dieser richtig schlecht ist:

Partial shuffle, only one initialization: 0.0323859 s
Partial shuffle, 100000 initializations: 41.7274 s
Random sample: 0.169453 s
TGGC random sample: 105.731 s
BOBW random sample: 0.531802 s

Tatsächlich ist bei den hier gezeigten Werten immer der partial_shuffle am schnellsten, sofern man die Einmalkosten vernachlässigen kann (d.h. wenn man oftmals die gleiche Menge sampelt). Man müsste also zu noch extremeren Werten gehen als hier im Benchmark, damit die anderen Algorithmen besser als partial_shuffle werden, irgendwo, wo die Notwendigkeit der Speicherung der Werte ein Nachteil wird. Das sind dann aber die Werte, wo der vector<bool> ebenfalls stinkt und der random_sample mit unordered_set gewinnen wird.
An keiner Stelle ist dein Vorschlag am besten (selbst wenn man meinen BOBW-Vorschlag ignoriert oder beim random_shuffle die Einmalkosten nicht vernachlässigen kann). Dafür gibt es auch eine Erklärung: Dein Code muss bei jedem Lauf O(N) Speicher allokieren und initialisieren. Er hat jedes Mal mindestens Einmalkosten von O(N) in der Laufzeit für das Iterieren und O(k) für das Generieren, sofern k << N. Und statt O(k) kann man da was richtig großes bekommen, wenn k nahe N ist. Der partial_shuffle muss (einmalig) O(N) allokieren und initialisieren, läuft dann in stets in O(k). Der random_sample muss O(k) allokieren und läuft für k << N in O(k) und hat das gleiche schlechte Verhalten bei k ~ N wie dein Code. Daher mein Kommentar, dass dein Code die Nachteile beider Vorschläge vereinigt. Und irgendwelche Träume, dass die kleinen Konstanten beim vector<bool> an irgendeiner Stelle einen Vorteil bringen, bewahrheiten sich nicht, wie der Benchmark zeigt. Jeweils einer der anderen Codes ist immer besser, meistens sogar alle.

TGGC

Vielleicht haettest du dir vorher mal ueberlegen sollen, ob wir ueberhaupt ueber das Gleiche reden. Ich ging davon aus, das mit Sequenz gemeint ist, das die Zahlen aufsteigend sind. Dein bemaengeltes iterieren ist gerade dafuer da, diese aufsteigende Sequenz zu erzeugen (was immer eine effiziente Methode des Sortierens ist, wenn nicht m<<N). Ist das nicht noetig, ist die Implementation meines Vorschlags natuerlich einfach bobw_random_sample. Verbuch doch einfach fuer dich, das du jetzt weisst, das ein std::vector<bool> ein set vielen Faellen schlagen kann, auch wenn du erst dachtest "toll noch einen Nachteil eingebaut". Dein partial Shuffle Ansatz ist super, wenn fast alle Zahlen des Arrays gebraucht werden oder man tatsaechlich sehr viele der Sequenzen erzeugen will, das ist klar. Aber der andere Ansatz hat eben auch seine Anwendungsfaelle.

Nicht streiten. Ich schicke hier auch noch einen Vorschlag ins Rennen:

So wie out eine Liste von Zufallszahlen erzeugen, dann sortieren und die Zahlen mit folgendem Algorithmus eindeutig machen:

for (int i = 1; i != M; ++i) ar[i] += i;

SeppJ

TGGC schrieb:

Vielleicht haettest du dir vorher mal ueberlegen sollen, ob wir ueberhaupt ueber das Gleiche reden. Ich ging davon aus, das mit Sequenz gemeint ist, das die Zahlen aufsteigend sind.

Woher soll ich wissen, dass du dir ein ganz anderes Problem überlegt hast, als alle anderen Teilnehmer im Thread?

Verbuch doch einfach fuer dich, das du jetzt weisst, das ein std::vector<bool> ein set vielen Faellen schlagen kann,

Nur damit das klar ist, ich weiß jetzt das Gegenteil. Ich hätte vor dem Benchmark erwartet, dass der vector<bool> bei "normalen" Werten immer gewinnt. Ich bin ein großer Fan von vector<bool> für Anwendungsfälle wie diesem. Aber in Zukunft sollte ich wohl öfters auch unordered_set in Betracht ziehen.

xgrif schrieb:

dann sortieren

Das deutet fast immer auf einen Fehler beim Entwurf eines Algorithmus hin, wenn man zwischendurch etwas sortieren muss, ohne dass es primär um das Sortieren an sich geht. Deinen Vorschlag könnte man z.B. ganz leicht verbessern, indem man die Zahlen sofort in eine sortierte Datenstruktur einfügt. Dann kann man sie auch gleich eindeutig machen, indem man Kollisionen abfängt (sprich: Benutz ein set!).

Außerdem funktioniert dein Algorithmus nicht, weil dein Uneindeutigmacher nicht richtig funktioniert, aber das wäre behebbar. Probleme, die du noch lösen musst: Was ist, wenn a[i] + i größer ist als das Maximum? Was ist, wenn a[i] + i bereits vorhanden ist?

Man darf im ersten Schritt nur Zahlen zwischen 1 und N-M+1 erzeugen, a[i]+i kann nicht bereits vorhanden sein (bzw. macht das nichts, da für i < j aus a[i] <= a[j] folgt a[i]+i < a[j]+j und auch wenn a[i]+i mit a[j] kollidieren mag, kollidiert es nicht mehr mit dem schlussendlichen a[j]+j).

xgrif schrieb:

Man darf im ersten Schritt nur Zahlen zwischen 1 und N-M+1 erzeugen, a[i]+i kann nicht bereits vorhanden sein (bzw. macht das nichts, da für i < j aus a[i] <= a[j] folgt a[i]+i < a[j]+j und auch wenn a[i]+i mit a[j] kollidieren mag, kollidiert es nicht mehr mit dem schlussendlichen a[j]+j).

Und was ist mit a[1]=3 und a[2]=2?

Namal schrieb:

Sequenz von einzigartigen Integers generieren

Tut mir leid, aber es wurden schon alle einzigartigen Integers generiert, es sind keine mehr für dich übrig.

keksampel schrieb:

xgrif schrieb:

Man darf im ersten Schritt nur Zahlen zwischen 1 und N-M+1 erzeugen, a[i]+i kann nicht bereits vorhanden sein (bzw. macht das nichts, da für i < j aus a[i] <= a[j] folgt a[i]+i < a[j]+j und auch wenn a[i]+i mit a[j] kollidieren mag, kollidiert es nicht mehr mit dem schlussendlichen a[j]+j).

Und was ist mit a[1]=3 und a[2]=2?

Dann war die Liste nicht sortiert.

krümelkacker

Für kleine Mengen ist das voll OK mit shuffle oder partial_shuffle .

Für große Mengen kann man das auch anders machen, ohne dabei O(N) Speicher zu verbrauchen. Hier das Rezept für 'ne pseudozufällige Permutation von [0,N) für große N:

b = ceil(log2(N)); // Anzahl der benötigten Bits
Konstruiere eine Blockchiffre e mit Blockgröße b
Wähle einen Schlüssel k zufällig aus.
Iteriere über alle p von einschließlich 0 bis ausschließlich 2^b:
c = e_k(p); // Verschlüssele p mit e und k
Gib c aus, falls c < N

"Konstruiere eine Blockchiffre" klingt komplizierter als es ist. Es muss ja weder besonders effizient noch besonders sicher sein. Das, was sich hier anbietet ist eine Feistechiffre, wo man einfach eine schon vorhandene kryptographische Hashfunktion gefolgt vom Wegschneiden unbenötigter Bits als F nehmen kann, also z.B. die ersten Bits von SHA1(schluessel | rundennummer | haelfte_des_zustands), wobei der vertikale Strich hier das Aneinanderhängen von Bitstrings bedeuten soll. Ich empfehle 5 oder mehr Runden.

So, könnte man z.B. auf einem kleinen embedded MP3-Player eine Shuffle-Funktion bauen, wo sich der Player nur den Schlüssel k und die Position p merken muss, statt eine komplette Liste von Indizes.

krümelkacker schrieb:

So, könnte man z.B. auf einem kleinen embedded MP3-Player eine Shuffle-Funktion bauen, wo sich der Player nur den Schlüssel k und die Position p merken muss, statt eine komplette Liste von Indizes.

Und? Bei shuffle etc. muss man sich auch nur den Seed des Zufallszahlengenerators merken.

Namal

SeppJ schrieb:

Man müsste also zu noch extremeren Werten gehen als hier im Benchmark, damit die anderen Algorithmen besser als partial_shuffle werden, irgendwo, wo die Notwendigkeit der Speicherung der Werte ein Nachteil wird.

Ich hab jetzt gemerkt bei meiner Simulation, dass bei 3 aus 1000000 und das 4,2 Millionen mal partial shuffle dafür ca 12 Stunden brauchen würde. Allerdings sind diese 1 Million Zahlen bei jedem Schritt unterschiedlich (zufällig negativ oder positiv). Ist das hier so ein Fall bei dem ich random_sample nehmen sollte?

Ich kenn mich leider noch nicht soviel mit Templates und Iteratoren aus. Kann mir jemand bitte erklären wie ich das Ergebnis von random_sample in einen vektor speichern kann? (der Rechner hier hat gcc 4.4.7 und kann den neuen C++11 kram noch nicht).

Außerdem, was macht genau das doppelte & bei den übergebenen Parametern? ich hab das bei dem partial_shuffle mit einem und doppeltem ausprobiert und es gab keinen Unterschied.

SeppJ

Namal schrieb:

Ich hab jetzt gemerkt bei meiner Simulation, dass bei 3 aus 1000000 und das 4,2 Millionen mal partial shuffle dafür ca 12 Stunden brauchen würde.

Die Zeit kommt mir aber sehr lang vor, vermutlich machst du andere Dinge falsch/ungünstig:
-Hast du auch Optimierungen angestellt bei deinen Messungen?
-Generierst du die Zahlen 1-1000000 jedes Mal neu? Du kannst sie doch einfach wiederverwenden!

Allerdings sind diese 1 Million Zahlen bei jedem Schritt unterschiedlich (zufällig negativ oder positiv).

Erzähl mal mehr.

Ist das hier so ein Fall bei dem ich random_sample nehmen sollte?

Probier's doch aus.

Ich kenn mich leider noch nicht soviel mit Templates und Iteratoren aus. Kann mir jemand bitte erklären wie ich das Ergebnis von random_sample in einen vektor speichern kann? (der Rechner hier hat gcc 4.4.7 und kann den neuen C++11 kram noch nicht).

Ein back_inserter böte sich an, dann brauchst du gar nichts umzuschreiben.

Außerdem, was macht genau das doppelte & bei den übergebenen Parametern? ich hab das bei dem partial_shuffle mit einem und doppeltem ausprobiert und es gab keinen Unterschied.

Das ist eine rvalue-Referenz. Das zu erklären würde den Rahmen des Forums sprengen. Es ist (hier) eine Mikrooptimierung. Oder eher die Chance einer Mikrooptimierung. Du kannst es einfach weglassen. Ich persönlich hätte es hier niemals benutzt, wenn der Originalposter des Codes es nicht schon so gemacht hätte.

SeppJ schrieb:

Außerdem, was macht genau das doppelte & bei den übergebenen Parametern? ich hab das bei dem partial_shuffle mit einem und doppeltem ausprobiert und es gab keinen Unterschied.

Das ist eine rvalue-Referenz. Das zu erklären würde den Rahmen des Forums sprengen. Es ist (hier) eine Mikrooptimierung. Oder eher die Chance einer Mikrooptimierung. Du kannst es einfach weglassen. Ich persönlich hätte es hier niemals benutzt, wenn der Originalposter des Codes es nicht schon so gemacht hätte.

Tatsächlich handelt es sich hier um Perfect Forwarding weil URNG ein Template Parameter ist. Ich hätte es an dieser Stelle auch nicht verwendet, obwohl z.B. die std::shuffle Funktion das genauso macht. Außerdem ist partial_user in seinem Code nicht sehr konsistent, da er einmal Perfect Forwaring und andermal einfach Call by Value macht. Das sollte man bei dem Zufallszahlengenerator auf keinen Fall machen, da man dann eine Kopie vom originalen Generator erstellt (kostet erstmal Zeit) und außerdem kriegt man dann bei jedem Funktionsaufruf die gleichen Werte, da der originale Generator nie verändert wird. Meine Empfehlung wäre daher den RNG einfach als normale Reference zu übergeben. Das ist dann fast wie Perfect Forwarding, außer das man die Funktion nicht mit temporären Objekten aufrufen kann was meiner Meinung nach bei einem RNG sowieso wenig Sinn macht.

Columbo

Das sollte man bei dem Zufallszahlengenerator auf keinen Fall machen, da man dann eine Kopie vom originalen Generator erstellt (kostet erstmal Zeit) und außerdem kriegt man dann bei jedem Funktionsaufruf die gleichen Werte, da der originale Generator nie verändert wird.

Dafür gibt es reference_wrapper . Was aber natürlich nicht bei jedem Aufruf nötig sein sollte.

sebi707 schrieb:

Außerdem ist partial_user in seinem Code nicht sehr konsistent, da er einmal Perfect Forwaring und andermal einfach Call by Value macht.

Das habe ich schlicht und einfach vergessen. Ich war erstaunt, dass SeppJ das bei seinen Messungen nicht gemerkt hat, habe aber nichts gesagt.war

Perfect Forwarding ist hier einfach angenehm, da ich dann bei Bedarf einen temporären Generator gleich im Argument konstruieren kann und das habe ich auch schon ein paar mal gemacht.