бързо XORing байтове в python 3

Когато XORing bytes обекти с един милион елемента всеки, този цикъл създава приблизително един милион временни bytes обекта и копира всеки байт средно приблизително 500 хиляди пъти от един временен bytes към следващия. Обърнете внимание, че точно същият проблем съществува за низове (също и на много други езици). Решението за низ е да се създаде списък с части от низ и да се използва ''.join в края, за да се свържат ефективно. Можете да направите същото с байтове:

def bxor(b1, b2): # use xor for bytes
    parts = []
    for b1, b2 in zip(b1, b2):
        parts.append(bytes([b1 ^ b2]))
    return b''.join(parts)

Като алтернатива можете да използвате bytearray, което е променливо и следователно може да избегне проблема. Също така ви позволява да не разпределяте нов bytes обект на всяка итерация, можете просто да добавите byte/int.

def bxor(b1, b2): # use xor for bytes
    result = bytearray()
    for b1, b2 in zip(b1, b2):
        result.append(b1 ^ b2)
    return result

Можете алтернативно да return bytes(result), ако искате/имате нужда от bytes обект.

Добавяне на това в друг отговор, защото е едно:

Ако искате нещо по-бързо от дадените "ръчни" методи, винаги има Numpy:

import numpy

def bxor_numpy(b1, b2):
    n_b1 = numpy.fromstring(b1, dtype='uint8')
    n_b2 = numpy.fromstring(b2, dtype='uint8')

    return (n_b1 ^ n_b2).tostring()

и е бързо:

first_random = urandom(100000)
second_random = urandom(100000)

min(Timer(partial(bxor_inplace, first_random, second_random)).repeat(10, 100))
#>>> 1.5381054869794752
min(Timer(partial(bxor_append, first_random, second_random)).repeat(10, 100))
#>>> 1.5624085619929247
min(Timer(partial(bxor_numpy, first_random, second_random)).repeat(10, 100))
#>>> 0.009930026979418471

Така че е 150 пъти по-бърз от най-добрите алтернативи, публикувани тук.

Използването на bytearray вече е много по-бързо:

def bxor(b1, b2):
    result = bytearray(b1)
    for i, b in enumerate(b2):
        result[i] ^= b
    return bytes(result)

Едно бързо timeit сравнение:

>>> import timeit
>>> b1, b2 = b'abcdefg' * 10, b'aaaaaaa' * 10
>>> timeit.timeit('it(b1, b2)', 'from __main__ import b1, b2, bxor as it', number=10000)
0.9230150280000089
>>> timeit.timeit('it(b1, b2)', 'from __main__ import b1, b2, bxor_ba as it', number=10000)
0.16270576599890774

Това избягва създаването на нови bytes обекти за всички конкатенации.

Методът b''.join() предложен от delnan не е много по-добър от оригиналната версия:

>>> timeit.timeit('it(b1, b2)', 'from __main__ import b1, b2, bxor_join as it', number=10000)
0.9936718749995634

И повторно изпълнение с байтови низове 100 пъти по-големи:

>>> b1, b2 = b'abcdefg' * 1000, b'aaaaaaa' * 1000
>>> timeit.timeit('it(b1, b2)', 'from __main__ import b1, b2, bxor as it', number=1000)
11.032563796999966
>>> timeit.timeit('it(b1, b2)', 'from __main__ import b1, b2, bxor_join as it', number=1000)
9.242204494001271
>>> timeit.timeit('it(b1, b2)', 'from __main__ import b1, b2, bxor_ba as it', number=1000)
1.762020197998936

за да покаже, че bytes.join() е по-бързо от повтарящо се конкатениране.

Последно изпълнение от 7 милиона байта, повторено 10 пъти, само с версията bytearray, търпението ми свърши с другите версии:

>>> b1, b2 = b'abcdefg' * 1000000, b'aaaaaaa' * 1000000
>>> timeit.timeit('it(b1, b2)', 'from __main__ import b1, b2, bxor_ba as it', number=10)
16.18445999799951

Времената на Martijn Pieters са малко по-различни от моите:

def bxor_add(b1, b2): # use xor for bytes
    result = b""
    for b1, b2 in zip(b1, b2):
        result += bytes([b1 ^ b2])
    return result

def bxor_inplace(b1, b2):
    result = bytearray(b1)
    for i, b in enumerate(b2):
        result[i] ^= b
    return bytes(result)

def bxor_join(b1, b2): # use xor for bytes
    parts = []
    for b1, b2 in zip(b1, b2):
        parts.append(bytes([b1 ^ b2]))
    return b''.join(parts)

def bxor_append(b1, b2): # use xor for bytes
    result = bytearray()
    for b1, b2 in zip(b1, b2):
        result.append(b1 ^ b2)
    return bytes(result)

#>>> 

from os import urandom
from timeit import Timer
from functools import partial

first_random = urandom(200000)
second_random = urandom(200000)

Timer(partial(bxor_add, first_random, second_random)).timeit(1)
#>>> 1.3261873809969984
Timer(partial(bxor_inplace, first_random, second_random)).timeit(1)
#>>> 0.03055390200461261
Timer(partial(bxor_join, first_random, second_random)).timeit(1)
#>>> 0.15852201101370156
Timer(partial(bxor_append, first_random, second_random)).timeit(1)
#>>> 0.030534288001945242

first_random = urandom(10000000)
second_random = urandom(10000000)

Timer(partial(bxor_inplace, first_random, second_random)).timeit(1)
#>>> 1.5432947289955337
Timer(partial(bxor_join, first_random, second_random)).timeit(1)
#>>> 7.90503858300508
Timer(partial(bxor_append, first_random, second_random)).timeit(1)
#>>> 1.5145326450001448

Бих избрал версията append за яснота и бързина.

За пояснение, не мисля, че методът append е значително по-бърз от версията inplace; Просто мисля, че е малко по-ясно.

Въпреки това, тъй като беше поискано:

first_random = urandom(100000)
second_random = urandom(100000)

min(Timer(partial(bxor_inplace, first_random, second_random)).repeat(10, 100))
#>>> 1.5381054869794752
min(Timer(partial(bxor_append, first_random, second_random)).repeat(10, 100))
#>>> 1.5196998479950707