将binarySearch与Comparator和regex一起使用 [英] Using binarySearch with Comparator and regex

问题描述

我正在尝试编写快速搜索，搜索列表< String>
而不是循环遍历列表并手动检查，我想这样做使用binarySearch，但我不知道该怎么做。

I am trying to write a quick search that searches a List<String> Instead of looping through the list and manually checking, I want to do this using binarySearch, but I am not sure how to do it.

旧方式：

for(String s : list) {
  if(s.startsWith("contact.")
     return true;
}

相反，我想要这样的事情：

Instead I would like something like this:

Collections.sort(list);
Collections.binarySearch(list, FindContactComparator());

有人可以帮我写这个比较器吗？

有没有更好的方法来做这个而不是使用binarySearch？

Can someone help me write this Comparator?
Is there any better way of doing this instead of using binarySearch?

推荐答案

这应该有效：

        Comparator<String> startsWithComparator = new Comparator<String>() {
            public int compare(String currentItem, String key) {
                if(currentItem.startsWith(key)) {
                    return 0;
                }
                return currentItem.compareTo(key);
            }
        };

int index = Collections.binarySearch(items, "contact.", startsWithComparator);

然而，排序和二进制搜索的效率低于单遍迭代。

However sorting and then binary searching is less efficient than the single pass iteration.

附录：

虽然以上答案对您有所帮助，但这是另一种方式（灵感来自Scala，Google收藏品）：

Though the above answer helps you, here is another way (inspired from Scala, Google Collections) :

List<String> items = Arrays.asList("one", "two", "three", "four", "five", "six");
int index = find(items, startsWithPredicate("th"));
System.out.println(index);


public static Predicate<String> startsWithPredicate(final String key) {
    return new Predicate<String>(){
        @Override
        public boolean apply(String item) {
            return item.startsWith(key); 
        }
    };
}

public static <T> int find(Collection<T> items, Predicate<T> predicate) {
    int index = 0;
    for(T item: items) {
        if(predicate.apply(item)) {
            return index;
        }
        index++;
    }
    return -1;
}

interface Predicate<T> {
    boolean apply(T item);
}

这里的东西是find（）方法与你的'匹配无关'逻辑;它只是找到一个满足谓词的元素。所以你可以传递一个不同的谓词实现，例如。它可以检查'endsWith'到find（）方法，它将返回以特定字符串结尾的找到的项目。此外，find（）方法适用于任何类型的集合;它需要的是一个谓词，它将集合元素类型的元素转换为布尔值。这个围绕简单逻辑的多行代码也表明Java缺乏对第一类函数的支持。

Here the thing is the find() method is not tied with your 'matching' logic; it just finds an element that satisfies the predicate. So you could pass on a different implementation of predicate, for ex. which can check 'endsWith' to find() method and it would return the found item which ends with a particular string. Further the find() method works for any type of collection; all it needs is a predicate which transforms an element of collection element type to a boolean. This multiple lines of code around a simple logic also show the Java's lack of support for first class functions.

这篇关于将binarySearch与Comparator和regex一起使用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！