python - 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

这是分析代码:

import string
import time
import random
from NumString import Numstring
import numpy as np
import matplotlib.pyplot as plt
if __name__ == '__main__':
    

    numstring_times = []
    regstring_times = []

    numstring = Numstring("abc")
    regstring = "abc"

    for i in range(0, 10000):
        char_to_add = random.choice(string.ascii_letters)
        
        start_time = time.time()
        numstring.append(char_to_add)
        end_time = time.time()

        numstring_times.append(end_time-start_time)

        start_time = time.time()
        regstring += char_to_add
        end_time = time.time()

        regstring_times.append(end_time-start_time)

    plt.plot(numstring_times, label="Numstring")
    plt.plot(regstring_times, label="Regular strings")
    plt.legend()
    plt.show()

它以我想要的方式工作，但是当我测试附加到字符串所需的时间时，我的 Numstring 类的表现要差得多。我知道会有开销，但我没想到整体趋势会比在 python 中连接字符串更糟糕。

奇怪的是，Numstrings 的比较时间实际上比常规字符串更好:

我意识到我并不真正了解 Python 中的整数运算是如何实现的，以及无限整数精度的局限性是什么。有人可以帮助我了解我缺少什么吗？

Answer 1

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