Sequenz von einzigartigen Integers generieren

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.