Использование бинарного поиска с компаратором и регулярным выражением

Question

Я пытаюсь написать быстрый поиск, который ищет List<String> Вместо того, чтобы перебирать список и проверять вручную, я хочу сделать это с помощью binarySearch, но я не уверен, как это сделать.

Старый путь:

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

Вместо этого я хотел бы что-то вроде этого:

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

Может кто-нибудь помочь мне написать этот компаратор?
Есть ли лучший способ сделать это вместо использования 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);

Однако сортировка и последующий двоичный поиск менее эффективны, чем однопроходная итерация.

Добавление:

Хотя приведенный выше ответ поможет вам, вот другой способ (вдохновленный 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 () не связан с вашей логикой «соответствия»;он просто находит элемент, который удовлетворяет предикату.Таким образом, вы можете передать другую реализацию предиката, например.который может проверять метод 'setsWith' для метода find (), и он будет возвращать найденный элемент, который заканчивается конкретной строкой.Далее метод find () работает для любого типа коллекции;все, что ему нужно - это предикат, который преобразует элемент типа элемента коллекции в логическое значение.Это множество строк кода вокруг простой логики также показывает отсутствие поддержки Java для функций первого класса.

Answer 2

Просто еще один компаратор (с регулярным выражением):

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:

"Доги", "Dogb", "собака", "ABCD", "Yxcv"

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 (log n) , где n - длина списка.)

Даже если список полностью отсортирован в большинстве случаев , алгоритм сортировки должен будет по крайней мере перебрать список, чтобы проверить это.

По сути, независимо от того, как вы реализуете алгоритм сортировки, алгоритм (даже в лучшем случае) должен по крайней мере смотреть на все элементы . Таким образом, линейный поиск «concat», вероятно, является лучшим вариантом здесь.

---

Более сложным решением было бы создать подкласс списка, который содержит строки, и поддерживать индекс первого вхождения "concat".

Учитывая, что строки неизменны, все, что вам нужно сделать, это переопределить add, remove и так далее, и соответственно обновить индекс.

Answer 5

Проблема в том, что бинарный поиск никогда не оглядывается назад. Я решил эту проблему путем нахождения первого соответствующего элемента с помощью бинарного поиска, а затем зациклился назад, чтобы найти первое вхождение этой подстроки, за которым последовал цикл, который собирает все соответствующие элементы.