将binarySearch与Comparator和regex一起使用

我正在尝试编写一个快速搜索来搜索List而不是循环遍历列表并手动检查，我想使用binarySearch执行此操作，但我不知道如何执行此操作。

旧方式：

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

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

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

有人可以帮我写这个比较器吗？
有没有更好的方法来做这个而不是使用binarySearch？

Answer 1

这应该工作：

  Comparator startsWithComparator = new Comparator() { public int compare(String currentItem, String key) { if(currentItem.startsWith(key)) { return 0; } return currentItem.compareTo(key); } }; int index = Collections.binarySearch(items, "contact.", startsWithComparator); 

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

附录：

虽然上面的答案可以帮到你，但这是另一种方式（灵感来自Scala，Google Collections）：

 List items = Arrays.asList("one", "two", "three", "four", "five", "six"); int index = find(items, startsWithPredicate("th")); System.out.println(index); public static Predicate startsWithPredicate(final String key) { return new Predicate(){ @Override public boolean apply(String item) { return item.startsWith(key); } }; } public static  int find(Collection items, Predicate predicate) { int index = 0; for(T item: items) { if(predicate.apply(item)) { return index; } index++; } return -1; } interface Predicate { boolean apply(T item); } 

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

Answer 2

问题是二进制搜索永远不会回头。 我通过使用二进制搜索找到第一个匹配的元素，然后向后循环以找到该子字符串的第一个匹配项，然后是一个收集所有匹配元素的循环来解决这个问题。

Answer 3

我认为现在这样做的方式实际上是从性能角度来看的最佳方式。 排序本身可能比简单地遍历未排序列表更昂贵。 但是要确保你必须运行一些测试（虽然这并不像JIT编译那样容易听起来）。

您正在寻找的标准始终是“开始于”吗？ 因为在你的问题中，你在谈论正则表达式。

如果你想要实现这个，你应该至少使用相同的Comparator进行排序和搜索。 比较器本身可以非常简单。 只需编写一个将符合您标准的所有内容放在不符合标准的所有内容之前。 我的语法可能不完全正确，因为我有一段时间没有完成Java。

 public class MyComparator implements Comparator { 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; } } 

Answer 4

对列表进行排序本身比列表的线性扫描花费更多时间。 （基于比较的排序需要时间与n（log n）成比例，其中n是列表的长度。）

即使列表在大多数时间内完全排序 ，排序算法也必须至少遍历列表以检查这一点。

基本上，无论你如何实现排序算法，算法（即使在最好的情况下） 必须至少查看所有元素 。 因此，线性搜索“concat”可能是您最好的选择。

---

更复杂的解决方案是子类化包含字符串的列表，并维护“concat”的第一个出现的索引。

鉴于字符串是不可变的，您所要做的就是覆盖添加，删除等，并相应地更新索引。

Answer 5

只是另一个比较器（带正则表达式）：

 Comparator comparator = new Comparator() { 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): 

“yxcv”，“dogb”，“doga”，“abcd”，“a dog”

 Output(sorted) ArrayList: 

“doga”，“dogb”，“a dog”，“abcd”，“yxcv”