在 Python 中表示图灵机的无限磁带的最有效方法是什么?
What is the most efficient way to represent the infinite tape of a Turing machine in Python?
A Turing machine 根据 table 规则操纵 无限条带 上的符号。
在我的例子中,磁带上的条目可以是 0 和 1(二进制)。
磁带从 'empty' 开始,正向和负向都为无穷大的 0。此磁带根据机器遵循的规则写入,可能会在未写入的边缘添加 0 或 1。
由于磁带值是二进制的,是否有一种最有效的方法可以在机器写入磁带时在内存中表示它们,向左侧或右侧添加新值?显然我不需要表示无限零(未写入的磁带),但我确实需要扩展数据结构,因为新值被添加到磁带的末端。
python 列表可以解决问题,此处显示在左侧插入 1:
start_time = time.time()
tape = [0]*10000000
print tape[:10]
insertion_time = time.time()
tape = [1] + tape
print tape[:10]
print "total execution time: ", time.time() - start_time
print "time to add entry: ", time.time() - insertion_time
这输出:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
total execution time: 0.257364034653
time to add entry: 0.109524011612
使用 list.insert 确实使速度提高了 23 倍:
start_time = time.time()
tape = [0]*100000
print tape[:10]
insertion_time = time.time()
tape.insert(0, [1])
print tape[:10]
print "execution time: ", time.time() - start_time
print "time to add entry: ", time.time() - insertion_time
给予:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[[1], 0, 0, 0, 0, 0, 0, 0, 0, 0]
execution time: 0.0270080566406
time to add entry: 0.00468802452087
有没有比使用 list
对象更有效的表示二进制磁带的方法?
鉴于磁带的两端是无限的,您还必须考虑 (-inf, -1]
索引范围。最好的表示,IMO,将是一对列表 - 一个用于非负范围,另一个用于负范围(索引反转)。当您超出磁带的分配范围时,您只需附加到相应的列表(与添加到列表不同,这是一个快速操作)。
实施草案(使用 this answer 中 GrowingList
的增强版):
class GrowingList(list):
def __init__(self, default_value):
self.default_value=default_value
def __getitem__(self, i):
return list.__getitem__(i) if i < len(self) else self.default_value
def __setitem__(self, i, v):
if i >= len(self):
self.extend([self.default_value]*(i + 1 - len(self)))
list.__setitem__(self, i, v)
class Tape:
def __init__(self):
self.pos_range=GrowingList(0)
self.neg_range=GrowingList(0)
def __getitem__(self, i):
if i >= 0:
return self.pos_range[i]
else:
return self.neg_range[-i-1]
def __setitem__(self, i, v):
if i >= 0:
self.pos_range[i]=v
else:
self.neg_range[-i-1]=v
def __repr__(self):
start = -len(self.neg_range)
end = len(self.pos_range)
data = list(reversed(self.neg_range)) + self.pos_range
return "Tape(range=[{}, {}), data={})".format(start, end, data)
t = Tape()
print(t)
t[4]=1
print(t)
t[-2]=1
print(t)
输出:
Tape(range=[0, 0), data=[])
Tape(range=[0, 5), data=[0, 0, 0, 0, 1])
Tape(range=[-2, 5), data=[1, 0, 0, 0, 0, 0, 1])
A Turing machine 根据 table 规则操纵 无限条带 上的符号。
在我的例子中,磁带上的条目可以是 0 和 1(二进制)。
磁带从 'empty' 开始,正向和负向都为无穷大的 0。此磁带根据机器遵循的规则写入,可能会在未写入的边缘添加 0 或 1。
由于磁带值是二进制的,是否有一种最有效的方法可以在机器写入磁带时在内存中表示它们,向左侧或右侧添加新值?显然我不需要表示无限零(未写入的磁带),但我确实需要扩展数据结构,因为新值被添加到磁带的末端。
python 列表可以解决问题,此处显示在左侧插入 1:
start_time = time.time()
tape = [0]*10000000
print tape[:10]
insertion_time = time.time()
tape = [1] + tape
print tape[:10]
print "total execution time: ", time.time() - start_time
print "time to add entry: ", time.time() - insertion_time
这输出:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
total execution time: 0.257364034653
time to add entry: 0.109524011612
使用 list.insert 确实使速度提高了 23 倍:
start_time = time.time()
tape = [0]*100000
print tape[:10]
insertion_time = time.time()
tape.insert(0, [1])
print tape[:10]
print "execution time: ", time.time() - start_time
print "time to add entry: ", time.time() - insertion_time
给予:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[[1], 0, 0, 0, 0, 0, 0, 0, 0, 0]
execution time: 0.0270080566406
time to add entry: 0.00468802452087
有没有比使用 list
对象更有效的表示二进制磁带的方法?
鉴于磁带的两端是无限的,您还必须考虑 (-inf, -1]
索引范围。最好的表示,IMO,将是一对列表 - 一个用于非负范围,另一个用于负范围(索引反转)。当您超出磁带的分配范围时,您只需附加到相应的列表(与添加到列表不同,这是一个快速操作)。
实施草案(使用 this answer 中 GrowingList
的增强版):
class GrowingList(list):
def __init__(self, default_value):
self.default_value=default_value
def __getitem__(self, i):
return list.__getitem__(i) if i < len(self) else self.default_value
def __setitem__(self, i, v):
if i >= len(self):
self.extend([self.default_value]*(i + 1 - len(self)))
list.__setitem__(self, i, v)
class Tape:
def __init__(self):
self.pos_range=GrowingList(0)
self.neg_range=GrowingList(0)
def __getitem__(self, i):
if i >= 0:
return self.pos_range[i]
else:
return self.neg_range[-i-1]
def __setitem__(self, i, v):
if i >= 0:
self.pos_range[i]=v
else:
self.neg_range[-i-1]=v
def __repr__(self):
start = -len(self.neg_range)
end = len(self.pos_range)
data = list(reversed(self.neg_range)) + self.pos_range
return "Tape(range=[{}, {}), data={})".format(start, end, data)
t = Tape()
print(t)
t[4]=1
print(t)
t[-2]=1
print(t)
输出:
Tape(range=[0, 0), data=[])
Tape(range=[0, 5), data=[0, 0, 0, 0, 1])
Tape(range=[-2, 5), data=[1, 0, 0, 0, 0, 0, 1])