获取字符串中不同索引数的快速方法

Question

我想得到两个不同的字符串中的索引数。你知道吗

固定的东西：

字符串数据在任何索引上只有0或1。i、 字符串是数字的二进制表示形式。你知道吗

两条线的长度相同。你知道吗

对于上面的问题，我用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

未经测试，但其性能如何：

sum(x!=y for x,y in zip(a,b))

Answer 2

我将在这里介绍这些选项，但基本上你是在计算两个数字之间的汉明距离。有一些专用的库可以让这个过程非常非常快，但是让我们首先关注纯Python选项。你知道吗

你的方法，拉链

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

from itertools import izip

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

这样一次只生成一对，避免了必须先创建一个大的元组列表。你知道吗

Python布尔类型是int的子类，其中True == 1和False == 0，允许您对它们求和：

>>> True + True
2

改为使用整数

但是，您可能需要重新考虑您的输入数据。使用整数来表示二进制数据要有效得多；整数可以直接操作。内联进行转换，然后计算XOR结果上的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

如果输入变大，XOR方法的速度会快上几个数量级，这就是先将输入转换成int。你知道吗

用于位计数的专用库

位计数（format(integer, 'b').count(1)）非常快，但是如果安装^{} 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位数）：

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以上数字之间汉明距离的10万倍。你知道吗

另一个可以计算距离的包是^{}，它支持直接计算字符串之间的汉明距离。你知道吗

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

再次将其与具有位计数的异或方法进行比较：

>>> 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()函数在使用整数时仍然优于它。你知道吗

Answer 3

如果字符串表示二进制数，则可以转换为整数并使用位运算符：

def foo(s1, s2):
    # return sum(map(int, format(int(a, 2) ^ int(b, 2), 'b'))) # one-liner
    a = int(s1, 2) # convert string to integer 
    b = int(s2, 2)
    c = a ^ b # use xor to get differences
    s = format(c, 'b') # convert back to string of zeroes and ones
    return sum(map(int, s)) # sum all ones (count of differences)

s1 = "0100010010"
s2 = "0011100010"
     # 12345

assert foo(s1, s2) == 5