Verwendung von binarySearch mit Comparator und regex

Question

Ich versuche, eine schnelle Suche zu schreiben, die eine List<String> Anstatt die Liste in einer Schleife zu durchlaufen und manuell zu überprüfen, möchte ich dies mit binarySearch tun, aber ich bin mir nicht sicher, wie man es macht.

Alte Methode:

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

Stattdessen hätte ich gerne etwas in dieser Art:

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

Kann mir jemand helfen, diesen Comparator zu schreiben?
Gibt es eine bessere Möglichkeit, dies zu tun, anstatt binarySearch zu verwenden?

Answer 1

Das sollte funktionieren:

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

Das Sortieren und anschließende binäre Suchen ist jedoch weniger effizient als die Iteration in einem Durchgang.

Nachtrag:

Auch wenn die obige Antwort Ihnen hilft, hier ist ein anderer Weg (inspiriert von 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);
}

Hier ist die find()-Methode nicht mit Ihrer "passenden" Logik verbunden; sie findet einfach ein Element, das das Prädikat erfüllt. Sie können also eine andere Implementierung des Prädikats an die find()-Methode übergeben, die z.B. 'endsWith' prüfen kann und das gefundene Element zurückgibt, das mit einer bestimmten Zeichenkette endet. Außerdem funktioniert die find()-Methode für jede Art von Sammlung; alles, was sie braucht, ist ein Prädikat, das ein Element vom Typ Sammlungselement in einen Boolean umwandelt. Diese vielen Codezeilen um eine einfache Logik herum zeigen auch die mangelnde Unterstützung von Java für Funktionen erster Klasse.

Answer 2

Das Problem ist, dass die binäre Suche nie zurückblickt. Ich habe das Problem gelöst, indem ich das erste übereinstimmende Element mit der binären Suche gefunden habe, dann eine Rückwärtsschleife, um das erste Vorkommen dieses Teilstrings zu finden, gefolgt von einer Schleife, die alle übereinstimmenden Elemente sammelt.

Answer 3

Ich denke, dass die Art und Weise, wie Sie dies jetzt tun, vom Standpunkt der Leistung aus gesehen die beste ist. Das Sortieren selbst ist wahrscheinlich teurer als die einfache Iteration durch die unsortierte Liste. Aber um sicher zu sein, müssten Sie einige Tests durchführen (obwohl das aufgrund der JIT-Kompilierung nicht so einfach ist, wie es klingen mag).

Ist das Kriterium, das Sie suchen, immer "beginnt mit"? Denn in Ihrer Frage sprechen Sie von einer Regex.

Wenn Sie dies implementieren wollen, sollten Sie zumindest die gleiche Comparator für die Sortierung wie für die Suche. Der Komparator selbst kann sehr einfach sein. Schreiben Sie einfach einen, der alles, was mit Ihren Kriterien übereinstimmt, vor alles stellt, was nicht übereinstimmt. Meine Syntax ist vielleicht nicht ganz korrekt, da ich schon eine Weile nicht mehr mit Java gearbeitet habe.

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

Das Sortieren der Liste selbst nimmt mehr Zeit in Anspruch als eine lineare Suche in der Liste. (Vergleichsbasiertes Sortieren benötigt Zeit proportional zu n(log n) wobei n ist die Länge der Liste).

Auch wenn die Liste in den meisten Fällen vollständig sortiert ist muss der Sortieralgorithmus die Liste zumindest iterieren, um dies zu überprüfen.

Im Grunde ist es egal, wie man einen Sortieralgorithmus implementiert, der Algorithmus (selbst im besten Fall) muss zumindest alle Elemente berücksichtigen . Daher ist eine lineare Suche nach "concat" hier wahrscheinlich die beste Option.

---

Eine kompliziertere Lösung wäre, die Liste, die die Zeichenketten enthält, zu untergliedern und den Index des ersten Vorkommens von "concat" beizubehalten.

Da Zeichenketten unveränderlich sind, müssen Sie nur add, remove usw. außer Kraft setzen und den Index entsprechend aktualisieren.

Answer 5

Nur ein weiterer Komparator (mit Regex):

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", "doga", "abcd", "ein Hund"

Output(sorted) ArrayList:

"doga", "dogb", "ein Hund", "abcd", "yxcv"