首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >Python快速重复检测,我可以只存储散列而不存储值吗

Python快速重复检测,我可以只存储散列而不存储值吗
EN

Stack Overflow用户
提问于 2018-07-23 06:41:31
回答 1查看 344关注 0票数 1

我有一个创建图像“散列”的方法,它对重复帧检测很有用。(对这个问题来说无关紧要)

目前,我将视频的每一帧放在一个集合中,可以通过比较集合来查找包含交集的视频。(我有数十亿个哈希值)

因为我有自己的“散列”,所以我不需要集合的值,只需要检测重复项的能力。

这将使我的内存占用减少大约一半(因为我只有散列)。

我知道在内部,一个集合实际上是散列,值对。必须有一种方法来创建"SparseSet“或"hashonly”集。

就像这样

代码语言:javascript
复制
2 in sparset(1,2,3) 

True

但是在哪里呢

代码语言:javascript
复制
for s in sparset(1,2,3)

将不返回任何内容,或者哈希不返回值。

EN

回答 1

Stack Overflow用户

发布于 2018-07-23 06:58:33

这并不完全是集合的工作方式。散列值和值都是必需的,因为在发生散列冲突的情况下,必须检查这两个值是否相等。

如果您不关心冲突,您可以使用Bloom filter而不是set。它们的内存效率非常高,但会给出概率答案(要么肯定不在集合中,要么可能在集合中)。在标准库中没有布隆过滤器,但在PyPI上有几个实现。

如果你更关心优化空间而不是时间,你可以将散列保存在一个列表中,然后当你需要检查一个元素时,在适当的地方对它进行排序并进行二进制搜索。当列表大部分已经排序时,Python的Timsort非常有效,因此后续排序将相对较快。Python列表有一个sort()方法,您可以使用标准库bisect模块相当容易地实现二进制搜索。

您可以结合这两种技术,也就是说,如果Bloom filter指示元素不在集合中,则不必费心进行排序。当然,如果您自上次以来没有添加任何元素,请不要费心再次排序。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/51469825

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档