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

Question

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

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 尝试就地调整字符串大小，而不是构建新字符串并复制 的所有数据。当它起作用时，它可以避免您在基于整数的实现中进行的大部分不必要的复制。

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