Tối ưu hóa mã thay thế mật mã trong Python

Question

Đây là mã của tôi để kiểm tra ba chức năng khác nhau của tôi thực hiện mã hóa thay thế đơn giản trên 2000 chuỗi ngẫu nhiên có độ dài lên đến 500 với 2000 khóa ngẫu nhiên.

Kết quả cho thấy rằng chức năng tốt nhất là encrypt3sau đó encrypt1và chức năng chậm nhất là encrypt2.

Các phương pháp khác để thực hiện thay thế thậm chí còn nhanh hơn là encrypt3gì?

Việc thay thế được thực hiện trên bảng chữ cái viết hoa "A" thành "Z", không có ký tự nào khác được phép và không cần kiểm tra xem chuỗi đầu vào chỉ chứa những ký tự đó hay không.

Cuối đoạn mã là một bài kiểm tra xem tất cả các chức năng có tạo ra các đầu ra giống nhau hay không.

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)

Đầu ra:

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

Answer 1

Chỉ cần so sánh thời gian thực hiện của phép nối mà không có bất kỳ thao tác nào và translante/maketrans, bạn có thể nhanh chóng thấy rằng không thể có giải pháp nào sử dụng phép nối và nhanh hơn việc translante/maketranstriển khai (xem đoạn mã ở cuối để triển khai).

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

Và biết rằng các chuỗi là bất biến trong Python và phép nối là một trong những cách python thuần túy nhanh nhất (nếu không phải là nhanh nhất) để nối các ký tự, có vẻ như sẽ khó tìm được cách triển khai python tốt hơn.

Tuy nhiên, như đã đề cập bởi Frank-yellin, việc triển khai C có thể được thực hiện để làm cho mã chạy nhanh hơn. Mã C chạy nhanh hơn python đối với các hoạt động cấp thấp như trong trường hợp này (thay thế ký tự trong một chuỗi).

Để thử viết một phiên bản C, bạn có thể sử dụng cython sẽ dễ dàng hơn rất nhiều so với việc tự viết tất cả bản soạn sẵn của một phần mở rộng.

Ví dụ: Bạn sẽ cần cài đặt cython: pip install cythonvà biên dịch mã cython bằng cách chạy python setup.py build_ext --inplacetrong thư mục chứa 3 tệp sau

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

Kết quả 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