การแทนที่การเพิ่มประสิทธิภาพรหัสรหัสใน Python

Question

นี่คือรหัสของฉันเพื่อทดสอบฟังก์ชั่นที่แตกต่างกันสามอย่างของฉันซึ่งทำการเข้ารหัสการแทนที่อย่างง่ายบนสตริงสุ่ม 2,000 สตริงที่มีความยาวสูงสุด 500 พร้อมคีย์สุ่ม 2,000 คีย์

แสดงให้เห็นผลลัพธ์ที่ฟังก์ชั่นที่ดีที่สุดคือencrypt3แล้วและช้าที่สุดคือencrypt1encrypt2

มีวิธีการอื่นใดในการเปลี่ยนตัวที่เร็วกว่า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 บริสุทธิ์ที่เร็วที่สุด (ถ้าไม่ใช่วิธีที่เร็วที่สุด) ในการต่ออักขระเข้าด้วยกันดูเหมือนจะยากที่จะหาการใช้งาน Python ที่ดีกว่า

อย่างไรก็ตามตามที่แฟรงก์เยลลินกล่าวไว้การใช้งาน C สามารถทำได้เพื่อให้โค้ดทำงานเร็วขึ้น รหัส C ทำงานได้เร็วกว่า python สำหรับการดำเนินการระดับต่ำเช่นในกรณีนี้ (การแทนที่อักขระในสตริง)

ในการลองเขียนเวอร์ชัน C คุณสามารถใช้ cython ซึ่งจะทำให้ง่ายกว่าการเขียนต้นแบบของส่วนขยายทั้งหมดด้วยตัวเอง

ตัวอย่าง: คุณจะต้องติดตั้ง cython: pip install cythonและคอมไพล์โค้ด cython โดยการทำลายpython setup.py build_ext --inplaceในโฟลเดอร์ที่มี 3 ไฟล์ต่อไปนี้

# 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