最佳算法和数据结构来比较两个大列表

Question

3

每天我都会收到一个包含30-40k行的列表，每一行都包含有意义或无意义的名称，例如fastcar，ultrafastcar，blablablacar等。

我还有一个由任何语言中的所有单词组成的大列表（约50k行）。

我想将第一个列表与第二个列表进行比较，以过滤包含（或以...开头/以...结尾）第二个列表中的单词的内容。我的意思是，如果单词是“ultrafastcar”，那么它不会被过滤，但“blablacar”将被过滤掉。

我已经准备了一些Java代码，但比较列表需要太长时间。我已经使用了ArrayLists并将它们与contains()、startsWith()方法进行了比较。ArrayLists是正确的选择吗？除了这些方法之外，我还可以使用什么算法来进行比较？

- lutfucan

50k并不算大，你应该能够很快完成。查看ArrayList和parallelStream()以轻松添加一些并发性（它在底层使用fork join）。 - markspace

你的单词列表是否已排序？如果是，你是否使用了二分查找？哈希映射可能比列表更快。 - Alan Birtles

2

第二个列表的 HashSet - Abdul Ahad

这个问题，你不需要对第二个集合进行排序，使用哈希表可以加快查找速度。难怪它“太慢了”。这一点应该很明显。 - markspace

1

哈希集合在这里真的有帮助吗？考虑到 OP 正在寻找子字符串，Aho-Corasick 算法听起来更加有用。Aho-Corasick - Andy Turner

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Keanu Dirkse · Answer 1

你可以尝试使用三叉搜索树来实现第二个列表，然后检查第一个列表中的单词是否存在于这棵树中。