Nachdem ich diese Frage gelesen hatte, begann ich mich zu fragen: ist es möglich Haben Sie einen Shuffling-Algorithmus, der die ursprüngliche Liste nicht ändert oder kopiert?
Um es klar zu machen:
Stellen Sie sich vor, Sie erhalten eine Liste von Objekten. Die Listengröße kann beliebig sein, aber angenommen, sie ist ziemlich groß (sagen wir 10.000.000 Elemente). Sie müssen die Elemente der Liste in zufälliger Reihenfolge ausdrucken, und Sie müssen es so schnell wie möglich tun. Sie sollten jedoch nicht:
Ist das möglich?
Hinzugefügt: Weitere Erläuterungen.
Added 2 : OK, lassen Sie es uns so sagen: Sie haben eine 1TB HDD mit Datenelementen gefüllt, die jeweils 512 Bytes groß sind (ein einzelner Sektor). Sie möchten alle diese Daten auf eine andere 1 TB HDD kopieren, während Sie alle Elemente mischen. Sie möchten dies so schnell wie möglich machen (einmaliger Durchlauf über Daten usw.). Sie haben 512 MB RAM verfügbar und zählen nicht auf Swap. (Dies ist ein theoretisches Szenario, ich habe so etwas in der Praxis nicht. Ich möchte nur den perfekten algorithm.item finden.)
Hier ist ein sehr einfacher Beweis, dass kein PRNG-Schema funktionieren kann:
Die PRNG-Idee hat zwei Phasen: Wählen Sie zuerst einen PRNG und seinen Anfangszustand; Zweitens, verwenden Sie den PRNG, um die Ausgabe zu mischen. Nun, es gibt N! mögliche Permutationen, also brauchst du mindestens N! verschiedene mögliche Start-Zustände, um Phase 2 zu betreten. Das bedeutet, dass du zu Beginn von Phase 2 musst habe mindestens log 2 N! Statusbits, was nicht erlaubt ist.
Dies schließt jedoch keine Schemata aus, bei denen der Algorithmus neue zufällige Bits von der Umgebung empfängt, während er läuft. Es könnte zB eine PRNG geben, die ihren ursprünglichen Zustand träge liest und dennoch garantiert nicht wiederholt wird. Können wir beweisen, dass es nicht ist?
Angenommen, wir haben einen perfekten Shuffling-Algorithmus. Stellen Sie sich vor, wir fangen an, es zu starten, und wenn es halb fertig ist, legen wir den Computer in den Ruhezustand. Jetzt wurde der vollständige Status des Programms irgendwo gespeichert. Sei S die Menge aller möglichen Zustände, in denen sich das Programm bei dieser Halbzeitmarke befinden könnte.
Da der Algorithmus korrekt ist und garantiert beendet wird, gibt es eine Funktion f , die angesichts des gespeicherten Programmstatus plus einer ausreichend langen Bitfolge eine gültige Folge von Lese- und Schreibvorgängen erzeugt das Mischen. Der Computer selbst implementiert diese Funktion. Aber betrachten Sie es als eine mathematische Funktion:
f : (S × Bits) → Folge von Lese- und Schreibvorgängen
Dann gibt es, trivialerweise, eine Funktion g , die, wenn nur der gespeicherte Programmzustand ist, den Satz von Speicherplätzen erzeugt, die noch gelesen und geschrieben werden müssen. (Übergeben Sie einfach eine beliebige Bitfolge an f und sehen Sie sich die Ergebnisse an.)
g : S → Menge der zu lesenden und zu schreibenden Speicherorte
Das verbleibende Bit des Beweises soll zeigen, dass die Domäne von g mindestens N
Ich bin mir nicht sicher, wie ich das letzte Bit beweisen soll, da entweder die Menge der zu lesenden Orte oder die Menge der Orte ist -to-write kann abhängig vom Algorithmus eine niedrige Entropie sein. Ich vermute, dass es ein offensichtliches Prinzip der Informationstheorie gibt, das den Knoten lösen kann. Markieren Sie dieses Community-Wiki in der Hoffnung, dass jemand es liefern wird.
Nun, es hängt ein bisschen davon ab, welche Art von Zufälligkeit Sie außer dem Mischen, d. h. sollten alle Mischbewegungen wahrscheinlich sein sollen, oder kann die Verteilung verzerrt sein.
Es gibt mathematische Möglichkeiten, um "zufällig aussehende" Permutationen von N ganzen Zahlen zu erzeugen. Wenn P also eine solche Permutation von 0..N-1 bis 0..N-1 ist, können Sie einfach x von 0 bis N durchlaufen -1 und Ausgabe Listenelement L (P (x)) anstelle von L (x) und Sie haben ein Mischen erhalten. Solche Permutationen können z.B. mit modularen Arithmetik. Wenn zum Beispiel N eine Primzahl ist, ist P (x) = (x * k) mod N eine Permutation für irgendeinen 0 & lt; k & lt; N (aber Karten 0 bis 0). Ähnlich für eine Primzahl N, zum Beispiel P (x) = (x ^ 3) mod N sollte eine Permutation sein (aber bildet 0 bis 0 und 1 bis 1 ab). Diese Lösung kann leicht zu Nicht-Primzahl-N erweitert werden, indem die niedrigste Primzahl über N (Nennen M), Permute bis M und Verwerfen der permutierten Indizes über N (ähnlich wie unten) gewählt wird.
Es sollte beachtet werden, dass die modulare Exponentiation die Grundlage für viele kryptographische Algorithmen (z. B. RSA, Diffie-Hellman) ist und von den Experten auf diesem Gebiet als eine stark pseudozufällige Operation angesehen wird.
Ein weiterer einfacher Weg (ohne Primzahlen) besteht darin, zuerst die Domäne zu erweitern, so dass Sie anstelle von N M betrachten, wobei M die kleinste Potenz von zwei über N ist. Wenn N = 12 ist, setzen Sie M = 16. Dann verwenden Sie bijektive Bitoperationen, z. B.
%Vor%Wenn Sie dann Ihre Liste ausgeben, iterieren Sie x von 0 bis M-1 und geben L (P (x)) nur dann aus, wenn P (x) tatsächlich & lt; N.
Eine "wahre, unverzerrte zufällige" Lösung kann konstruiert werden, indem eine kryptographisch starke Blockchiffre (z. B. AES) und ein zufälliger Schlüssel (k) festgelegt und dann die Sequenz
iteriert wird %Vor%und Ausgabe des entsprechenden Elements aus der Sequenz, wenn AES (k, i) & lt; N. Dies kann im konstanten Raum erfolgen (der interne Speicher, der von der Chiffre benötigt wird) und ist von einer zufälligen Permutation (aufgrund der kryptografischen Eigenschaften der Chiffre) nicht unterscheidbar, aber offensichtlich sehr langsam. Im Falle von AES müssten Sie iterieren, bis i = 2 ^ 128.
Sie dürfen keine Kopie erstellen, ändern oder verfolgen, welche Elemente Sie besucht haben. Ich werde sagen, dass es nicht möglich ist. Es sei denn, ich missverstanden Ihre dritten Kriterien.
Ich nehme an, dass Sie nicht sagen dürfen, ein Array von 10.000.000 entsprechenden booleschen Werten zu erstellen, die auf "true" gesetzt werden, wenn Sie das entsprechende Element gedruckt haben. Und Sie dürfen keine Liste der 10.000.000 Indizes erstellen, die Liste mischen und die Elemente in dieser Reihenfolge ausdrucken.
Diese 10.000.000 Elemente sind nur Referenzen (oder Zeiger) auf tatsächliche Elemente, daher wird Ihre Liste nicht so groß sein. Nur ~ 40 MB bei 32-Bit-Architektur für alle Referenzen + Größe der internen Variablen dieser Liste. Wenn Ihre Artikel kleiner als die Referenzgröße sind, kopieren Sie einfach die ganze Liste.
Es ist nicht möglich, dies mit einem wirklich Zufallsgenerator zu tun, da Sie entweder:
müssenDas sind keine Möglichkeiten in Ihrer Frage, also muss ich sagen "nein, das geht nicht".
Was ich in diesem Fall bevorzugen würde, ist eine Bitmaske der verwendeten Werte, aber nicht mit Überspringen, da, wie erwähnt, die Laufzeiten schlechter werden, wenn sich die verwendeten Werte ansammeln.
Eine Bit-Maske ist wesentlich besser als die ursprüngliche Liste von 39 GB (10 Millionen Bits ist nur etwa 1,2 Millionen), viele Größenordnungen weniger als Sie angefordert haben, obwohl es immer noch O (n) ist.
Um das Laufzeitproblem zu umgehen, erzeugen Sie immer nur eine Zufallszahl und wenn das entsprechende "used" -Bit bereits gesetzt ist, scannen Sie vorwärts durch die Bitmaske, bis Sie eine gefunden haben, die nicht
Das heißt, Sie werden nicht herumhängen, verzweifelt nach dem Zufallszahlengenerator, um Ihnen eine Nummer zu geben, die noch nicht benutzt wurde. Die Laufzeiten werden immer nur so schlecht sein wie die Zeit für das Scannen von 1.2M Daten.
Das bedeutet natürlich, dass die gewählte Nummer zu jeder Zeit auf der Grundlage der bereits gewählten Zahlen verzerrt ist. Da diese Zahlen jedoch zufällig sind, ist die Verzerrung zufällig (und wenn die Zahlen nicht sind) wirklich zufällig zu Beginn, dann ist die Verzerrung nicht wichtig).
Und Sie könnten sogar die Suchrichtung wechseln (nach oben oder unten scannen), wenn Sie ein bisschen mehr Abwechslung möchten.
Fazit: Ich glaube nicht, dass das, was du verlangst, machbar ist, aber bedenke, dass ich mich vorher geirrt habe, wie meine Frau es schnell und häufig bestätigen wird :-) Aber wie bei allen Dingen auch normalerweise Wege, um solche Probleme zu umgehen.
Es klingt unmöglich.
Aber 10.000.000 64-Bit-Zeiger sind nur etwa 76 MB.
Ein lineares Rückkopplungs-Schieberegister kann ziemlich genau das tun, was Sie wollen - eine Liste von Zahlen bis zu einem gewissen Grad erzeugen, aber in einer (vernünftigen) zufälligen Reihenfolge. Die Muster, die es erzeugt, sind statistisch ähnlich denen, die Sie von zufälligen Versuchen erwarten würden, aber es ist nicht einmal kryptografisch sicher. Mit dem Berlekamp-Massey-Algorithmus können Sie ein äquivalentes LFSR basierend auf einer Ausgabesequenz zurückentwickeln.
Wenn Sie eine Liste von etwa 10.000.000 Elementen benötigen, möchten Sie ein LFSR mit einer maximalen Länge von 24 Bit haben und Ausgaben, die größer als die Größe Ihrer Liste sind, einfach verwerfen.
Für das, was es wert ist, ist ein LFSR im Allgemeinen ziemlich schnell verglichen mit einem typischen linearen Kongruenz-PRNG derselben Periode. In der Hardware ist ein LFSR extrem einfach, bestehend aus einem N-Bit-Register und M 2-Eingangs-XORs (wobei M die Anzahl der Abgriffe ist - manchmal nur ein paar und selten mehr als a ein halbes Dutzend oder so).
Wenn genügend Speicherplatz vorhanden ist, können Sie die Zeiger des Knotens in einem Array speichern, eine Bitmap erstellen und zufällige Ints abrufen, die auf das nächste ausgewählte Element zeigen. Wenn Sie bereits ausgewählt haben (Sie speichern das in Ihrer Bitmap), dann erhalten Sie am nächsten (links oder rechts, können Sie randomize), bis keine Elemente mehr übrig sind.
Wenn es nicht genug Platz gibt, können Sie dasselbe tun, ohne die Zeiger des Knotens zu speichern, aber die Zeit wird darunter leiden (das ist der Zeit-Raum-Kompromiss).
Sie können eine Pseudozufalls-, 'sichere' Permutation mit einer Blockchiffre erstellen - siehe hier . Die wichtigste Erkenntnis ist, dass man bei einer Blockchiffre von n Bit Länge "falten" verwenden kann, um sie auf m & lt; n Bits, dann der bereits erwähnte Trick antti.huima, um daraus eine kleinere Permutation zu generieren, ohne viel Zeit damit zu verschwenden, Werte außerhalb des Bereichs zu verwerfen.
Im Wesentlichen benötigen Sie einen Zufallszahlengenerator, der die Zahlen 0..n-1 genau einmal erzeugt.
Hier ist eine halbgebackene Idee: Sie könnten ziemlich gut tun, indem Sie eine Primzahl p etwas größer als n wählen und dann ein zufälliges x zwischen 1 und p-1 wählen, dessen Reihenfolge in der multiplikativen Gruppe mod p p-1 ist random xs und teste, welche für x & lt; p-1 genügen, du wirst nur ein paar testen müssen, bevor du eins findest. Da x dann die Gruppe erzeugt, berechne einfach x ^ i mod p für 1 & lt; = i & lt; = p-2 und das wird dir p-2 verschiedene zufällige (ish) Zahlen zwischen 2 und p-1 geben. Subtrahieren Sie 2 und werfen Sie die & gt; = n aus und das gibt Ihnen eine Reihe von zu druckenden Indizes.
Das ist nicht schrecklich zufällig, aber Sie können die gleiche Technik mehrmals verwenden, indem Sie die obigen Indizes (+1) verwenden und sie als Exponenten eines anderen Generators verwenden x2 Modulo ein anderes Primzahl p2 (Sie benötigen n & lt; p2 & lt; p) und so weiter. Ein Dutzend Wiederholungen sollte die Dinge ziemlich zufällig machen.