比较两个字符串是否相等的超级快速方法

Question

显然，在Python中检查两个字符串是否相等你可以这样做：

\n\n

"hello word" == "hello world"

\n\n

但是，如果您要比较很长的字符串（超过 100 万个字符）怎么办？python 中是否有内置方法或任何库可以更快地完成此操作；也许利用 Karp\xe2\x80\x93Rabin 算法或类似的算法？

\n\n

或者，在幕后， stringA == stringB 实际上是最快的方法吗？

\n

Answer 1

（已编辑：提高整体质量）。

\n\n

考虑到如何str == str在Python 中实现，这首先得到一个id()检查、长度检查，然后逐个元素进行。\n这非常快且可以理解，因为很多 Python 代码都依赖于此。\n在平均情况下，有无需进一步优化，因为任意字符串很早就会有所不同。

\n\n

然而，有两个用例有一些优化的空间：

\n\n

\n
• 你有一些关于如何的部分信息不同的部分信息。
\n
• 您在一组特定元素之间执行多重比较（请参阅@wim 评论）。
\n

\n\n\n\n

第一种情况的示例是：如果您知道当两个相同大小的输入不同时，它们至少对于连续元素可能不同，然后对每个元素m进行比较kk < m将是一个合理的选择，例如：

\n\n

def is_k_equal(a, b, k=4096):\n    if k in {0, 1}:\n        return a == b\n    else:\n        return a[::k] == b[::k]\n\n\ndef is_equal_partial(a, b, partial_match=is_k_equal):\n    return len(a) == len(b) and partial_match(a, b) and a == b\n

\n\n\n\n

第二种情况的一个例子是：如果你想知道哪些p输入q是两两相等的，计算输入的哈希值（例如使用hash()，但其他选项可能同样有效）并且只执行完整的哈希可能会有所帮助。哈希值匹配时进行比较。\n不言而喻，如果您的哈希值具有较高的冲突等级，它可能只会引入额外的开销（有关哈希值的信息，请参阅维基百科）。\n输入的哈希值可以手动管理，也可以通过函数中的哈希比较来保护您的完整is_equal()比较，例如：

\n\n

def is_equal_hashing(a, b, hashing=hash):\n    return len(a) == len(b) and hashing(a) == hashing(b) and a == b\n

\n\n

前提是您的哈希函数已被记忆。因为hash()您不需要执行任何其他操作，因为这些输入已经被记忆。\n如果您要使用更高级的哈希（例如 crc32、md5 等），您可能需要自己添加记忆，例如使用 . @functools.lru_cache\该用例从这种方法中获益的条件（忽略比较哈希值所需的时间，该时间通常比要考虑的其他操作快得多）是：

\n\n

t_h * n_h < t_c * n_c\n

\n\n

初始t_h哈希计算时间、要计算的唯一n_h哈希的数量、比较时间以及在输入末尾附近失败的完整比较的数量。t_cn_c

\n\n

当对输入的执行方式有疑问时，测量/分析您的代码通常是一个好主意。

\n\n

对记忆函数（如 ）进行计时时必须小心hash()，因为，如果您对非记忆路径的性能感兴趣，则不能像通常那样依赖同一输入的多次重复调用的计时，例如IPython%timeit使用默认参数。相反，您可以用于%timeit -n1 -r1未缓存的计时。结果仅对数量级估计有用。

\n\n

为了让您了解您的方法的可能成分有多快，这里有一些微基准：

\n\n

import hashlib\nimport functools\n\n\ndef md5(data):\n    return hashlib.md5(data).digest()\n\n\n@funtools.lru_cache(maxsize=16384)\ndef sha1(data):\n    return hashlib.sha1(data).digest()\n\n\ndef sha256(data):\n    return hashlib.sha1(data).digest()\n\n\ndef sha512(data):\n    return hashlib.sha1(data).digest()\n

\n\n

import numpy as np\nimport numba as nb\n\n\n@nb.jit(fastmath=True)\ndef hash_sum_nb(data, init=0):\n    dtype = np.uint64\n    nbytes = 8\n    n = len(data)\n    offset = n % nbytes\n    result = init\n    if offset:\n        body = np.frombuffer(data[:-offset], dtype=dtype)\n        tail = np.frombuffer(data[-offset:], dtype=np.uint8)\n        for x in tail:\n            result += x\n    else:\n        body = np.frombuffer(data, dtype=dtype)\n    for x in body:\n        result += x\n    return result + n\n

\n\n

import zlib\nimport string\nimport random\n\n\nn = 1_000_000\ns = b\'\'.join(string.printable[random.randrange(len(string.printable))].encode() for _ in range(n))\nfuncs = hash, hash, zlib.crc32, zlib.adler32, md5, sha1, sha1, sha256, sha512, hash_sum_nb\nfor func in funcs:\n    result = %timeit -n1 -r1 -q -o func(s)\n    print(f\'{func.__name__:>12s}  {result.best * 1e6:.3f} \xc2\xb5s\')\n#         hash  586.401 \xc2\xb5s\n#         hash  0.853 \xc2\xb5s\n#        crc32  976.128 \xc2\xb5s\n#      adler32  468.452 \xc2\xb5s\n#          md5  1790.659 \xc2\xb5s\n#         sha1  1362.948 \xc2\xb5s\n#         sha1  1.423 \xc2\xb5s\n#       sha256  1347.432 \xc2\xb5s\n#       sha512  1321.981 \xc2\xb5s\n#  hash_sum_nb  64.768 \xc2\xb5s\n\n\ncases = {\n    \'worst case\': (s[:-1] + b\'x\', s[:-1] + b\'y\'),\n    \'best case*\': (s[:-1], s[:-2]),\n    \'best case\': (b\'x\' + s[:-1], b\'y\' + s[:-1]),\n}\nfor name, (a, b) in cases.items(): \n    result = %timeit -n1 -r1 -q -o a == b\n    print(f\'str == str ({name:10s})  {result.best * 1e6:.3f} \xc2\xb5s\')\n# str == str (worst case)  142.466 \xc2\xb5s\n# str == str (best case*)  0.856 \xc2\xb5s\n# str == str (best case )  1.012 \xc2\xb5s\n\n\na, b = (s[:-1] + b\'x\', s[:-1] + b\'y\')\nresult = %timeit -n1 -r1 -q -o is_k_equal(a, b)\nprint(f\'{is_k_equal.__name__:>12s}  {result.best * 1e6:.3f} \xc2\xb5s\')\n# is_k_equal  10.037 \xc2\xb5s\n

\n\n

请注意，在同一输入上调用hash()和sha1()两次以显示记忆的效果。

\n\n

有了这些数据（或您可以在输入/系统上生成的类似数字），就有可能制作出性能更高的字符串相等性比较。\n请注意，我在整个答案中都使用了替代方法bytes。\n的计时str通常会更糟大多数散列，因为处理编码需要额外的开销，但hash().

\n\n\n