用于搜索字符串三元组的最有效的Java数据结构

Question

假设我有一个大的字符串三元组列表(大约10,000个条目)，如下所示:

car    noun    yes
dog    noun    no
effect noun    yes
effect verb    no

假设我看到一个双精度字符串(例如，(effect, verb))，我需要快速查看列表中是否出现了对，如果出现了，它的值是yes还是no。(在本例中，双精度体确实出现，值为"no")

在Java中存储列表的最佳数据结构和执行搜索的最有效方法是什么?我正在运行成千上万个这样的搜索，所以速度是至关重要的。

谢谢!

Answer 1

您可以考虑使用HashMap<YourDouble, String>。搜索次数为0(1)。

你可以创建一个对象YourDouble来保存前两个值，或者将一个值附加到另一个值上——如果值仍然是唯一的——并使用HashMap<String, String>

Answer 2

我会为您想要的每种类型的搜索创建一个HashMultimap，例如:"all three"， "each pair"one_answers"each single field"。当您构建列表时，填充所有不同的映射，然后您可以从适合您的查询的映射中获取。

(缺点是，您至少需要为每个字段使用一个类型，例如，对于"单字段"映射只使用String，但是对于双字段映射使用Pair，对于三字段映射使用Triple。)

Answer 3

可以使用HashMap，其中键是用于查找的前两个字符串的连接，值是布尔值，表示yes和no字符串。

另一种情况是，第二列中的单词似乎更少，因为它们表示类别。你可以有一个HashMap<String, HashMap<String, Boolean>>，你首先索引例如。"名词"，"动词"等等，然后按e.g.进行索引。"car" "dog" "effect"来得到你的布尔值。这可能更节省空间。

Answer 4

10k对我来说似乎没有那么大。你试过DB吗?

查找此类信息的地方是语义网。许多项目都是基于这种类型的Triple Stores。在Triple Store页面的底部有一个实现列表。

就java而言，你的算法几乎肯定会依赖于语言，如果你找到一个用C实现的好算法，它的java端口也会很快。

还有，你的数据集是什么样的?是否有很多匹配，主语和动词经常是相同的?你预计会有多少场比赛?MapReduce可以很好地在10k中找到一个匹配项，但如果查询返回10k的8k，查询就不能很好地进行分区了。

也有专门针对这个问题的查询语言:SPARQL。bigdata博客有一些很好的见解，尽管10k看起来也没有那么大。