在另一个大列表中搜索大量单词

40亿个字符串是很多要搜索的字符串。

您可能能够将整个数据结构放入内存散列中进行快速查找,但更可能希望将整个列表存储在更大(但速度较慢)的磁盘上,在这种情况下,排序列表将适合于相对高效的二进制搜索算法。

如果调用了二进制搜索或此类函数 find_string_in_articles() ,然后是伪代码:

foreach $protein_name ( @protein_names ) {
    if ( $article_id = find_string_in_articles( $protein_name ) ) {
        print( "$protein_name matches $article_id\n" );
    }
}

您可以对它们进行排序,然后执行“merge sort”,这实际上不会合并,但会发现重复/重叠。维基百科对此有很好的参考资料。

对大量数据进行排序可能需要比您所能访问的更多的内存。我不知道unix-sort(在windows/mac上也有)是否能处理这个问题,但是任何像样的SQL数据库都能做到。

另一种可能是在你的蛋白质名称上使用一个根目录树(那些以进位A、B到B等开头的名称)。然后循环4个单词并定位重叠部分(您可能必须实现多个深层基数分块才能一次丢弃更多的蛋白质)。

这本质上是一个关系联接。假设您还没有对文章单词进行排序,那么您的基本算法应该是:

for word in article_words:
    if (proteins.find(word)):
        found_match(word)

find()是一个困难的部分,为了获得最佳的性能,你必须进行实验,这类问题是缓存效果开始发挥作用的地方。我首先尝试使用基数排序,它非常简单,而且可能足够快,但是二进制搜索和哈希也是可选的。

听起来像是你应该用二叉树来表示的。

我会用两种方法中的一种来解决这个问题。

1. 将它插入到SQL数据库中,并提取所需的数据(速度较慢,但更容易)
2. 对列表进行排序,然后进行二进制搜索以查找所需内容(快速,但很棘手)