Python远程查找表

我想创建一个类似于Python中的字典的数据结构，但使用范围键。这里是场景：Python远程查找表

我正在实现一种编程语言，以便与旧游戏向后兼容。游戏中的每条指令都放入一个列表中，每次遇到换行符时计数器都会增加。希望如果语言有运行时错误，它将能够查找表中的指令所在的行并将其显示回给用户。

因此，在指令20如果发生错误，和3号线包含指令15-30，然后查询这个结构为20应该返回3.

有一个字典，为每一个指令的入口是可能的，但也非常浪费。有没有另一种方法可以做到这一点？

来源

2012-03-14 Kelketek

听起来像直方图... – 2012-03-14 01:45:06

我不这么认为。直方图有重叠。那些更多的是'x有多少在y'中，而不是'哪个x在y'。 – Kelketek 2012-03-14 01:53:22

结构中有多少条指令，字典可能空间效率不高，但可能不够大。 – 2012-03-14 02:07:03

从你的描述，你有一个单调递增计数器和形式的地图功能（以下常数正好弥补了例如）：

0 <= x < 5: 0 
5 <= x < 7: 1 
7 <= x < 10: 2 
10 <= x < 18: 3 
18 <= x < 21: 4

它好像一个简单的数组（列表，在Python ）的转换点就足够了：

[5, 7, 10, 18, 21]

然后给出x，您会发现i的最低值，使得arr [i]> = x。

您可以使用内插搜索找到该索引，该索引大致为O（log log n），其中n是数组的长度（代码保留为练习:-)）。

来源

2012-03-14 02:03:20 torek

这个答案简单而优雅。我喜欢。我会试试这个。如果它有效，你可以保留你的对号:) – Kelketek 2012-03-14 03:14:50

顺便说一句，如果你想节省一些空间，把列表转换成一个'array.array（'I'）'或者（甚至H或B，如果最大值是足够小）。当然，不像指令计数数组那么明显，或者从指令编号直接映射到行号的数组。 – torek 2012-03-23 04:55:56

下面是该调整字典键的一类：

class rdict(dict): 

    def __init__(self, incSize, *args): 
     self.incSize = incSize 
     dict.__init__(self, *args) 

    def __normRange(self, keyArg, incSize): 
     return keyArg // incSize * incSize 

    def __getitem__(self, key): 
      return dict.__getitem__(self, self.__normRange(key, self.incSize)) 

     def __setitem__(self, key, value): 
      dict.__setitem__(self, self.__normRange(key, self.incSize), value) 

    g = input("hi") 
    d = rdict(3) 
    d[10.4] = "a" 
    print d

它输出： {9.0：“一”}

如果你不打算多使用它，忘记了阶级和只需通过函数运行你的输入normRange

来源

2012-03-14 02:05:23

“有一本词典包含每条指令的条目是可能的，但也非常浪费。”你期望用这种语言编写的程序长达数百万条指令吗？如果不是，这正是我所推荐的。不要过早优化。大多数人将这句谚语解释为表达性，但也适用于资源利用。

如果您确实需要优化空间，假设您使用的是Python 2.6或更高版本，我推荐的是bytearray。顾名思义，它是一个字节数组，因此可以表示0-255的值。数组中的每个项目将表示相应行中的语句数目。为了从指令数回行数转换将是这样的：

instcounts = bytearray((2, 4, 6, 3, 1, 1, 5, 2, 3)) 

def getline(instnumber): 
    count = line = 0 
    while count <= instnumber and line < len(instcounts): 
     count += instcounts[line] 
     line += 1 
    return line # conveniently, this will be 1-indexed :-) 

getline(15) # tells me instruction 15 is on line 5

的这种过度托雷克的回答的优点是，它基本上是存储相同的信息在每个源代码行只有一个字节：很多比列表更有效率。你必须做一些额外的工作来确定行号，但实际上，即使在非常大的文件中你也不会注意到，并且只有在打印错误消息时才会运行它，而不是速度关键功能。上述函数在代表1,000,000行的bytearray上大约需要十分之一秒，这是在运行于4年历史的Mac Pro上的Windows XP虚拟机上的Python 3.1下的未经优化的代码。

需要储存空间？ 1,087,199字节，约为所需的数量的四分之一，仅用于torek解决方案中的列表 - 不包括列表中引用的int对象，每个对象都是14个字节（CPython重用了一个小整数对象池，但是，所以如果有任何额外的整数内存，小文件可能不会使用太多）。

顺便说一句，CPython使用非常类似的方案（请参阅func_code.co_lnotab或__code__.co_lnotab关于任何函数）。

来源

2012-03-14 02:08:43 kindall

我提高了您的解决方案，这在实践中可能会更好。 – torek 2012-03-14 05:48:30

取决于您正在优化的内容。你可以让你做内插搜索，这意味着你会发现更快的线。每种教学法与我的方法之间有一种中间立场。 – kindall 2012-03-14 05:50:01

Python远程查找表

回答

相关问题