在Python 3中快速异或字节

Question

我需要对两个字节对象进行异或运算。我用的代码是：

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

当字节对象很小的时候，这段代码运行得很好，但如果字节对象很大（几兆字节），就会花很长时间（几个小时）。我该怎么做才能让它更快呢？

Answer 1

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

Answer 2

使用 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 对象。

由 delnan 提出的 b''.join() 方法其实和原来的版本差不多，没有太大改善：

>>> 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() 比重复拼接要快。

最后，我用 bytearray 版本进行了700万字节的测试，重复了10次，其他版本我已经没耐心再用了：

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

Answer 3

在这里补充一下，因为这是一个很重要的点：

如果你想要比之前提到的“手动”方法更快的选择，可以试试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倍。

Answer 4

当你对一百万个元素的bytes对象进行异或操作时，这个循环大约会创建一百万个临时的bytes对象，并且平均每个字节大约会被复制五十万次，从一个临时bytes对象到下一个。需要注意的是，字符串在很多其他语言中也会遇到同样的问题。解决字符串问题的方法是先创建一个字符串部分的列表，最后用''.join来高效地把它们连接起来。对bytes也可以用同样的方法：

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，它是可变的，因此可以避免这个问题。使用bytearray时，你不需要在每次循环中都分配一个新的bytes对象，你可以直接添加字节或int。

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

如果你想要或需要一个bytes对象，你也可以选择return bytes(result)。