logo标签列表

Python 3中快速进行XOR字节操作

pythonpython-3.xxor
7

我需要对两个字节对象进行异或操作。我使用以下代码：

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

当字节对象很小的时候，它可以正常工作，但如果我对大型对象（几MB）进行异或运算，它会花费很长时间（几个小时）。我该如何使它更快？

2
这可能会有所帮助：https://dev59.com/yHI95IYBdhLWcg3w2h56 - devnull
4个回答
10

在另一个答案中，添加了以下内容，因为它是一个方法：

如果你想要比给出的“手动”方法更快的方式，那么总有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倍。

8
当使用每个拥有一百万元素的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，从而避免该问题。它还允许您在每次迭代时不必分配新的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

你可以选择 return bytes(result) 如果你需要一个 bytes 对象。
b''.join()并不更快；在我的测试中，它实际上稍微慢一些。 - Martijn Pieters
我正在计时70个字节，并添加了一个7000个字节的测试。bytes.join()在有更多字节的情况下有所改善。 - Martijn Pieters
3
在进行一百万字节的测试中， bytes(map(operator.xor, b1, b2)) 的运行时间约为原始代码的一半。该代码用于按位异或两个字节对象并返回结果的字节对象。 - Eryk Sun
7

使用 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()比重复连接更快。

最后一个700万字节的运行，仅使用bytearray版本，重复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
1
它不仅仅是快了9倍，随着字符串变得越来越长，差距增长得非常快。但让人放心的是，渐进式更快的选项对于小输入也更快。 - user395760
2
马尔廷·皮特斯的时间表与我的有些不同：
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
2
.timeit(1)比玩弄time.time要好一点，你需要更多的迭代来消除噪音。 - user395760
通常情况下这是正确的，但是随着操作规模的增大，噪音可能会变得微不足道（在对数尺度上）。实际上，timeit(N) 不会做任何事情；你需要使用 .repeat。 - Veedrac
我不怀疑7.9秒与1.5秒的重要性，但我确实怀疑1.515秒与1.543秒的重要性（“我会选择append版本以获得更快的速度”）。是的，你需要使用repeat()。 - user395760
是的，但我只把它们视为相同的数字。如果由于您的操作规模而0.03秒很重要，那么最好使用Numpy重新编写此代码。 - Veedrac
bytearray.append() 在进行 10 次，每次处理 700 万字节的情况下是完全可比的；只要使用 bytearray，你选择哪个并不完全重要。 - Martijn Pieters
@Veedrac 我也将它们视为相同的数字，因此（正如Marijn所说），没有理由基于速度而更喜欢其中一个bytearray版本。 - user395760
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接