4

哪些算法可用于大小有效的字典或关联数组？例如，使用此键/值集，如何避免重复值中的“爱丽丝”？

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

我检查了Python 在 dictionary 上的实现，但似乎实现的重点是速度（保持 O(1)）而不是大小。

4

3 回答 3

1

正如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-09T16:59:51.567 回答
1

提高空间效率的一种方法（除了共享值，这（正如 bennofs 在评论中指出的那样）您可能可以通过使用 sys.intern 有效地完成）是使用 hopscotch hashing，这是一种开放式寻址方案（线性探测）用于解决冲突 - 封闭式寻址方案使用更多空间，因为您需要为每个存储桶分配一个链表，而使用开放式寻址方案，您只需使用后备数组中的一个开放相邻插槽，而无需分配任何链接列表。与其他开放寻址方案（例如布谷鸟散列或香草线性探测）不同，跳房子散列在高负载因子（超过 90%）下表现良好，并保证恒定时间查找。

于 2013-07-09T16:55:51.397 回答
0
  • 如果您的字典可以放入内存，那么可以使用一个简单的 Hashtable。

尝试在哈希表中插入每个键值。如果在插入之前密钥已经存在，那么您发现了重复项。在许多语言中都有许多哈希表的实现。

基本上有两种方式：数组和树。

  • 阵列以高内存成本关注速度。Hashtable 实现之间的主要区别在于唯一性的行为，一些实现强制唯一性，而另一些则没有。

  • 树专注于内存智能使用，代价是 O(log(n)) cpu 使用。g++ map 依赖于非常强大的全红黑树。

如果大小是非常非常有问题的，那么您应该搜索Huffman压缩和/或Lampel Ziv压缩，但它会花费更多，以适应字典。

  • 如果您的字典无法存储在内存中

你应该看看数据库。数据库的红黑树被称为BTree （几乎）。它对低延迟硬盘驱动器案例进行了分支因子优化。

我已经放了很多维基百科的链接，但如果你喜欢这个主题，我推荐你：

算法简介

于 2013-07-09T16:55:40.220 回答