Optimisation du code de chiffrement de substitution en Python

Question

Voici mon code pour tester mes trois fonctions différentes qui effectuent un cryptage de substitution simple sur 2000 chaînes aléatoires de longueur jusqu'à 500 avec 2000 clés aléatoires.

La sortie montre que la meilleure fonction est encrypt3alors encrypt1et la plus lente est encrypt2.

Quelles sont les autres méthodes pour effectuer une substitution qui serait encore plus rapide que encrypt3?

La substitution est effectuée sur l'alphabet majuscule «A» à «Z», aucun autre caractère n'est autorisé et aucun test n'est nécessaire pour savoir si les chaînes d'entrée contiennent uniquement ces caractères.

À la fin du code est un test pour savoir si toutes les fonctions ont produit les mêmes sorties.

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)

Production:

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

Answer 1

En comparant simplement le temps pris par une jointure sans aucune opération et le translante/maketrans, vous pouvez rapidement voir qu'il est impossible d'avoir une solution qui utilise join et soit plus rapide que l' translante/maketransimplémentation (voir le code à la fin pour l'implémentation).

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

Et sachant que les chaînes sont immuables en Python et que la jointure est l'un des moyens python purs les plus rapides (sinon le plus rapide) de concaténer des caractères, il semblerait difficile de trouver une meilleure implémentation de python.

Cependant, comme mentionné par frank-yellin, une implémentation en C peut être effectuée pour accélérer l'exécution du code. Le code C s'exécute plus rapidement que python pour les opérations de bas niveau comme dans ce cas (remplacement d'un caractère dans une chaîne).

Pour essayer d'écrire une version C, vous pouvez utiliser cython qui le rendra beaucoup plus facile que d'écrire tout le passe-partout d'une extension par vous-même.

Exemple: Vous devrez installer cython: pip install cythonet compiler le code cython python setup.py build_ext --inplaceen exécutant dans le dossier contenant les 3 fichiers suivants

# 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")
)

Résultats 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