Sequenz von einzigartigen Integers generieren

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.