为什么在处理二进制字符串的问题中使用整数比使用字符串慢得多？

Question

我解决了以下leet代码问题https://leetcode。 com/problems/find-kth-bit-in-nth-binary-string/ 使用字符串（类 Solution）和整数（类解决方案2）。我认为整数解决方案应该更快并且使用更少的内存。但实际上需要更长的时间。当 n=18 和 k=200 时，需要 10.1 秒，而字符串解决方案需要 0.13 秒。

import time

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        i = 0
        Sn = "0"
        Sn = self.findR(Sn, i, n)
        return Sn[k-1]

    def findR(self, Sn, i, n):
        if i == n:
            return Sn
        newSn = self.calcNewSn(Sn, i)
        return self.findR(newSn, i+1, n)

    def calcNewSn(self, Sn, i):
        inverted = ""
        for c in Sn:
            inverted += "1" if c == "0" else "0"
        newSn = Sn + "1" + (inverted)[::-1]
        return newSn


class Solution2:
    def findKthBitBin(self, n: int, k: int) -> str:
        i = 0
        # MSB (S1) has to be 1 for bit operations but is actually always 0
        Sn = 1
        Sn = self.findRBin(Sn, i, n)
        lenSn = (2**(n+1)) - 1
        return "0" if k == 1 else str((Sn >> (lenSn - k)) & 1)

    def findRBin(self, Sn, i, n):
        if i == n:
            return Sn
        newSn = self.calcNewSnBin(Sn, i)
        return self.findRBin(newSn, i+1, n)

    def calcNewSnBin(self, Sn, i):
        lenSn = 2**(i+1) - 1
        newSn = (Sn << 1) | 1
        inverted = (~Sn | (1 << (lenSn - 1))) & self.getMask(lenSn)
        newSn = self.reverseBits(newSn, inverted, lenSn)
        return newSn

    def getMask(self, lenSn):
        mask = 0
        for i in range(lenSn):
            mask |= (1 << i)
        return mask

    def reverseBits(self, newSn, inverted, lenSn):
        for i in range(lenSn):
            newSn <<= 1
            newSn |= inverted & 1
            inverted >>= 1
        return newSn
 
sol = Solution()
sol2 = Solution2()

start = time.time()
print(sol.findKthBit(18, 200))
end = time.time()
print(f"time using strings: {end - start}")
start = time.time()
print(sol2.findKthBitBin(18, 200))
end = time.time()
print(f"time using large integers: {end - start}")

为什么使用整数的解决方案这么慢？与字符串相比，其他语言中大整数的实现是否更快？

Answer 1

问题不在于整数实现有多快或多慢。问题是您编写了一个需要随机访问可变序列数据类型（如列表）的算法，而整数不是随机访问可变序列。

例如，查看您的 reverseBits 实现：

def reverseBits(self, newSn, inverted, lenSn):
    for i in range(lenSn):
        newSn <<= 1
        newSn |= inverted & 1
        inverted >>= 1
    return newSn

对于列表，您只需调用 list.reverse() 即可。相反，您的代码会一遍又一遍地转换 newSn 和 inverted，在每次迭代中重复复制几乎所有涉及的数据。

字符串也不是一种随机访问的可变序列数据类型，但它们更接近，并且 Python 的标准实现有一个奇怪的优化，它实际上确实尝试像您编写的那样在循环中改变字符串：

def calcNewSn(self, Sn, i):
    inverted = ""
    for c in Sn:
        inverted += "1" if c == "0" else "0"
    newSn = Sn + "1" + (inverted)[::-1]
    return newSn

而不是构建一个新字符串并复制 += 的所有数据，Python 尝试就地调整字符串大小。当它起作用时，它可以避免您在基于整数的实现中进行的大部分不必要的复制。

---

编写算法的正确方法是使用列表，而不是字符串或整数。然而，还有一种更好的方法，采用不同的算法，根本不需要构建位序列。您不需要整个位序列。您只需要计算一位即可。弄清楚如何计算那一点。

Answer 2

大部分时间花在 reverseBits() 上。总的来说，您将在其中创建数十万个新的整数对象，长度最多为 262143 位。它本质上是二次时间。字符串形式的相应操作就是(inverted)[::-1]，它完全以“C 速度”运行，并且是最坏情况的线性时间。

低级别、高级别

只需替换 reverseBits() 即可获得 8 倍的加速，

    def reverseBits(self, newSn, inverted, lenSn):
        inverted = int(f"{inverted:0{lenSn}b}"[::-1], 2)
        return (newSn << lenSn) | inverted

即线性时间。它将inverted转换为位字符串，反转该字符串，然后将结果转换回int。其他技巧可用于加速其他过慢的 bigint 算法。

但是，正如另一个答案（你应该接受！）所说，只见树木不见森林：整个方法偏离了最佳轨道。即使使用更简单的代码，也可以编写一个函数，使所有这些都运行得非常快（每次调用的最坏情况是O(n)），并且只需要微不足道的工作内存

>>> [findKthBit(4, i) for i in range(1, 16)] == list("011100110110001")
True
>>> findKthBit(500, 2**20)
'1'
>>> findKthBit(500, 2**20 - 1)
'1'
>>> findKthBit(500, 2**20 + 1)
'0'

：世界有足够的内存来构建一个包含 2**500-1 字符的字符串（或具有这么多位的 bigint）。