尺寸高效字典（关联数组）实现

什么算法可用于尺寸高效A dictionary or associative array？例如，使用这个键/值集，如何避免在值中重复“Alice”？尺寸高效字典（关联数组）实现

{ 
    "Pride and Prejudice": "Alice", 
    "The Brothers Karamazov": "Pat", 
    "Wuthering Heights": "Alice" 
}

我检查Python's implementation on dictionary，但似乎实施的重点是速度（保持O（1））没有大小。

来源

2013-07-09 prosseek

保持第二字典映射值ID（例如哈希）值，在这一个使用值ID。 –

你的数据结构应该支持mutable * values *吗？ –

我想你可以存储sys.intern的结果，如果你只想把字符串作为值。 – bennofs

正如在评论中提到由bennofs，你可以使用intern()以确保相同的字符串存储只有一次：

class InternDict(dict): 

    def __setitem__(self, key, value): 
     if isinstance(value, str): 
      super(InternDict, self).__setitem__(key, intern(value)) 
     else: 
      super(InternDict, self).__setitem__(key, value)

下面是具有效果的例子：

>>> d = {} 
>>> d["a"] = "This string is presumably too long to be auto-interned." 
>>> d["b"] = "This string is presumably too long to be auto-interned." 
>>> d["a"] is d["b"] 
False 
>>> di = InternDict() 
>>> di["a"] = "This string is presumably too long to be auto-interned." 
>>> di["b"] = "This string is presumably too long to be auto-interned." 
>>> di["a"] is di["b"] 
True

来源

2013-07-09 16:59:51

如果你的字典可以放在内存中，那么可以使用一个简单的Hashtable。

尝试在散列表中插入每个键值。如果在插入之前存在密钥，那么你已经找到了重复。许多语言的执行次数为hashtable。

基本上有两种方法：array &树。

Array专注于高记忆成本的速度。 Hashtable实现的主要区别在于unicity的行为，有些实现强制unicity其他一些不行。
树将重点放在以O（log（n））cpu使用为代价的内存智能使用。 g ++地图依靠非常强大的功能red black tree。

如果大小是非常非常问题群，那么你应该寻找一个Huffman压缩和/或Lampel Ziv压缩，但它的成本多一点，为适应dictionnary。

如果您dictionnary不能在内存

适合你应该看看数据库。 红黑树数据库知道为BTree（差不多）。它针对低延迟硬盘驱动器案例进行了分支因素优化。

我已经把许多链接到维基百科，但如果你喜欢这个问题，我建议您：提高空间效率（除了共享的价值观，这（如bennofs中指出

Introduction to algorithms

来源

2013-07-09 16:55:40 Galigator

的一种方式注释）你可以使用sys.intern来高效地完成）是使用hopscotch hashing，这是一个开放的寻址方案（一种线性探测的变体）来解决冲突 - 封闭的寻址方案使用更多的空间，因为你需要分配一个链表对于每个存储桶而言，采用开放式寻址方案时，您只需在后备阵列中使用一个开放的相邻插槽而无需任何必要ng来分配任何链接列表。与其他开放寻址方案（如杜鹃散列或香草线性探测）不同，跳房散列在高负载因子（超过90％）下表现良好，可确保恒定时间查找。

来源

2013-07-09 16:55:51

尺寸高效字典（关联数组）实现

回答

相关问题