Optimierung des Substitutions-Chiffriercodes in Python

Question

Hier ist mein Code zum Testen meiner drei verschiedenen Funktionen, die eine einfache Substitutionsverschlüsselung für 2000 zufällige Zeichenfolgen mit einer Länge von bis zu 500 mit 2000 zufälligen Schlüsseln durchführen.

Die Ausgabe zeigt, dass die beste Funktion encrypt3dann encrypt1und die langsamste ist encrypt2.

Was sind andere Methoden, um eine Substitution durchzuführen, die noch schneller wäre als encrypt3?

Die Ersetzung erfolgt für Großbuchstaben "A" bis "Z", es sind keine weiteren Zeichen zulässig und es sind keine Tests erforderlich, ob Eingabezeichenfolgen nur diese Zeichen enthalten.

Am Ende des Codes steht ein Test, ob alle Funktionen die gleichen Ausgaben erzeugt haben.

from random import randrange, seed, sample
from time import perf_counter

alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def encrypt1(t,key):
    v=dict(zip(alphabet,key))
    return ''.join(v.get(n) for n in t)

def encrypt2(t,key):
    return ''.join(key[alphabet.index(n)] for n in t)

def encrypt3(t,key):
    return t.translate(str.maketrans(alphabet,key))
    
d=2000 # number of strings and keys to test
length=500 # biggest length of strings

strings=[''.join(chr(randrange(26)+65) for n in range(1,randrange(1,length))) for n in range(d)]

keys=[''.join(chr(n+65) for n in sample(range(26), 26)) for n in range(d)]

a=perf_counter()
en1=[encrypt1(strings[n],keys[n]) for n in range(d)]
b=perf_counter()
print('encrypt1 time:',b-a)

a=perf_counter()
en2=[encrypt2(strings[n],keys[n]) for n in range(d)]
b=perf_counter()
print('encrypt2 time:',b-a)

a=perf_counter()
en3=[encrypt3(strings[n],keys[n]) for n in range(d)]
b=perf_counter()
print('encrypt3 time:',b-a)

print("All encryptions outputs are same:",en1==en2==en3)

Ausgabe:

# encrypt1 time: 0.09787979999999999
# encrypt2 time: 0.16948359999999996
# encrypt3 time: 0.029016399999999998
# All encryptions outputs are same: True

Answer 1

Wenn Sie einfach die Zeit vergleichen, die ein Join ohne Operation benötigt, und die translante/maketrans, können Sie schnell erkennen, dass es unmöglich ist, eine Lösung zu haben, die Join verwendet und schneller als die translante/maketransImplementierung ist (Implementierung siehe Code am Ende).

Encryption join only took: 0.006335399999999991s
Encryption translation function took: 0.004516500000000034s

Und da wir wissen, dass Zeichenfolgen in Python unveränderlich sind und der Join eine der schnellsten (wenn nicht die schnellsten) reinen Python-Methoden zum Verketten von Zeichen ist, scheint es schwierig, eine bessere Python-Implementierung zu finden.

Wie von Frank-Yellin erwähnt, kann jedoch eine C-Implementierung durchgeführt werden, um den Code schneller laufen zu lassen. C-Code läuft schneller als Python für Operationen auf niedriger Ebene wie in diesem Fall (Ersetzen von Zeichen in einer Zeichenfolge).

Um zu versuchen, eine C-Version zu schreiben, können Sie Cython verwenden, was es viel einfacher macht, als das gesamte Boilerplate einer Erweiterung selbst zu schreiben.

Beispiel: Sie müssen cython: installieren pip install cythonund den cython-Code kompilieren, indem Sie ihn python setup.py build_ext --inplacein dem Ordner ausführen, der die drei folgenden Dateien enthält

# file cencrypt.pyx

# distutils: language = c++

from libcpp.string cimport string

cdef char char_A = 'A'

def encrypt(t, key):
    cdef string key_str = key.encode('UTF-8')
    cdef string result = t.encode('UTF-8')

    for i in range(len(result)):
        result[i] = key_str[result[i]-char_A]

    return result.decode('UTF-8')

# file main.py

from random import randrange, seed, sample
from time import perf_counter

from cencrypt import encrypt as encrypt_c

alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def encrypt_join_only(t, key):
    return ''.join(t)


def encrypt_dict(t, key):
    v = dict(zip(alphabet, key))
    return ''.join(v.get(n) for n in t)


def encrypt_array(t, key):
    ord_a = ord("A")
    return ''.join(key[n - ord_a] for n in map(ord, t))


def encrypt_translation(t, key):
    return t.translate(str.maketrans(alphabet, key))


d = 2000  # number of strings and keys to test
length = 500  # biggest length of strings

strings = [''.join(chr(randrange(26) + 65) for n in range(1, randrange(1, length))) for n in range(d)]
keys = [''.join(chr(n + 65) for n in sample(range(26), 26)) for n in range(d)]


def measure_perf(function, name):
    start = perf_counter()
    result = [function(strings[n], keys[n]) for n in range(d)]
    end = perf_counter()
    print(f'Encryption {name} took: {end - start}s', )
    return result


measure_perf(encrypt_join_only, "join only")
equal = (
    measure_perf(encrypt_dict, "dict lookup") ==
    measure_perf(encrypt_array, "array lookup") ==
    measure_perf(encrypt_translation, "translation function") ==
    measure_perf(encrypt_c, "cython implementation")
)

print("All encryptions outputs are same:", equal)

#file setup.py

from setuptools import setup
from Cython.Build import cythonize

setup(
    ext_modules=cythonize("cencrypt.pyx")
)

Ergebnisse I7:

Encryption join only took: 0.006335399999999991s
Encryption dict lookup took: 0.044010700000000014s
Encryption array lookup took: 0.0479598s
Encryption translation function took: 0.004516500000000034s
Encryption cython implementation took: 0.002248700000000048s
All encryptions outputs are same: True