我建议如下:将所有值存储在数据库中,并保留一个以字符串哈希为键的内存字典。如果发生冲突,请从数据库中获取值,否则(大多数情况下)使用字典。实际上,它将是一个巨大的缓存。
Python中的字典存在一个问题,即它们占用了大量空间:即使int-int字典在32位系统上每个键值对也使用 。同时,每对intarray.array('i')
仅使用 ,并且通过少量记账就可以实现基于数组的 int→int 字典的合理快速运行。
一旦有了内存效率高的int-int字典实现,就将您的 字符串→(对象,int,int) 字典分成三个字典,并使用哈希代替完整的字符串。您将获得一个int→对象 和两个 int→int 字典。模仿 int→对象 字典,如下所示:保留对象列表并将对象的索引存储为 int→int 字典的值。
我的确意识到要获得基于数组的字典需要涉及大量的编码。我遇到了与您类似的问题,并且实现了一个相当快,内存效率很高的通用hash-int字典。这是我的代码(BSD许可证)。它是基于数组的(每对8个字节),它负责密钥散列和冲突检查,它在写入过程中使数组(实际上是几个较小的数组)保持有序,并在读取时进行二进制搜索。您的代码简化为:
dictionary = HashIntDict(checking = HashIntDict.CHK_SHOUTING)
# ...
database.store(k, v)
try:
dictionary[k] = v
except CollisionError:
pass
# ...
try:
v = dictionary[k]
except CollisionError:
v = database.fetch(k)
该checking
参数指定发生冲突时发生的情况:在读取和写入时CHK_SHOUTING
提高,CollisionError
在读取时CHK_DELETING
返回None
,并且在写入时保持沉默,CHK_IGNORING
不进行冲突检查。
接下来是对我的实现的简要说明,欢迎使用优化提示!顶层数据结构是数组的常规字典。每个数组最多包含2^16 = 65536
整数对(的平方根2^32
)。键k
和对应的值v
都存储在k/65536
-th数组中。数组按需初始化,并按键保持顺序。每次读取和写入都会执行二进制搜索。冲突检查是一个选项。如果启用,尝试覆盖现有键的操作将从字典中删除键和关联的值,将该键添加到一组冲突键中,并且(再次可选)引发异常。