加快列表中的查找项目（通过Python）

我有一个非常大的列表，我必须运行这个列表的很多查找。更具体地说，我在一个大型（> 11GB）文本文件上进行处理，但有一些项目出现了多次，而且我只在它们出现时才处理它们。如果模式显示出来，我将它处理并放到列表中。如果该项目再次出现，我检查它在列表中，如果是的话，我只是通过处理，像这样：加快列表中的查找项目（通过Python）

[...] 
if boundary.match(line): 
    if closedreg.match(logentry): 
     closedthreads.append(threadid) 
    elif threadid in closedthreads: 
     pass 
    else: 
[...]

代码本身是远远没有达到最佳。我的主要问题是'closedthreads'列表包含几百万项，整个操作开始变得越来越慢。我认为它可以帮助排序列表（或使用'排序列表'对象）每个append（）后，但我不知道这一点。什么是最优雅的溶剂？

来源

2014-01-15 banyek

到目前为止的答案表明，了解更多关于'threadid'的信息会有所帮助：它是哪种类型，如果值受到某种限制...最后，您需要一些快速查找，因此哈希，以及在某些情况下，制作你自己的散列函数可能是一条可行的路线;领域知识帮助那里。 – mknecht

threadid是一个简单的整数。（我正在处理大量的mysql_slow.log文件，以便在具有percona-playback的服务器上重新运行它们。为了加速重播过程，我必须关闭最后出现在日志中的线程 – banyek

然后接受的答案很可能是如果你仍然有速度问题，那么应该仔细看看这些数字，或者更确切地说，用一些不同的方式来解决实际问题:) – mknecht

使用一个集合而不是一个列表会给你O（1）查找时间，尽管可能有其他方法来优化它，这对你的特定数据更好。

closedthreads = set() 
# ... 

if boundary.match(line): 
    if closedreg.match(logentry): 
     closedthreads.add(threadid) 
    elif threadid in closedthreads: 
     pass 
    else:

来源

2014-01-15 14:31:50 geoffspear

感谢你的例子。（我接受了另一个答案，因为它更快。） – banyek

:(对不起，下一次然后 – banyek

您可以简单地使用一个集合或一个哈希表，标记是否已经出现给定的ID。它应该解决您的问题与O（1）时间复杂性添加和查找项目。

来源

2014-01-15 14:27:48

您是否需要保留排序？如果不是 - 使用一组。

如果你这样做 - 使用OrderedDict。 OrderedDict允许您存储与之相关的值（例如，处理结果）

但是......您是否需要保留原始值？如果你真的这么做了（或者购买大量内存！），或者不是存储实际文本，而是存储SHA-1摘要，或者类似的东西，你可以看看'dbm'模块。如果你想要做的只是确保你不会运行相同的元素两次，那可能会奏效。

来源

2014-01-15 14:33:49

我猜测一个线程ID可能比它的SHA1哈希短（尽管OP没有提供足够的信息），并且散列操作本身的计算过于昂贵 – geoffspear

是的，这是真实的 - 出于某种原因，我认为原始项目是字符串，在这种情况下，它可能并不那么慢，甚至可能是更快（因为检查一个项目是否在集合中，你必须同时调用'__hash__'和'__eq__'，并且字符串相等不一定对长字符串的影响很小）.... –

加快列表中的查找项目（通过Python）

回答

相关问题