python - 获取字符串中不同索引数量所需的快速方法

Question

我想获取两个不相同的字符串中的索引数。

固定的东西:

字符串数据在任何索引上只会有 0 或 1。即字符串是数字的二进制表示。

两个字符串的长度相同。

针对上面的问题我用python写了下面的函数

def foo(a,b):
    result = 0
    for x,y in zip(a,b):
        if x != y:
            result += 1
    return result

但问题是这些字符串很大。很大。所以上述功能花费了太多时间。我应该做些什么来让它变得超快。

这就是我在 C++ 中做同样的事情，它现在相当快，但仍然无法理解如何用短整数打包以及@Yves Daoust 所说的所有内容:

size_t diff(long long int n1, long long int n2)
{
long long int c = n1 ^ n2;
bitset<sizeof(int) * CHAR_BIT> bits(c);
string s = bits.to_string();

return std::count(s.begin(), s.end(), '1');

}

Answer 1

我将在此处详细介绍这些选项，但基本上您是在计算两个数字之间的汉明距离。有专门的库可以让这一切变得非常非常快，但让我们首先关注纯 Python 选项。

你的方法，压缩

zip() 首先生成一个大列表，然后让您循环。您可以改用 itertools.izip()，并使其成为生成器表达式:

from itertools import izip

def foo(a, b):
    return sum(x != y for x, y in izip(a, b))

这一次只生成一对，避免必须先创建一个大的元组列表。

Python bool 类型是 int 的子类，其中 True == 1 和 False == 0，让您将它们相加:

>>> True + True
2

改用整数

但是，您可能需要重新考虑您的输入数据。使用整数表示二进制数据效率更高；整数可以直接操作。进行内联转换，然后计算异或结果中 1 的个数为:

def foo(a, b):
    return format(int(a, 2) ^ int(b, 2), 'b').count('1')

但不必首先将 a 和 b 转换为整数会更有效率。

时间比较:

>>> from itertools import izip
>>> import timeit
>>> s1 = "0100010010"
>>> s2 = "0011100010"
>>> def foo_zipped(a, b): return sum(x != y for x, y in izip(a, b))
... 
>>> def foo_xor(a, b): return format(int(a, 2) ^ int(b, 2), 'b').count('1')
... 
>>> timeit.timeit('f(s1, s2)', 'from __main__ import s1, s2, foo_zipped as f')
1.7872788906097412
>>> timeit.timeit('f(s1, s2)', 'from __main__ import s1, s2, foo_xor as f')
1.3399651050567627
>>> s1 = s1 * 1000
>>> s2 = s2 * 1000
>>> timeit.timeit('f(s1, s2)', 'from __main__ import s1, s2, foo_zipped as f', number=1000)
1.0649528503417969
>>> timeit.timeit('f(s1, s2)', 'from __main__ import s1, s2, foo_xor as f', number=1000)
0.0779869556427002

如果输入变大，异或方法会快几个数量级，这是首先将输入转换为int。

用于比特计数的专用库

位计数 (format(integer, 'b').count(1)) 非常快，但如果安装 gmpy extension library(围绕 GMP library 的 Python 包装器)，还可以变得更快) 并使用了 gmpy.popcount() 函数:

def foo(a, b):
    return gmpy.popcount(int(a, 2) ^ int(b, 2))

gmpy.popcount() 在我的机器上比 str.count() 方法快大约 20 倍。同样，不必首先将 a 和 b 转换为整数将消除另一个瓶颈，但即使这样，每次调用的性能也几乎翻了一番:

>>> import gmpy
>>> def foo_xor_gmpy(a, b): return gmpy.popcount(int(a, 2) ^ int(b, 2))
... 
>>> timeit.timeit('f(s1, s2)', 'from __main__ import s1, s2, foo_xor as f', number=10000)
0.7225301265716553
>>> timeit.timeit('f(s1, s2)', 'from __main__ import s1, s2, foo_xor_gmpy as f', number=10000)
0.47731995582580566

为了说明当 a 和 b 是整数开头时的区别:

>>> si1, si2 = int(s1, 2), int(s2, 2)
>>> def foo_xor_int(a, b): return format(a ^ b, 'b').count('1')
... 
>>> def foo_xor_gmpy_int(a, b): return gmpy.popcount(a ^ b)
... 
>>> timeit.timeit('f(si1, si2)', 'from __main__ import si1, si2, foo_xor_int as f', number=100000)
3.0529568195343018
>>> timeit.timeit('f(si1, si2)', 'from __main__ import si1, si2, foo_xor_gmpy_int as f', number=100000)
0.15820622444152832

汉明距离专用库

gmpy 库实际上包含一个 gmpy.hamdist() 函数，它计算这个精确数字(整数异或结果中 1 的位数) < em>直接:

def foo_gmpy_hamdist(a, b):
    return gmpy.hamdist(int(a, 2), int(b, 2))

如果您使用整数开头，那完全会让您大吃一惊:

def foo_gmpy_hamdist_int(a, b):
    return gmpy.hamdist(a, b)

比较:

>>> def foo_gmpy_hamdist(a, b):
...     return gmpy.hamdist(int(a, 2), int(b, 2))
... 
>>> def foo_gmpy_hamdist_int(a, b):
...     return gmpy.hamdist(a, b)
... 
>>> timeit.timeit('f(s1, s2)', 'from __main__ import s1, s2, foo_xor as f', number=100000)
7.479684114456177
>>> timeit.timeit('f(s1, s2)', 'from __main__ import s1, s2, foo_gmpy_hamdist as f', number=100000)
4.340585947036743
>>> timeit.timeit('f(si1, si2)', 'from __main__ import si1, si2, foo_gmpy_hamdist_int as f', number=100000)
0.22896099090576172

这是两个 3k+ 数字之间汉明距离的 100.000 倍。

另一个可以计算距离的包是 Distance ，它支持直接计算字符串之间的汉明距离。

确保使用 --with-c 开关让它编译 C 优化；使用 pip 安装时，例如使用 bin/pip install Distance --install-option --with-c。

再次针对 XOR-with-bitcount 方法进行基准测试:

>>> import distance
>>> def foo_distance_hamming(a, b):
...     return distance.hamming(a, b)
... 
>>> timeit.timeit('f(s1, s2)', 'from __main__ import s1, s2, foo_xor as f', number=100000)
7.229060173034668
>>> timeit.timeit('f(s1, s2)', 'from __main__ import s1, s2, foo_distance_hamming as f', number=100000)
0.7701470851898193

它使用了朴素的方法；压缩两个输入字符串并计算差异的数量，但由于它在 C 中执行此操作，因此速度仍然快得多，大约快 10 倍。但是，当您使用整数时，gmpy.hamdist() 函数仍然胜过它。