Ottimizzazione del codice di cifratura sostitutiva in Python

Question

Ecco il mio codice per testare le mie tre diverse funzioni che eseguono una semplice crittografia di sostituzione su 2000 stringhe casuali di lunghezza fino a 500 con 2000 chiavi casuali.

L'output mostra che la funzione migliore è encrypt3allora encrypt1e la più lenta è encrypt2.

Quali sono altri metodi per eseguire la sostituzione che sarebbero ancora più veloci di encrypt3?

La sostituzione viene eseguita sull'alfabeto maiuscolo dalla "A" alla "Z", non sono consentiti altri caratteri e non sono necessari test se le stringhe di input contengono solo quei caratteri.

Alla fine del codice è un test se tutte le funzioni hanno prodotto gli stessi output.

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)

Produzione:

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

Answer 1

Confrontando semplicemente il tempo impiegato da un join senza alcuna operazione e il translante/maketrans, puoi vedere rapidamente che è impossibile avere una soluzione che utilizza join ed è più veloce translante/maketransdell'implementazione (vedi il codice alla fine per l'implementazione).

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

E sapendo che le stringhe sono immutabili in Python e il join è uno dei modi più veloci (se non il più veloce) di Python puro per concatenare i caratteri, sembrerebbe difficile trovare una migliore implementazione di Python.

Tuttavia, come menzionato da frank-yellin, è possibile eseguire un'implementazione in C per rendere il codice più veloce. Il codice C viene eseguito più velocemente di Python per operazioni di basso livello come in questo caso (sostituzione del carattere in una stringa).

Per provare a scrivere una versione C, puoi usare cython che renderà molto più semplice che scrivere tutto il boilerplate di un'estensione da solo.

Esempio: sarà necessario installare cython: pip install cythone compilare il codice cython eseguendo la procedura python setup.py build_ext --inplacenella cartella contenente i 3 file seguenti

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

Risultati 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