时间戳

首页 > 解决方案 > Python：搜索长字符串是否在字符串列表中的最快方法

python - Python：搜索长字符串是否在字符串列表中的最快方法

问题描述

我输入了大约 2-5 百万个字符串，每个字符串大约 400 个字符，来自一个存储的文本文件。在将它们添加到我检查的列表之前，我需要检查重复项（不必是列表，可以是任何其他数据类型，列表在技术上是一个集合，因为所有项目都是唯一的）。

我可以预计最多 0.01% 的数据是非唯一的，我需要将它们过滤掉。

我想知道是否有更快的方法来检查该项目是否存在于列表中，而不是：

a=[]
for item in data:
    if item not in a:
        a.add(item)

我不想失去订单。

散列会更快（我不需要加密）吗？但随后我必须维护一个哈希表，以便首先检查所有值。我有什么办法吗？

我在 python 2 上，最多可以升级到 python 3.5。

标签： pythonsearch

解决方案

很难回答这个问题，因为它一直在变化；-) 我正在回答的版本询问是否有比以下更快的方法：

a=[]
for item in data:
    if item not in a:
        a.add(item)

这将是非常缓慢的，需要时间二次方len(data)。在任何版本的 Python 中，以下将采用预期案例时间线性len(data)：

seen = set()
for item in data:
    if item not in seen:
        seen.add(item)
        emit(item)

你喜欢的东西在哪里emit()（附加到列表，写入文件，等等）。

在评论中，我已经注意到使用有序字典实现相同目的的方法（无论是通过 Python 3.7 中的语言保证，还是通过包中的OrderedDict类型进行排序collections）。不过，上面的代码是最节省内存的。

推荐阅读