Pengoptimalan kode sandi substitusi dengan Python

Question

Berikut adalah kode saya untuk menguji tiga fungsi berbeda yang melakukan enkripsi substitusi sederhana pada 2000 string acak dengan panjang hingga 500 dengan 2000 kunci acak.

Output menunjukkan bahwa fungsi terbaik adalah encrypt3kemudian encrypt1dan paling lambat adalah encrypt2.

Apa metode lain untuk melakukan substitusi yang akan lebih cepat daripada encrypt3?

Pergantian dilakukan pada huruf besar alfabet "A" ke "Z", tidak ada karakter lain yang diperbolehkan dan tidak ada tes yang diperlukan apakah string input hanya berisi karakter tersebut.

Di akhir kode adalah pengujian apakah semua fungsi menghasilkan keluaran yang sama.

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)

Keluaran:

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

Answer 1

Cukup membandingkan waktu translante/maketransyang dibutuhkan oleh join tanpa operasi apa pun dan , Anda dapat dengan cepat melihat bahwa tidak mungkin memiliki solusi yang menggunakan join dan lebih cepat daripada translante/maketransimplementasinya (lihat kode di bagian akhir untuk implementasi).

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

Dan mengetahui bahwa string tidak dapat diubah dalam Python dan gabungannya adalah salah satu cara python murni tercepat (jika bukan yang tercepat) untuk menggabungkan karakter, tampaknya sulit untuk menemukan implementasi python yang lebih baik.

Namun, seperti yang disebutkan oleh frank-yellin, implementasi C dapat dilakukan untuk membuat kode berjalan lebih cepat. Kode C berjalan lebih cepat daripada python untuk operasi tingkat rendah seperti dalam kasus ini (mengganti karakter dalam string).

Untuk mencoba menulis versi C, Anda dapat menggunakan cython yang akan membuatnya jauh lebih mudah daripada menulis semua boilerplate ekstensi sendiri.

Contoh: Anda perlu menginstal cython: pip install cythondan mengkompilasi kode cython dengan merusak python setup.py build_ext --inplacefolder yang berisi 3 file berikut

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

Hasil 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