Pythonでの換字式暗号コードの最適化

Question

これは、2000個のランダムキーを使用して最大500の長さの2000個のランダム文字列に対して単純な換字式暗号化を実行する3つの異なる関数をテストするためのコードです。

出力は、最良の関数が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

また、文字列はPythonで不変であり、結合が文字を連結するための最も高速な（最速ではないにしても）純粋なPythonの方法の1つであることを知っていると、より良いPython実装を見つけるのは難しいようです。

ただし、frank-yellinが述べたように、コードの実行を高速化するためにC実装を実行できます。この場合のような低レベルの操作（文字列内の文字の置換）では、CコードはPythonよりも高速に実行されます。

Cバージョンの作成を試すには、cythonを使用できます。これにより、拡張機能の定型文をすべて自分で作成するよりもはるかに簡単になります。

例：cython：をインストールし、次の3つのファイルを含むフォルダーでpip install cythonruunningpython setup.py build_ext --inplaceして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