3

我有大量的字符串。我希望能够找到以“Foo”开头的字符串或以“Bar”结尾的字符串。获得最快结果的最佳 Collection 类型是什么？（我正在使用 Java）

我知道 HashSet 对于完全匹配非常快，但对于部分匹配我认为不是？那么，我可以使用什么来代替循环列表呢？我应该查看 LinkedList 或类似类型吗？是否有针对此类查询优化的集合类型？

4

3 回答 3

3

The best collection type for this problem is SortedSet. You would need two of them in fact:

  1. Words in regular order.
  2. Words with their characters inverted.

Once these SortedSets have been created, you can use method subSet to find what you are looking for. For example:

  1. Words starting with "Foo":

     forwardSortedSet.subSet("Foo","Fop");

  2. Words ending with "Bar":

     backwardSortedSet.subSet("raB","raC");

The reason we are "adding" 1 to the last search character is to obtain the whole range. The "ending" word is excluded from the subSet, so there is no problem.

EDIT: Of the two concrete classes that implement SortedSet in the standard Java library, use TreeSet. The other (ConcurrentSkipListSet) is oriented to concurrent programs and thus not optimized for this situation.

于 2013-09-02T01:59:50.340 回答
3

已经有一段时间了，但我现在需要实现它并做了一些测试。

我已经有一个HashSet<String>源，因此所有其他数据结构的生成都包含在搜索时间中。使用了 100 个不同的源，每次都需要重新生成数据结构。我每次只需要匹配几个单个字符串。这些测试在 Android 上运行。

方法：

  1. 简单循环HashSet并调用endsWith()每个字符串

  2. 简单循环HashSet并在每个字符串上执行预编译 Pattern匹配（正则表达式）。

  3. 转换HashSet为整个字符串的单个String连接\n和单个匹配。

  4. 使用SortedTree反向生成Strings。 HashSet然后subset()按照@Mario Rossi 的解释进行匹配。

结果：

Duration for method 1: 173ms (data setup:0ms search:173ms)
Duration for method 2: 6909ms (data setup:0ms search:6909ms)
Duration for method 3: 3026ms (data setup:2377ms search:649ms)
Duration for method 4: 2111ms (data setup:2101ms search:10ms)

结论：

SortedSet/SortedTree搜索速度极快。比仅仅循环遍历所有Strings. 但是，创建结构需要很多时间。String正则表达式要慢得多，但是从数百个中生成一个大Strings则更多是 Android/Java 的瓶颈。

如果只需要进行一些匹配，那么您最好循环浏览您的收藏。如果您有更多匹配项，使用SortedTree!

于 2014-03-09T00:31:36.257 回答
2

如果单词列表是稳定的（添加或删除的单词不多），一个很好的第二种选择是创建 2 个列表：

  1. 一个以正常顺序的单词。
  2. 第二个将每个单词中的字符颠倒过来。

出于速度目的，将它们设为ArrayLists。Never LinkedLists 或其他在随机访问上表现极差的变体（二分搜索的核心；见下文）。

创建列表后，可以使用方法对它们进行排序Collections.sort（每个仅一次），然后使用Collections.binarySearch. 例如：

    Collections.sort(forwardList);
    Collections.sort(backwardList);

然后搜索以“Foo”开头的单词：

    int i= Collections.binarySearch(forwardList,"Foo") ;
    while( i < forwardList.size() && forwardList.get(i).startsWith("Foo") ) {
        // Process String forwardList.get(i)
        i++;
    }

以及以“酒吧”结尾的词：

    int i= Collections.binarySearch(backwardList,"raB") ;
    while( i < backwardList.size() &&  backwardList.get(i).startsWith("raB") ) {
        // Process String backwardList.get(i)
        i++;
    }
于 2013-09-02T02:12:20.693 回答