Comparison과 regex와 함께 binarySearch 사용하기

Question

List<String> 목록을 반복하면서 수동으로 확인하는 대신 binarySearch를 사용하여이 작업을 수행하려하지만 어떻게해야할지 모르겠다.

오래된 방법 :

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

누군가가 나에게이 비교기를 작성하는 데 도움 수

:

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

대신 나는 이런 식으로 뭔가를 원하십니까?
binarySearch 대신이 작업을 수행하는 더 좋은 방법이 있습니까?

Answer 1

이 작동합니다 :

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

는 것은 찾기입니다() 메소드는 아니다 당신의 '일치하는'논리로 묶여; 단지 술어를 만족하는 요소를 찾습니다. 예를 들어 다른 술어 구현을 전달할 수 있습니다. 'endsWith'를 find() 메소드로 검사 할 수 있으며 특정 문자열로 끝나는 찾은 항목을 반환합니다. 또한 find() 메소드는 모든 유형의 콜렉션에서 작동합니다. 필요한 것은 콜렉션 요소 유형의 요소를 부울로 변환하는 술어입니다. 간단한 로직을 둘러싼이 여러 줄의 코드는 자바가 일류 함수를 지원하지 못함을 보여줍니다. (정규식)

Answer 2

문제는 이진 검색이 되돌아 가지 않는다는 것입니다. 이진 검색을 사용하여 첫 번째 일치하는 요소를 찾은 다음이 하위 문자열의 첫 번째 항목을 찾으려면 뒤로 루프를 수행하고 일치하는 모든 요소를 ​​수집하는 루프를 찾아서이 문제를 해결했습니다.

Answer 3

나는 지금 당신이 이것을하는 방식이 실제로 성능 관점에서 가장 좋은 방법이라고 생각합니다. 정렬 자체는 단순히 정렬되지 않은 목록을 반복하는 것보다 비용이 많이 듭니다. 하지만 몇 가지 테스트를 실행해야합니다 (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; 
    } 
} 

Answer 4

목록 자체를 정렬하면 목록의 선형 스캔보다 시간이 오래 걸립니다.

리스트 완전히 배 대부분 정렬된다하더라도, 정렬 알고리즘은 것 (비교 기반 정렬() N 로그 N리스트의 길이. N에 비례하는 시간 소요) 적어도 이것을 점검하기 위해 목록을 반복합니다.

기본적으로 정렬 알고리즘을 구현하는 방법에 상관없이 알고리즘 (심지어 최상의 경우에도) 은 최소한 모든 요소을 살펴야합니다. 따라서 "concat"에 대한 선형 검색이 아마 여기에서 가장 좋은 옵션 일 것입니다.

---

더 정교한 솔루션은 문자열을 포함하는 목록을 서브 클래스, 및 "CONCAT"의 첫 번째 occurnece의 인덱스를 유지하는 것입니다.

문자열을 변경할 수 없다면 추가, 제거 등을 재정의하고 이에 따라 색인을 업데이트해야합니다.

Answer 5

그냥 다른 비교 :

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

"yxcv" "dogb" "도가" "ABCD", "개가"

Output(sorted) ArrayList: 

"doga", "dogb", "개", "abcd",