Python에서 대체 암호 코드 최적화

Question

다음은 2000 개의 임의 키로 최대 500 개 길이의 임의 문자열 2000 개에 대해 간단한 대체 암호화를 수행하는 세 가지 다른 기능을 테스트하는 코드입니다.

최고의 기능은 출력을 보여줍니다 것을 encrypt3다음 encrypt1과 느린입니다 encrypt2.

더 빠른 대체를 수행하는 다른 방법은 무엇입니까 encrypt3?

대체는 대문자 알파벳 "A"에서 "Z"까지 수행되며 다른 문자는 허용되지 않으며 입력 문자열에 해당 문자 만 포함되는지 여부에 대한 테스트가 필요하지 않습니다.

코드 끝에는 모든 함수가 동일한 출력을 생성하는지 테스트합니다.

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)

산출:

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

Answer 1

아무 작업없이 조인에 걸리는 시간과를 비교하면 조인 translante/maketrans을 사용하는 솔루션이 불가능하고 translante/maketrans구현 보다 빠르다는 것을 빠르게 알 수 있습니다 (구현은 마지막 코드 참조).

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

그리고 문자열은 파이썬에서 불변이고 조인이 문자를 연결하는 가장 빠른 (가장 빠르지는 않지만) 순수한 파이썬 방법 중 하나라는 것을 알면 더 나은 파이썬 구현을 찾기가 어려울 것입니다.

그러나 frank-yellin이 언급했듯이 C 구현을 수행하여 코드를 더 빠르게 실행할 수 있습니다. C 코드는이 경우 (문자열의 문자 교체)와 같은 저수준 작업의 경우 Python보다 빠르게 실행됩니다.

C 버전을 작성하기 위해 cython을 사용하면 확장의 모든 상용구를 직접 작성하는 것보다 훨씬 쉽게 만들 수 있습니다.

예 : cython :을 설치 pip install cython하고 python setup.py build_ext --inplace다음 3 개의 파일이 포함 된 폴더에서 실행하여 cython 코드를 컴파일해야 합니다.

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

결과 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