Python中的整数运算是如何实现的？

Question

这可能是一个非常广泛的问题。我想创建一种表示字符串的方法，该方法支持 O(1) 追加、O(1) 向左追加和 O(1) 比较，同时保持 O(N) 切片和 O(1) 索引。我的想法是，我将 unicode 字符存储为其 unicode 编号，并使用数学运算从两端添加和删除字符。我将其命名为“NumString”：

class Numstring:

    def __init__(self, init_str=""):

        self.num = 0

        self.length = 0

        for char in init_str:

            self.append(char)

    def toString(self, curr=None):

        if curr is None:

            curr = self.num

        retlst = []

        while curr:

            char = chr(curr % 10000)

            retlst.append(char)

            curr = curr // 10000

        return "".join(retlst)

    def appendleft(self, char):

        assert len(char) == 1

        self.num *= 10000

        self.num += ord(char)

        self.length += 1

    def append(self, char):

        self.num += ord(char)*(10000**self.length)

        self.length += 1    

    def pop(self):

        # self.num = self.num % (10000**self.length-1)

        self.num = self.num % 10000**(self.length-1)

        self.length -= 1

    def popleft(self):

        self.num = self.num // 10000

        self.length -= 1

    def compare(self, numstring2):

        return self.num == numstring2.num

    def size(self):

        return self.length

    def get(self, start, end=None):

        if start >= self.length:

            raise IndexError("index out of bounds")

        if end and end > self.length + 1:

            raise IndexError("index out of bounds")

        if end is not None:

            if start == end:

                return ""

            curr = self.num

            curr = curr // (10000 ** start)

            curr = curr % 10000**(end)

            return self.toString(curr)

        else:

            curr = self.num

            curr = curr // (10000 ** start)

            char = chr(curr % 10000)

            return char

Answer 1

ints 本质上表示为数字字符串（基数高于 10），对它们进行的大多数操作（包括加法和乘法）所花费的时间与它们包含的数字数量成正比，甚至更糟。由于您使用的基数 (10000) 与基数int的使用不匹配，因此乘以或除以基数等操作会变成复杂的操作，而不是简单地复制内存字节。因此，它几乎是对已经执行的操作字符串的效率较低的重新实现（这是您通过基准测试发现的），并且它不支持所有 Unicode（最高可达 0x10FFFF，而不是 10000）。不过，提示实际上具有您正在寻找的属性的数据结构：基于循环缓冲区的双端队列。