webentwicklung-frage-antwort-db.com.de

Schnellste Methode zum Generieren einer zufälligen eindeutigen Zeichenfolge mit zufälliger Länge in Python 3

Ich weiß, wie man eine zufällige Zeichenfolge erstellt:

''.join(secrets.choice(string.ascii_uppercase + string.digits) for _ in range(N))

Es sollte jedoch keine Duplikate geben, also prüfe ich gerade, ob der Schlüssel bereits in einer Liste vorhanden ist, wie im folgenden Code gezeigt:

import secrets
import string
import numpy as np


amount_of_keys = 40000

keys = []

for i in range(0,amount_of_keys):
    N = np.random.randint(12,20)
    n_key = ''.join(secrets.choice(string.ascii_uppercase + string.digits) for _ in range(N))
    if not n_key in keys:
        keys.append(n_key)

Was für eine kleine Anzahl von Schlüsseln wie 40000 in Ordnung ist, das Problem skaliert jedoch nicht gut, je mehr Schlüssel vorhanden sind. Ich frage mich also, ob es für noch mehr Schlüssel, wie 999999, einen schnelleren Weg zum Ergebnis gibt.

23
Kev1n91

Grundlegende Verbesserungen, Sets und lokale Namen

Verwenden Sie ein set , keine Liste, und das Testen auf Eindeutigkeit ist viel schneller. Das Testen der Zugehörigkeit zu einem Satz dauert unabhängig von der eingestellten Größe konstant, während Listen eine O(N) lineare Zeit benötigen. Verwenden Sie ein Mengenverständnis, um eine Reihe von Schlüsseln gleichzeitig zu erzeugen, damit Sie die set.add() -Methode nicht in einer Schleife nachschlagen und aufrufen müssen. Bei richtig zufälligen, größeren Schlüsseln ist die Wahrscheinlichkeit, dass Duplikate erstellt werden, ohnehin sehr gering.

Da dies in einer engen Schleife erfolgt, lohnt es sich, alle Namenssuchen so weit wie möglich zu optimieren:

import secrets
import numpy as np
from functools import partial

def produce_amount_keys(amount_of_keys, _randint=np.random.randint):
    keys = set()
    pickchar = partial(secrets.choice, string.ascii_uppercase + string.digits)
    while len(keys) < amount_of_keys:
        keys |= {''.join([pickchar() for _ in range(_randint(12, 20))]) for _ in range(amount_of_keys - len(keys))}
    return keys

Das Schlüsselwortargument _randint Bindet den Namen np.random.randint An ein lokales Element in der Funktion, das schneller als globale Elemente referenziert werden kann, insbesondere bei Attributsuchen.

Das pickchar() -Partial vermeidet das Nachschlagen von Attributen in Modulen oder mehr Locals. Es ist eine einzelne aufrufbare Datei, die alle Referenzen enthält, und daher schneller ausführbar ist, insbesondere wenn sie in einer Schleife ausgeführt wird.

Die while -Schleife wird nur dann wiederholt, wenn Duplikate erstellt wurden. Wir produzieren genug Schlüssel in einem einzigen Set-Verständnis, um den Rest zu füllen, wenn es keine Duplikate gibt.

Timings für diese erste Verbesserung

Bei 100 Artikeln ist der Unterschied nicht so groß:

>>> timeit('p(100)', 'from __main__ import produce_amount_keys_list as p', number=1000)
8.720592894009314
>>> timeit('p(100)', 'from __main__ import produce_amount_keys_set as p', number=1000)
7.680242831003852

aber wenn Sie anfangen, dies zu vergrößern, werden Sie feststellen, dass der Mitgliedschaftstest O(N) für eine Liste Ihre Version wirklich in die Länge zieht:

>>> timeit('p(10000)', 'from __main__ import produce_amount_keys_list as p', number=10)
15.46253142200294
>>> timeit('p(10000)', 'from __main__ import produce_amount_keys_set as p', number=10)
8.047800761007238

Meine Version ist bereits fast doppelt so schnell wie 10.000 Artikel. 40.000 Elemente können in 32 Sekunden zehnmal ausgeführt werden:

>>> timeit('p(40000)', 'from __main__ import produce_amount_keys_list as p', number=10)
138.84072386901244
>>> timeit('p(40000)', 'from __main__ import produce_amount_keys_set as p', number=10)
32.40720253501786

Die Listenversion dauerte über 2 Minuten, mehr als zehnmal so lange.

Numpy's random.choice Funktion, nicht kryptografisch stark

Sie können dies noch beschleunigen, indem Sie auf das Modul secrets verzichten und stattdessen np.random.choice() verwenden. Dies erzeugt jedoch keine Zufälligkeit auf kryptografischer Ebene, aber das Auswählen eines zufälligen Zeichens ist doppelt so schnell:

def produce_amount_keys(amount_of_keys, _randint=np.random.randint):
    keys = set()
    pickchar = partial(
        np.random.choice,
        np.array(list(string.ascii_uppercase + string.digits)))
    while len(keys) < amount_of_keys:
        keys |= {''.join([pickchar() for _ in range(_randint(12, 20))]) for _ in range(amount_of_keys - len(keys))}
    return keys

Das macht einen großen Unterschied, jetzt können in nur 16 Sekunden 10 mal 40.000 Schlüssel erzeugt werden:

>>> timeit('p(40000)', 'from __main__ import produce_amount_keys_npchoice as p', number=10)
15.632006907981122

Weitere Optimierungen mit dem itertools-Modul und einem Generator

Wir können auch die Funktion unique_everseen() aus dem Abschnitt itertools module Recipes verwenden, damit sie sich um die kümmert Verwenden Sie dann einen unendlichen Generator und die Funktion itertools.islice() , um die Ergebnisse auf die gewünschte Zahl zu beschränken:

# additional imports
from itertools import islice, repeat

# assumption: unique_everseen defined or imported

def produce_amount_keys(amount_of_keys):
    pickchar = partial(
        np.random.choice,
        np.array(list(string.ascii_uppercase + string.digits)))
    def gen_keys(_range=range, _randint=np.random.randint):
        while True:
            yield ''.join([pickchar() for _ in _range(_randint(12, 20))])
    return list(islice(unique_everseen(gen_keys()), amount_of_keys))

Das geht noch etwas schneller, aber nur unwesentlich:

>>> timeit('p(40000)', 'from __main__ import produce_amount_keys_itertools as p', number=10)
14.698191125993617

os.urandom () Bytes und eine andere Methode zur Erzeugung von Strings

Als nächstes können wir uns an Adam Barnes 'Ideen für die Verwendung von UUID4 (das im Grunde genommen nur ein Wrapper um os.urandom() ) und Base64 anschließt. Indem Base64 in Groß- und Kleinschreibung gefaltet wird und 2 Zeichen durch zufällig ausgewählte Zeichen ersetzt werden, schränkt seine Methode die Entropie in diesen Zeichenfolgen erheblich ein (Sie können nicht den gesamten Bereich eindeutiger Werte erzeugen, eine Zeichenfolge mit 20 Zeichen nur mit (256 ** 15) / (36 ** 20) == 1 von 99437 Entropiebits!).

Die Base64-Codierung verwendet sowohl Groß- als auch Kleinbuchstaben und Ziffern, aber auch fügt die Zeichen - Und / (Oder +) Hinzu. und _ für die URL-sichere Variante). Wenn Sie nur Großbuchstaben und Ziffern verwenden, müssen Sie die Ausgabe in Großbuchstaben schreiben und diese zusätzlichen zwei Zeichen anderen zufälligen Zeichen zuordnen. Dies führt dazu, dass die von os.urandom() bereitgestellten Zufallsdaten eine große Menge an Entropie enthalten. Anstelle von Base64 können Sie auch die Base32-Codierung verwenden, bei der Großbuchstaben und die Ziffern 2 bis 8 verwendet werden, um Zeichenfolgen mit 32 ** n-Möglichkeiten im Vergleich zu 36 ** n zu erstellen. Dies kann jedoch die Dinge aus den obigen Versuchen weiter beschleunigen:

import os
import base64
import math

def produce_amount_keys(amount_of_keys):
    def gen_keys(_urandom=os.urandom, _encode=base64.b32encode, _randint=np.random.randint):
        # (count / math.log(256, 32)), rounded up, gives us the number of bytes
        # needed to produce *at least* count encoded characters
        factor = math.log(256, 32)
        input_length = [None] * 12 + [math.ceil(l / factor) for l in range(12, 20)]
        while True:
            count = _randint(12, 20)
            yield _encode(_urandom(input_length[count]))[:count].decode('ascii')
    return list(islice(unique_everseen(gen_keys()), amount_of_keys))

Das ist wirklich schnell:

>>> timeit('p(40000)', 'from __main__ import produce_amount_keys_b32 as p', number=10)
4.572628145979252

10-mal 40.000 Tasten in etwas mehr als 4 Sekunden. Also ungefähr 75 mal so schnell; Die Geschwindigkeit, mit der os.urandom() als Quelle verwendet wird, ist nicht zu leugnen.

Dies ist wieder kryptografisch stark ; os.urandom() erzeugt Bytes für die kryptografische Verwendung. Auf der anderen Seite haben wir die Anzahl der möglichen Strings um mehr als 90% reduziert (((36 ** 20) - (32 ** 20)) / (36 ** 20) * 100 Ist 90,5), wir verwenden nicht mehr den 0, 1, 8 Und 9 Ziffern in den Ausgängen.

Vielleicht sollten wir den Trick urandom() verwenden, um eine korrekte Base36-Codierung zu erzeugen. Wir müssen unsere eigene b36encode() -Funktion erzeugen:

import string
import math

def b36encode(b, 
        _range=range, _ceil=math.ceil, _log=math.log, _fb=int.from_bytes, _len=len, _b=bytes,
        _c=(string.ascii_uppercase + string.digits).encode()):
    """Encode a bytes value to Base36 (uppercase ASCII and digits)

    This isn't too friendly on memory because we convert the whole bytes
    object to an int, but for smaller inputs this should be fine.
    """
    b_int = _fb(b, 'big')
    length = _len(b) and _ceil(_log((256 ** _len(b)) - 1, 36))
    return _b(_c[(b_int // 36 ** i) % 36] for i in _range(length - 1, -1, -1))

und benutze das:

def produce_amount_keys(amount_of_keys):
    def gen_keys(_urandom=os.urandom, _encode=b36encode, _randint=np.random.randint):
        # (count / math.log(256, 36)), rounded up, gives us the number of bytes
        # needed to produce *at least* count encoded characters
        factor = math.log(256, 36)
        input_length = [None] * 12 + [math.ceil(l / factor) for l in range(12, 20)]
        while True:
            count = _randint(12, 20)
            yield _encode(_urandom(input_length[count]))[-count:].decode('ascii')
    return list(islice(unique_everseen(gen_keys()), amount_of_keys))

Dies ist relativ schnell und liefert vor allem den gesamten Bereich von 36 Großbuchstaben und Ziffern:

>>> timeit('p(40000)', 'from __main__ import produce_amount_keys_b36 as p', number=10)
8.099918447987875

Zugegeben, die Base32-Version ist fast doppelt so schnell wie diese (dank einer effizienten Python -Implementierung unter Verwendung einer Tabelle), aber die Verwendung eines benutzerdefinierten Base36-Encoders ist immer noch doppelt so schnell wie die nicht kryptografisch sichere numpy.random.choice() Ausführung.

Wenn Sie jedoch os.urandom() verwenden, wird wiederum bias erzeugt. Wir müssen mehr Entropiebits erzeugen, als für 12 bis 19 Base36-Stellen erforderlich ist. Für 17 Stellen können wir zum Beispiel nicht 36 ** 17 verschiedene Werte mit Bytes erzeugen, sondern nur das nächste Äquivalent von 256 ** 11 Bytes, was ungefähr 1,08-mal zu hoch ist in Richtung A, B und in geringerem Maße C (Danke Stefan Pochmann für diesen Hinweis).

Wählen Sie eine Ganzzahl unter (36 ** length) Und ordnen Sie die Ganzzahlen base36 zu

Wir müssen uns also um eine sichere Zufallsmethode bemühen, mit der wir Werte erhalten, die gleichmäßig zwischen 0 (Einschließlich) und 36 ** (desired length) (ausschließlich) verteilt sind. Wir können die Nummer dann direkt der gewünschten Zeichenfolge zuordnen.

Zunächst wird die Ganzzahl einer Zeichenfolge zugeordnet. Folgendes wurde optimiert, um die Ausgabe-Zeichenfolge am schnellsten zu erzeugen:

def b36number(n, length, _range=range, _c=string.ascii_uppercase + string.digits):
    """Convert an integer to Base36 (uppercase ASCII and digits)"""
    chars = [_c[0]] * length
    while n:
        length -= 1
        chars[length] = _c[n % 36]
        n //= 36
    return ''.join(chars)

Als Nächstes benötigen wir eine schnelle und kryptografisch sichere Methode zum Auswählen unserer Nummer in einem Bereich. Sie können hierfür immer noch os.urandom() verwenden, müssen dann jedoch die Bytes bis auf eine maximale Anzahl von Bits maskieren und dann eine Schleife ausführen, bis Ihr tatsächlicher Wert unter dem Grenzwert liegt. Dies ist eigentlich schon implementiert, durch die secrets.randbelow() function . In Python Versionen <3.6 können Sie random.SystemRandom().randrange() verwenden, wobei genau dieselbe Methode mit einigem zusätzlichen Zeilenumbruch verwendet wird, um eine Untergrenze größer als 0 und einen Schritt zu unterstützen Größe.

Mit secrets.randbelow() wird die Funktion:

import secrets

def produce_amount_keys(amount_of_keys):
    def gen_keys(_below=secrets.randbelow, _encode=b36number, _randint=np.random.randint):
        limit = [None] * 12 + [36 ** l for l in range(12, 20)]
        while True:
            count = _randint(12, 20)
            yield _encode(_below(limit[count]), count)
    return list(islice(unique_everseen(gen_keys()), amount_of_keys))

und das ist dann ziemlich nah an der (wahrscheinlich voreingenommenen) base64-Lösung:

>>> timeit('p(40000)', 'from __main__ import produce_amount_keys_below as p', number=10)
5.135716405988205

Dies ist fast so schnell wie der Base32-Ansatz, bringt aber die gesamte Bandbreite an Schlüsseln hervor!

46
Martijn Pieters

Also ist es ein Speed ​​Race, oder?

Aufbauend auf der Arbeit von Martijn Pieters habe ich eine Lösung, die eine andere Bibliothek zur Erzeugung von zufälligen Zeichenketten geschickt einsetzt: uuid.

Meine Lösung ist, einen uuid4 zu generieren, ihn mit base64 zu codieren und ihn in Großbuchstaben zu schreiben, um nur die Zeichen zu erhalten, nach denen wir suchen, und dann eine zufällige Länge zu erhalten.

Dies funktioniert in diesem Fall, weil die Länge der Ausgaben (12-20), nach denen wir streben, kürzer ist als die kürzeste base64-Kodierung eines uuid4. Es ist auch sehr schnell, weil uuid sehr schnell ist.

Ich habe es auch zu einem Generator anstatt einer regulären Funktion gemacht, weil sie effizienter sein können.

Interessanterweise war die Verwendung der randint-Funktion der Standardbibliothek schneller als die von numpy.

Hier ist die Testausgabe:

Timing 40k keys 10 times with produce_amount_keys
20.899942063027993
Timing 40k keys 10 times with produce_amount_keys, stdlib randint
20.85920040300698
Timing 40k keys 10 times with uuidgen
3.852462349983398
Timing 40k keys 10 times with uuidgen, stdlib randint
3.136272903997451

Hier ist der Code für uuidgen():

def uuidgen(count, _randint=np.random.randint):
    generated = set()

    while True:
        if len(generated) == count:
            return

        candidate = b64encode(uuid4().hex.encode()).upper()[:_randint(12, 20)]
        if candidate not in generated:
            generated.add(candidate)
            yield candidate

Und hier ist das gesamte Projekt. (Beim Festschreiben d9925d zum Zeitpunkt des Schreibens).


Dank des Feedbacks von Martijn Pieters habe ich die Methode etwas verbessert, die Entropie erhöht und sie um den Faktor 1/6 beschleunigt.

Es ist immer noch viel Entropie verloren, wenn alle Kleinbuchstaben in Großbuchstaben umgewandelt werden. Wenn dies wichtig ist, ist es möglicherweise ratsam, stattdessen b32encode() zu verwenden, die die gewünschten Zeichen enthält, minus 0, 1, 8 und 9.

Die neue Lösung lautet wie folgt:

def urandomgen(count):
    generated = set()

    while True:
        if len(generated) == count:
            return

        desired_length = randint(12, 20)

        # # Faster than math.ceil
        # urandom_bytes = urandom(((desired_length + 1) * 3) // 4)
        #
        # candidate = b64encode(urandom_bytes, b'//').upper()
        #
        # The above is rolled into one line to cut down on execution
        # time stemming from locals() dictionary access.

        candidate = b64encode(
            urandom(((desired_length + 1) * 3) // 4),
            b'//',
        ).upper()[:desired_length]

        while b'/' in candidate:
            candidate = candidate.replace(b'/', choice(ALLOWED_CHARS), 1)

        if candidate not in generated:
            generated.add(candidate)
            yield candidate.decode()

Und die Testausgabe:

Timing 40k keys 10 times with produce_amount_keys, stdlib randint
19.64966493297834
Timing 40k keys 10 times with uuidgen, stdlib randint
4.063803717988776
Timing 40k keys 10 times with urandomgen, stdlib randint
2.4056471119984053

Das neue Commit in meinem Repository lautet 5625fd .


Martijns Kommentare zur Entropie brachten mich zum Nachdenken. Die Methode, die ich mit base64 und .upper() verwendet habe, macht Buchstaben SO viel häufiger als Zahlen. Ich habe das Problem mit einem binäreren Verstand wieder aufgegriffen.

Die Idee war, die Ausgabe von os.urandom() zu übernehmen, sie als lange Zeichenfolge von vorzeichenlosen 6-Bit-Zahlen zu interpretieren und diese Zahlen als Index für ein rollendes Array der zulässigen Zeichen zu verwenden. Die erste 6-Bit-Nummer würde ein Zeichen aus dem Bereich A..Z0..9A..Z01 auswählen, die zweite 6-Bit-Nummer würde ein Zeichen aus dem Bereich 2..9A..Z0..9A..T und so weiter auswählen.

Dies hat eine leichte Entropie-Unterdrückung zur Folge, da das erste Zeichen 2..9 etwas weniger enthält, das zweite Zeichen U..Z0 und so weiter, aber es ist so viel besser als zuvor.

Es ist etwas schneller als uuidgen() und etwas langsamer als urandomgen(), wie unten gezeigt:

Timing 40k keys 10 times with produce_amount_keys, stdlib randint
20.440480664998177
Timing 40k keys 10 times with uuidgen, stdlib randint
3.430628580001212
Timing 40k keys 10 times with urandomgen, stdlib randint
2.0875444510020316
Timing 40k keys 10 times with bytegen, stdlib randint
2.8740892770001665

Ich bin nicht ganz sicher, wie ich den letzten Teil der Entropie zerstören kann. Das Versetzen des Startpunkts für die Charaktere bewegt das Muster nur ein Stück weiter, das Versetzen mit Zufallszahlen wird langsam, das Mischen der Karte wird immer noch einen Zeitraum haben ... Ich bin offen für Ideen.

Der neue Code lautet wie folgt:

from os import urandom
from random import randint
from string import ascii_uppercase, digits

# Masks for extracting the numbers we want from the maximum possible
# length of `urandom_bytes`.
bitmasks = [(0b111111 << (i * 6), i) for i in range(20)]
allowed_chars = (ascii_uppercase + digits) * 16  # 576 chars long


def bytegen(count):
    generated = set()

    while True:
        if len(generated) == count:
            return

        # Generate 9 characters from 9x6 bits
        desired_length = randint(12, 20)
        bytes_needed = (((desired_length * 6) - 1) // 8) + 1

        # Endianness doesn't matter.
        urandom_bytes = int.from_bytes(urandom(bytes_needed), 'big')

        chars = [
            allowed_chars[
                (((urandom_bytes & bitmask) >> (i * 6)) + (0b111111 * i)) % 576
            ]
            for bitmask, i in bitmasks
        ][:desired_length]

        candidate = ''.join(chars)

        if candidate not in generated:
            generated.add(candidate)
            yield candidate

Der vollständige Code sowie ein tieferes README zur Implementierung sind um de0db8 vorbei.

Ich habe verschiedene Schritte unternommen, um die Implementierung zu beschleunigen, wie im Repo zu sehen ist. Was definitiv helfen würde, ist eine Zeichencodierung, bei der die Zahlen und die Großbuchstaben ASCII sequentiell sind.

8
Adam Barnes

Ein einfaches und schnelles:

def b36(n, N, chars=string.ascii_uppercase + string.digits):
    s = ''
    for _ in range(N):
        s += chars[n % 36]
        n //= 36
    return s

def produce_amount_keys(amount_of_keys):
    keys = set()
    while len(keys) < amount_of_keys:
        N = np.random.randint(12, 20)
        keys.add(b36(secrets.randbelow(36**N), N))
    return keys

- Edit: Das Folgende bezieht sich auf eine frühere Version von Martijns Antwort. Nach unserer Diskussion fügte er eine weitere Lösung hinzu, die im Wesentlichen die gleiche ist wie meine, jedoch mit einigen Optimierungen. Sie helfen zwar nicht viel, aber in meinen Tests sind es nur etwa 3,4% schneller als meine, daher machen sie meiner Meinung nach meist nur komplizierte Dinge. -

Verglichen mit Martijns endgültiger Lösung in seiner akzeptierten Antwort ist meine viel einfacher, um den Faktor 1,7 schneller und nicht voreingenommen:

Stefan
8.246490597876106 seconds.
8 different lengths from 12 to 19
  Least common length 19 appeared 124357 times.
  Most common length 16 appeared 125424 times.
36 different characters from 0 to Z
  Least common character Q appeared 429324 times.
  Most common character Y appeared 431433 times.
36 different first characters from 0 to Z
  Least common first character C appeared 27381 times.
  Most common first character Q appeared 28139 times.
36 different last characters from 0 to Z
  Least common last character Q appeared 27301 times.
  Most common last character E appeared 28109 times.

Martijn
14.253227412021943 seconds.
8 different lengths from 12 to 19
  Least common length 13 appeared 124753 times.
  Most common length 15 appeared 125339 times.
36 different characters from 0 to Z
  Least common character 9 appeared 428176 times.
  Most common character C appeared 434029 times.
36 different first characters from 0 to Z
  Least common first character 8 appeared 25774 times.
  Most common first character A appeared 31620 times.
36 different last characters from 0 to Z
  Least common last character Y appeared 27440 times.
  Most common last character X appeared 28168 times.

Martijns hat eine Neigung im ersten Zeichen, A erscheint viel zu oft und 8 viel zu selten. Ich habe meinen Test zehnmal durchgeführt, sein häufigstes erstes Zeichen war immer A oder B (jeweils fünfmal), und sein am wenigsten häufiges Zeichen war immer 7, 8 oder 9 (zwei-, dreifach- bzw. fünfmal). Ich habe die Längen auch separat geprüft, Länge 17 war besonders schlecht, sein häufigster erster Buchstabe erschien immer etwa 51500 Mal, während sein am wenigsten gewöhnlicher erster Charakter etwa 25400 Mal erschien.

Fun Side Note: Ich verwende das secrets Modul, das Martijn abgewiesen hat :-)

Mein ganzes Skript:

import string
import secrets
import numpy as np
import os
from itertools import islice, filterfalse
import math

#------------------------------------------------------------------------------------
#   Stefan
#------------------------------------------------------------------------------------

def b36(n, N, chars=string.ascii_uppercase + string.digits):
    s = ''
    for _ in range(N):
        s += chars[n % 36]
        n //= 36
    return s

def produce_amount_keys_stefan(amount_of_keys):
    keys = set()
    while len(keys) < amount_of_keys:
        N = np.random.randint(12, 20)
        keys.add(b36(secrets.randbelow(36**N), N))
    return keys

#------------------------------------------------------------------------------------
#   Martijn
#------------------------------------------------------------------------------------

def b36encode(b, 
        _range=range, _ceil=math.ceil, _log=math.log, _fb=int.from_bytes, _len=len, _b=bytes,
        _c=(string.ascii_uppercase + string.digits).encode()):
    b_int = _fb(b, 'big')
    length = _len(b) and _ceil(_log((256 ** _len(b)) - 1, 36))
    return _b(_c[(b_int // 36 ** i) % 36] for i in _range(length - 1, -1, -1))

def produce_amount_keys_martijn(amount_of_keys):
    def gen_keys(_urandom=os.urandom, _encode=b36encode, _randint=np.random.randint, _factor=math.log(256, 36)):
        while True:
            count = _randint(12, 20)
            yield _encode(_urandom(math.ceil(count / _factor)))[-count:].decode('ascii')
    return list(islice(unique_everseen(gen_keys()), amount_of_keys))

#------------------------------------------------------------------------------------
#   Needed for Martijn
#------------------------------------------------------------------------------------

def unique_everseen(iterable, key=None):
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in filterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

#------------------------------------------------------------------------------------
#   Benchmark and quality check
#------------------------------------------------------------------------------------

from timeit import timeit
from collections import Counter

def check(name, func):
    print()
    print(name)

    # Get 999999 keys and report the time.
    keys = None
    def getkeys():
        nonlocal keys
        keys = func(999999)
    t = timeit(getkeys, number=1)
    print(t, 'seconds.')

    # Report statistics about lengths and characters
    def statistics(label, values):
        ctr = Counter(values)
        least = min(ctr, key=ctr.get)
        most = max(ctr, key=ctr.get)
        print(len(ctr), f'different {label}s from', min(ctr), 'to', max(ctr))
        print(f'  Least common {label}', least, 'appeared', ctr[least], 'times.')
        print(f'  Most common {label}', most, 'appeared', ctr[most], 'times.')
    statistics('length', map(len, keys))
    statistics('character', ''.join(keys))
    statistics('first character', (k[0] for k in keys))
    statistics('last character', (k[-1] for k in keys))

for _ in range(2):
    check('Stefan', produce_amount_keys_stefan)
    check('Martijn', produce_amount_keys_martijn)
3
Stefan Pochmann

Warnung: Dies ist kryptografisch nicht sicher. Ich möchte einen alternativen Ansatz numpy zu dem in Martijns großartiger Antwort geben.

numpy - Funktionen sind nicht wirklich für den wiederholten Aufruf in einer Schleife für kleine Aufgaben optimiert. Vielmehr ist es besser, jede Operation in großen Mengen auszuführen. Dieser Ansatz bietet mehr Schlüssel als Sie benötigen (in diesem Fall massiv, weil ich die Notwendigkeit einer Überschätzung übertrieben habe) und ist daher weniger speichereffizient, aber immer noch superschnell.

  1. Wir wissen, dass alle Ihre Stringlängen zwischen 12 und 20 liegen. Generieren Sie einfach alle Stringlängen auf einmal. Wir wissen, dass das endgültige set die Möglichkeit hat, die endgültige Liste der Zeichenfolgen zu kürzen. Deshalb sollten wir dies vorwegnehmen und mehr "Zeichenfolgenlängen" erstellen, als wir benötigen. 20.000 extra sind übertrieben, aber es ist wichtig zu sagen:

    string_lengths = np.random.randint(12, 20, 60000)

  2. Anstatt alle unsere Sequenzen in einer for - Schleife zu erstellen, erstellen Sie eine 1D-Liste mit Zeichen, die lang genug ist, um in 40.000 Listen unterteilt zu werden. Im absoluten Worst-Case-Szenario waren alle zufälligen Zeichenfolgenlängen in (1) die maximale Länge von 20. Das heißt, wir benötigen 800.000 Zeichen.

    pool = list(string.ascii_letters + string.digits)

    random_letters = np.random.choice(pool, size=800000)

  3. Jetzt müssen wir nur noch die Liste der zufälligen Zeichen aufteilen. Mit np.cumsum() können wir sequentielle Startindizes für die Unterlisten erhalten, und np.roll() versetzt dieses Array von Indizes um 1, um ein entsprechendes Array von Endindizes zu erhalten.

    starts = string_lengths.cumsum()

    ends = np.roll(string_lengths.cumsum(), -1)

  4. Zerlegen Sie die Liste der zufälligen Zeichen anhand der Indizes.

    final = [''.join(random_letters[starts[x]:ends[x]]) for x, _ in enumerate(starts)]

Alles zusammenfassen:

def numpy_approach():
    pool = list(string.ascii_letters + string.digits)
    string_lengths = np.random.randint(12, 20, 60000)   
    ends = np.roll(string_lengths.cumsum(), -1) 
    starts = string_lengths.cumsum()
    random_letters = np.random.choice(pool, size=800000)
    final = [''.join(random_letters[starts[x]:ends[x]]) for x, _ in enumerate(starts)]
    return final

Und timeit ergibt:

322 ms ± 7.97 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
1
roganjosh

Alternativer Ansatz: Einzigartigkeit bei der Erstellung und nicht durch Test

Die naheliegendste Herangehensweise an Ihre Frage wäre, eine zufällige Ausgabe zu generieren und dann zu prüfen, ob sie eindeutig ist. Obwohl ich keine Implementierung anbiete, gibt es hier einen alternativen Ansatz:

  1. Generieren Sie eine Ausgabe, die so zufällig wie möglich aussieht
  2. Generieren Sie eine Ausgabe, die garantiert einzigartig ist und etwas zufällig aussieht
  3. Kombiniere sie

Jetzt haben Sie eine Ausgabe, die garantiert eindeutig ist und zufällig erscheint.

Beispiel

Angenommen, Sie möchten 999999 Zeichenfolgen mit Längen zwischen 12 und 20 generieren. Der Ansatz funktioniert natürlich für alle Zeichensätze, lässt sich jedoch einfach halten und nur 0-9 verwenden.

  1. Erzeugen Sie eine zufällige Ausgabe mit Längen von 6 bis 14
  2. Die Zahlen 000000 bis 999999 zufällig verteilen (Ja, 6-stellig ist in scheinbar zufälliger Reihenfolge viel zu "opfern", aber bei einem größeren Zeichensatz benötigen Sie nicht so viele Zeichen.)
  3. Kombinieren Sie sie jetzt so, dass die Einzigartigkeit erhalten bleiben muss. Der trivialste Weg wäre eine einfache Verkettung der Entitäten, aber man kann natürlich an weniger offensichtliche Lösungen denken. 

Kleines Beispiel

  1. Zufälligkeit erzeugen:

    sdfdsf xxer ver 

  2. Einzigartigkeit erzeugen

    xdaebd

  3. Kombinieren

    xdsdfdsf aexxer bdver

Beachten Sie, dass diese Methode voraussetzt, dass Sie eine Mindestanzahl von Zeichen pro Eintrag haben. Dies scheint in Ihrer Frage der Fall zu sein.

0