使用数组片段作为键的Python关联数组

Question

如何更好地实现这样的功能：

遍历这些数字。每个数字都在一个范围内，并且属于一个关联数组的某一部分。

例如：

 di = {}
 di[ xrange(0,10) ] = "A"
 di[ xrange(11,20) ] = "B"
 di[ xrange(21,30) ] = "C"

 direction = di[ 24 ]
 # direction should be "C"

 direction = di[ 6 ]
 # direction should be "A"

补充：我并不打算用离散的数字填满整个 di，因为我说的是IP地址，实际上是非常庞大的数据，比如网络掩码255.255.255.255。这样的 di 会占满我的内存。

Answer 1

你可以用元组来代替列表，这样可以解决TypeError（不过你的代码其实并没有出现这个错误）。不过，即使这样，查找还是不会成功。最简单的方法是把你的字典填充上每个特定值对应的所有不同的键，也就是说：

map = (
   (0, 10, "A"),
   (11, 20, "B"),
   # etc
   )

d = {}
for start, stop, val in map:
   for k in xrange(start, stop):
       d[k] = val

Answer 2

如果你不想填充一个字典，那就直接用一个函数就行了。

from __future__ import division
import string
def return_ltr(i):
    n = i//10 
    return string.ascii_uppercase[n]

如果你想填充一个字典，可以这样做。你现在的代码生成了 xrange 对象，并把它们当作字典的键。但这和直接用数字作为键是不一样的。试试下面的代码：

import string
d = {}
i = 0
for ltr in string.ascii_uppercase:
    for j in xrange(10):
        d[i] = ltr
        i += 1

如果你只想要字母的一部分，可以对 string.ascii_uppercase 进行切片。例如，使用 string.ascii_uppercase[0:3] 只会给你 A、B 和 C。

Answer 3

di = dict.fromkeys(xrange(0, 10), 'A')
di.update(dict.fromkeys(xrange(10, 20), 'B'))
di.update(dict.fromkeys(xrange(20, 30), 'C'))
print(di)

结果是

{0: 'A', 1: 'A', 2: 'A', 3: 'A', 4: 'A', 5: 'A', 6: 'A', 7: 'A', 8: 'A', 9: 'A', 10: 'B', 11: 'B', 12: 'B', 13: 'B', 14: 'B', 15: 'B', 16: 'B', 17: 'B', 18: 'B', 19: 'B', 20: 'C', 21: 'C', 22: 'C', 23: 'C', 24: 'C', 25: 'C', 26: 'C', 27: 'C', 28: 'C', 29: 'C'}

注意，xrange(N, M) 会生成从 N 开始，到 M-1 结束的整数（包括 N，但不包括 M）。所以如果你想把 10 和 20 包含在键里，那么范围应该是 xrange(10, 20) 和 xrange(20, 30)。

Answer 4

我会创建一个自定义字典，用xranges作为键：

class DictRange(dict):
    def __getitem__(self, val):
        for key in self.keys():
            if val in key:
                return super(DictRange,self).__getitem__(key)

缺点是你需要遍历所有的键才能找到你想要的元素。使用方法如下：

di = DictRange()
di[ xrange(0,10) ] = "A"
di[ xrange(11,20) ] = "B"
di[ xrange(21,30) ] = "C"

print di[24]
# C
print di[6]
# A

可以查看这个链接：http://repl.it/WAJ

更新

如果使用bisect，并且你在初始化时愿意花点时间来加快访问速度，你可以这样做：

import bisect
class DictRange(dict):

    def __setitem__(self, key, val):
        super(DictRange,self).__setitem__(key, val)
        self.ks = [key[0] for key in self.keys()]

    def __getitem__(self, val):
        return super(DictRange,self).__getitem__(self.keys()[bisect.bisect(self.ks, val) - 1])

这样获取元素的时间复杂度是O(logn)，其中n是键的数量，但设置的时间复杂度会变成O(n)。至于下一个解决方案，它依赖于范围是连续的。

其他解决方案

另一个解决方案，可能会更快，具体取决于你的范围大小，就是用范围的第一个元素作为键，然后用bisect来找到合适的键：

import bisect
ranges = [0, 11, 21, 31]
di = {}
di[0] = 'A'
di[11] = 'B'
di[21] = 'C'
di[31] = 'unknown' # special value to indicate the end of the range

print di[ranges[bisect.bisect(ranges, 24) - 1]]
# C
print di[ranges[bisect.bisect(ranges, 6) - 1]]
# A
print di[ranges[bisect.bisect(ranges, 31) - 1]]
# Unknown

这样会快很多。bisect的时间复杂度是O(logn)，其中n是范围的数量，其余的操作是O(1)。