This might be a very broad question. I wanted to create a way to represent strings that would support O(1) append, O(1) append to the left, and O(1) comparison while maintaining O(N) slicing and O(1) indexing. My idea is that I would store unicode characters as their unicode number, and use mathematical operations to add and delete characters from either end. I called it 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
Here is the profiling code:
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()
It works the way I want it to, but when I tested the time it takes to append to the string and my Numstring class performed way worse. I understood that there would be overhead, but I didn't expect the overall trend to be way worse than concatenating strings in python.
Curiously, comparison times are actually better for Numstrings than regular strings:
I've realized I don't really understand how integer operations in Python are implemented and what the limitations of infinite integer precision are. Could somebody help me understand what I'm missing?
