Python快速重复检测，我可以只存储散列而不存储值吗
Python快速重复检测，我可以只存储散列而不存储值吗
提问于 2018-07-23 06:41:31
我有一个创建图像“散列”的方法，它对重复帧检测很有用。(对这个问题来说无关紧要)
目前，我将视频的每一帧放在一个集合中，可以通过比较集合来查找包含交集的视频。(我有数十亿个哈希值)
因为我有自己的“散列”，所以我不需要集合的值，只需要检测重复项的能力。
这将使我的内存占用减少大约一半(因为我只有散列)。
我知道在内部，一个集合实际上是散列，值对。必须有一种方法来创建"SparseSet“或"hashonly”集。
就像这样
2 in sparset(1,2,3)
True但是在哪里呢
for s in sparset(1,2,3)将不返回任何内容，或者哈希不返回值。
回答 1
Stack Overflow用户
发布于 2018-07-23 06:58:33
这并不完全是集合的工作方式。散列值和值都是必需的，因为在发生散列冲突的情况下，必须检查这两个值是否相等。
如果您不关心冲突，您可以使用Bloom filter而不是set。它们的内存效率非常高，但会给出概率答案(要么肯定不在集合中，要么可能在集合中)。在标准库中没有布隆过滤器，但在PyPI上有几个实现。
如果你更关心优化空间而不是时间，你可以将散列保存在一个列表中，然后当你需要检查一个元素时，在适当的地方对它进行排序并进行二进制搜索。当列表大部分已经排序时，Python的Timsort非常有效，因此后续排序将相对较快。Python列表有一个sort()方法，您可以使用标准库bisect模块相当容易地实现二进制搜索。
您可以结合这两种技术，也就是说，如果Bloom filter指示元素不在集合中，则不必费心进行排序。当然，如果您自上次以来没有添加任何元素，请不要费心再次排序。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51469825
复制相关文章
相似问题
腾讯云开发者
