這可能是一個非常廣泛的問題。我想創建一種表示字符串的方法,該方法支持 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
1 回答

慕桂英546537
TA貢獻1848條經驗 獲得超10個贊
int
s 本質上表示為數字字符串(基數高于 10),對它們進行的大多數操作(包括加法和乘法)所花費的時間與它們包含的數字數量成正比,甚至更糟。由于您使用的基數 (10000) 與基數int
的使用不匹配,因此乘以或除以基數等操作會變成復雜的操作,而不是簡單地復制內存字節。因此,它幾乎是對已經執行的操作字符串的效率較低的重新實現(這是您通過基準測試發現的),并且它不支持所有 Unicode(最高可達 0x10FFFF,而不是 10000)。
不過,提示實際上具有您正在尋找的屬性的數據結構:基于循環緩沖區的雙端隊列。
添加回答
舉報
0/150
提交
取消