Kann die Reihenfolge der Schlüssel eines Wörterbuchs als eine zufällige Permutation betrachtet werden?

Question

Ich habe 40.000 IDs, die die Schlüssel in einem Wörterbuch sind. Ich muss sie mischen, zum Beispiel mit random.shuffle. Aber kann ich diesen Schritt überspringen?

Dictionary speichert die Schlüssel nicht mit der Reihenfolge, in der sie kommen, also wenn ich keys = dict.keys() mache, dann enthält keys die Schlüssel in einer nicht aufsteigenden Reihenfolge. Mein Programm wird nur einmal ausgeführt, also ist es mir egal, ob das "Ergebnis der Permutation" unter den Ausführungen dasselbe ist.

Also, kann ich "schummeln" und den Shuffle-Schritt überspringen?

---

Ich verstehe, dass die Reihenfolge der Schlüssel ein wenig vorhersehbar ist. Was ich aber frage ist das:

Was ist die Chance (grob gesagt) einer Permutation von random.shuffle() erzeugt, um (viel) identisch mit der Reihenfolge der Schlüssel zu sein?

Answer 1

Nein, Sie können nicht.

Wenn Sie Zufälligkeit benötigen, können Sie das Mischen entweder vor dem Eingeben der Daten in das Wörterbuch oder danach nicht überspringen.

Der Grund ist, dass, obwohl die Reihenfolge der Schlüssel in einem Wörterbuch nicht garantiert ist, eine starke Vorhersagbarkeit hinsichtlich der Reihenfolge, die sie basierend auf der Reihenfolge der Eingabe annehmen wird.

Einträge in einem Wörterbuch werden nach dem Wert der hash des Schlüssels, der einige sehr große Zahl ist, Modulo eine andere große Zahl, die Schaffung eines begrenzten Wertebereich vorgenommen. Wenn zwei Schlüssel auf denselben Wert hashen, tritt ein collision auf; der Schlüssel wird dann an der nächsten verfügbaren Stelle platziert (je nachdem, welcher Weg bestimmt wird)

[edit]:
Die Chance zufällig die Schlüssel in einer ungefähr (viel) identischen Reihenfolge als ein Hash-Bucket zu bekommen ist ... unbestimmt.

Answer 2

Um zu erläutern, was andere sagen und warum Sie tatsächlich die Schlüssel mischen müssen. Wenn Sie Ihr Wörterbuch wiederholt auf die gleiche Weise initialisieren, wird es jedes Mal dieselbe Reihenfolge haben. Das ist offensichtlich nicht zufällig. Wie Masque sagte, basiert es auf dem Hash (siehe diese SO-Frage Why is the order in dictionaries and sets arbitrary?).

Um zu antworten "Was ist die Chance (grob gesagt) einer Permutation, die durch random.shuffle() erzeugt wird, um (viel) identisch mit der Reihenfolge der Schlüssel zu sein?" direkt: die Wahrscheinlichkeit, dass es ist genau identisch mit einem Shuffle ist 1/factorial(len(yourDict)); Das liegt daran, dass eine der Permutationen zu der gleichen Reihenfolge führt, die Ihr Diktat bei der Initialisierung vornimmt. Alle anderen Ordnungen werden sich jedoch unterscheiden, und es gibt factorial(len(yourDict)) verschiedene Permutationen (Ordnungen), die aus dem Mischen resultieren könnten.

Hoffe, dass hilft!