代码之家 › 专栏 › 技术社区 › Shervin Asgari

使用带比较器和regex的二进制搜索

comparator search java

Shervin Asgari · 技术社区 · 14 年前

List<String> 我不想在列表中循环并手动检查,而是想使用binarySearch来执行此操作,但我不确定如何执行此操作。

老办法:

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

相反,我想要这样的东西:

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

有人能帮我写这个比较器吗?
有没有比使用二进制搜索更好的方法呢?

5 回复 | 直到 14 年前

Marimuthu Madasamy 14 年前

这应该起作用:

        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);

然而,排序和二进制搜索比单次迭代效率低。

附录:

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项。此外,find()方法适用于任何类型的集合;它只需要一个将集合元素类型的元素转换为布尔值的谓词。围绕一个简单逻辑的多行代码也显示了Java缺乏对第一类函数的支持。

stacker 14 年前

问题是二进制搜索从不回头。

Ronald Wildenberg 14 年前

我认为从性能的角度来看,你现在这样做实际上是最好的方式。排序本身可能比简单地遍历未排序的列表更昂贵。但是要确定的是,您必须运行一些测试(尽管由于JIT编译,这听起来不像那么容易)。

你要找的标准总是从“开始”开始吗?因为在你的问题中你说的是正则表达式。

Comparator 分类和搜索。比较器本身可以非常简单。只要写一篇文章,把符合你标准的东西放在不符合你标准的东西前面。我的语法可能不完全正确,因为我已经有一段时间没有使用Java了。

public class MyComparator<string> implements Comparator<string> {
    private string prefix;
    public MyComparator(string prefix) {
        this.prefix = prefix;
    }
    public int compare(string s0, string s1) {
        if (s0.startsWith(prefix) && s1.startsWith(prefix)) {
            return 0;
        }
        else if (s0.startsWith(prefix)) {
            return -1;
        }
        else if (s1.startsWith(prefix)) {
            return 1;
        }
        return 0;
    }
    public bool equals(object comp) {
        return true;
    }
}

aioobe 14 年前

排序列表本身要比线性扫描列表花费更多的时间(基于比较的排序所需时间与哪里 n

即使列表在大多数情况下是完全排序的 ,排序算法必须至少遍历列表才能检查这一点。

基本上,无论您如何实现排序算法,算法(即使在最佳情况下) . 因此,线性搜索“concat”可能是最好的选择。

更详细的解决方案是对包含字符串的列表进行子类化,并维护“concat”第一次出现的索引。

假设字符串是不可变的,您所要做的就是重写add、remove等,并相应地更新索引。

rekinyz 12 年前

Comparator<String> comparator = new Comparator<String>() {

    private final Pattern containsPattern = Pattern.compile(searchTerm,Pattern.CASE_INSENSITIVE);

    public int compare(String o1, String o2) {

        Matcher contains1 = containsPattern.matcher(o1);
        Matcher contains2 = containsPattern.matcher(o2);
        boolean find1 = contains1.find();
        boolean find2 = contains2.find();

        if(find1 && find2){
            int compareContains = contains1.end() - contains2.end();
            if (compareContains == 0) {
                return o1.compareTo(o2);
            } else {
                return compareContains;
            }
        }else if(find1){
            return -1;
        }else if(find2){
            return 1;
        }else{
            return o1.compareTo(o2);
        } 
    } 
};

Input ArrayList (search term: dog):
“多加”, “一只狗”
Output(sorted) ArrayList:
“多加”, “狗狗”, “一只狗”,