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）。

不过，提示实际上具有您正在寻找的属性的数据结构：基于循环缓冲区的双端队列。