Binäres Einfügen

[Pfaeff]

Hallo,

Ich bin momentan echt am verzweifeln 😉 Ich habe eine Klasse, die von LinkedList erbt und Elemente beinhaltet, die einen String (name) in ihren Attributen haben. Jetzt würde ich diese Liste gerne sortiert halten, sprich: ich mache beim Einfügen eine Binärsuche und merke mir den Wert, wo mein Element hinkommen soll. Zurückgeben möchte ich, ob das Element gefunden wurde. Ich war jetzt schon so weit, dass ich (nur zu Testzwecken) von einer Binärsuche auf eine lineare Suche umgestiegen bin, jedoch kommt bei mir immer das selbe Ergebnis (ganz glücklich bin ich mit der Implementierung ohnehin nicht):

import java.util.LinkedList;

public class GroupList extends LinkedList<ObjGroup> {
    private int index = 0;
    public boolean find(String str) {
        for (int i=0; i<this.size(); i++) {
            index = i;
            int cmp = str.compareTo(this.get(i).name);
            if (cmp == 0)
                return true; 
            if (cmp < 0) 
                return false;                
        }    
        return false;        
    }
    // Einfügen nachdem sortiert wurde
    public boolean add(ObjGroup group) {
        index = Math.max(Math.min(index, this.size()), 0);
        super.add(index, group);
        return true;
    }    
    // Gesuchtes Element zurückgeben
    public ObjGroup getGroup() {
        if ((index >= 0) && (index < this.size()))
            return this.get(index);
        return null;
    }
}

Meine Beispieleingabe folge (mit jeweiligem Aufruf von find()) sieht so aus:
a d c b f
Die Ausgabe lautet dann: b c d f a statt a b c d f. Ich denke mir mal, dass die Art wie ich mir meinen index merke nicht ganz richtig ist.

EDIT: Ich glaube mit Comparator und Collections lässt sich da vielleicht was machen, aber ich bekomme es grad nicht hin 😉

Vielen Dank,
mfg

 

[SlaterB]

niemals sollte eine Methode, die nicht vom Namen her direkt dafür zuständig ist, einen Wert setzen und eine andere ihn dann benutzen,
add() sollte auch funktionieren ohne dass man vorher find() aufruft,
was passiert gar wenn man find() mit anderem Objekt aufruft? Chaos

-------
find() sieht bisher auch noch nicht aus,
aber das wußtest du wohl nach der Ausgabe,
baue doch logging ein, zu Beginn der Methode gibst du den Suchtwert + den Inhalt der Liste aus,
schaust dir die Vergleiche in der Schleife im Detail an und den Index am Ende, und prüfst mit deinem Kopf, ob das so korrekt ist oder nicht,
wenn du den Fehler erkannt hast und dich immer noch fragst, wie man das korrigieren kann, dann können wir ja nochmal drüber reden

ständig get(i) aufzurufen ist ziemlich schlecht bei LinkedList, da wird immer von Element 0 an neu alle Elemente durchlaufen,
lieber einen Iterator verwenden,
aber du wolltest wohl eh ganz was anderes,

Binärsuche im Sinne von Intervalhalbierung (erst mit Element an Position size/2 vergleichen usw.) könntest du direkt in deine Methode einbauen

Comparator oder Comparable wäre bei eigener Implementation nicht so viel anders, ob nun string.compare(string) oder ObjGroup.compare(ObjGroup),
für APIs wäre das natürlich interessant, Collections.sort() scheint übertrieben, jedes mal komplett neu sortieren?
dann schon lieber eine Struktur, die selber beim Einfügen sortiert, SortedList/ SortedLinkedList gibts aber nicht..

 

[Pfaeff]

Ja genau das mit der Variable war das was ich meinte das mir überhaupt nicht gefällt 😉
Ich muss halt irgendwie rausfinden können, ob etwas gefunden wurde, damit ich unterscheiden kann, ob ich beim Index einfügen muss, oder nicht.
Ich bin den Algorithmus (auch den mit der Intervalhalbierung) schon mehrfach schrittweise durchgegangen und bin auch auf die selben Ergebnisse gekommen wie mein Algorithmus. Allerdings bin ich noch nicht dahinter gekommen, warum es nicht funktioniert.
Angenommen es ist ein Element drin, so wird der Suchindex nicht größer als 0 werden. Wenn ich aber ein Element einfügen möchte, das größer ist, so brauche ich eine 1.

Das mit dem Iterator ist ein guter Tipp, danke 😉

 

[SlaterB]

genau, wenn der Index gleich der Size der Liste-1 ist musst du z.B. am Ende nochmal mit dem letzten Element vergleichen und den Index gegebenenfalls um 1 erhöhen,
nur in der Schleife kann der höchste Index nicht erreicht werden

 

[Civilazi]

dann schon lieber eine Struktur, die selber beim Einfügen sortiert, SortedList/ SortedLinkedList gibts aber nicht..

Aber eine PriorityQueue.

 

[Pfaeff]

so kommt es immerhin schon fast hin:

    public int find(String str) {
        int start = 0;
        int end = this.size()-1;
        int index = 0;
        String tmp = new String();
        while ((end-start) >= 0) {
            index = start + (end-start)/2;
            tmp = this.get(index).name; 
            if (tmp.compareTo(str) < 0)
                start = index+1;
            if (tmp.compareTo(str) > 0)
                end = index-1;     
            if (tmp.equals(str))
                return index;                
        }
        if (index == this.size()-1)
            index++;
        return index;
    }

Aber scheinbar gibt es noch Fälle (vielleicht wenn das gesuchte Element kleiner ist als das Letzte), wo es nicht geht. So klappt es auch nicht:

// Das letzte Element überprüfen
        if (index == this.size()-1) {
            int c = this.get(this.size()-1).name.compareTo(str);
            if (c < 0) {
                index++;
            } else {
                index--;
            }
        }

Und wie gebe ich zurück, ob das Element nun gefunden wurde? Wäre schlecht, wenn ich zweimal hintereinander suchen müsste.

 

[SlaterB]

niemals new String() schreiben,
String tmp = "";
oder
String tmp = null;
geht genauso

und immer noch mein Rat:

baue doch Logging ein, zu Beginn der Methode gibst du den Suchwert + den Inhalt der Liste aus,
schaust dir die Vergleiche in der Schleife im Detail an und den Index am Ende, und prüfst mit deinem Kopf, ob das so korrekt ist oder nicht,

ich könnte das auch und dann korrigieren,
aber mir scheint, du solltest das selbst versuchen wenn du schon derart gewagtes programmierst

 

[Pfaeff]

danke, so scheint es zu gehen:

    public int find(String str) {
        if (this.size() == 0)
            return 0;
        int start = 0;
        int end = this.size()-1;
        int index = 0;
        String tmp = "";
        int c = 0;
        while ((end-start) >= 0) {
            index = start + (end-start)/2;
            tmp = this.get(index).name; 
            c = tmp.compareTo(str);
            if (c < 0)
                start = index + 1;
            if (c > 0)
                end = index - 1;     
            if (c == 0)
                return index;                
        }
        tmp = this.get(index).name;
        c = tmp.compareTo(str);
        if (c < 0)
            index++;  
        return index;
    }

Wie gesagt ist jetzt noch die Frage, wie ich zusätzlich ausgeben kann, ob das Element gefunden wurde. Die einzige Möglichkeit die mir einfiele, wäre eine neue Klasse zu definieren, die einen int und einen boolean beinhaltet.

mfg

 

[SlaterB]

stimmt, mit einem Rückgabewert ist man da begrenzt,

wenn man aber erstmal den Index hat, kann man auch relativ zügig in einem zweiten Schritt das Element zum Index laden und dessen Name anschauen

 

[ice-breaker]

Öhm, also eine binäre Suche auf eine LinkedList anzuwenden ist ineffizienter als linear zu Suchen 😉

 

[SlaterB]

kommt auf den Aufwand eines Vergleichs an 😉

vielleicht ist auch die Verlinkung gerade in Intervall-Halbierungs-Schritten 😉

 

[Pfaeff]

Lineare Suche hat doch O(n) und die binäre Suche O(log n), nur dass ich bei der binären zusätzlich beim Einfügen suchen muss (bzw nichtmal das, weil ich ja die Werte der Suche direkt fürs Einfügen benutzen kann).
Sollte sie tatsächlich langsamer sein (durch die Listeneigenschaft), kann ich mir die Sortiererei auch sparen 😉

 

[Landei]

Falls du keine Duplikate hast: Nimm doch einfach ein TreeSet oder eine TreeMap

 

[Civilazi]

Lineare Suche hat doch O(n) und die binäre Suche O(log n),

Das gilt aber nur, wenn du Random Access hast, z.B. bei Arrays. Wenn du bei der LinkedList aber mit get(i) auf ein Element auf nem Index zugreifst, läuft er von vorne bis i komplett durch, wie soll er auch anders, das ist halt "nur" ne doppelt verkettete Liste. Das machst du im Zweifel mehrmals, vor allem, wenn das gesuchte in der rechten Hälfte ist, machst du da schon mehr Vergleiche als wenn du einfach einmal durchläufst. Befindet sich das gesuchte in der linken Hälfte, hast du aber auch kein O(logn). Eine LinkedList ist für sowas einfach nicht gedacht. Wenn du eine Datenstruktur brauchst, die in O(logn) Sachen sortiert bereitstellt mit entsprechenden add, poll etc.-Methoden, nimm eine PriorityQueue. Wenn du es selbst machen willst, dann eine ArrayList.

 

[ice-breaker]

Genau das meinte ich :applaus:

 

[Pfaeff]

Es würde also reichen LinkedList durch ArrayList zu substituieren um den gewünschten Geschwindigkeitsboost zu erreichen? Was ist genau der Unterschied bei einer ArrayList? Bzw. was ist der Vorteil der LinkedList?

EDIT: mein Programm ist nun um das 100 fache schneller, danke 😉

mfg

 

[Landei]

Array: Feste Länge, muss bei der Erzeugung angegeben werden.
ArrayList: Variable Länge, wächst mit den Daten

 

[ice-breaker]

Was ist genau der Unterschied bei einer ArrayList? Bzw. was ist der Vorteil der LinkedList?

:arrow: Javainsel: 12.3 Listen 😉

 

[Civilazi]

Es würde also reichen LinkedList durch ArrayList zu substituieren um den gewünschten Geschwindigkeitsboost zu erreichen? Was ist genau der Unterschied bei einer ArrayList? Bzw. was ist der Vorteil der LinkedList?

EDIT: mein Programm ist nun um das 100 fache schneller, danke 😉

mfg

Da gibts es hier sogar ein How To: Welche Collection wann verwenden? oder so in den FAQs.
Mal ganz kurz: Arrays sind toll (Random Access), habern aber eine feste Größe, die man bei der Erstellung angeben muss. Eine LinkedList ist toll (dynamische Größe, jeder Eintrag kennt seinen Vordermann und den nächsten Eintrag, die Liste selber den Anfang und das Ende, dadurch kann man die ganze Liste durchlaufen), die kann man nehmen, wenn man noch nicht weiß, wieviel Sachen man speichern will, aber dann immer alles durchlaufen und irgendwas damit tun will. Eine ArrayList ist auch toll (verwaltet im Hintergrund ein Array, das wenn es zu klein wird, in ein neues größeres kopiert wird <-- kostet Zeit), sollte man also verwenden, wenn man eigentlich ein Array mit Indexzugriff will, aber noch nicht weiß, wieviel Datensätze man hat, oder sich das ändern kann.
Collections kennen lohnt sich, auch Vector hat seine Berechtigung, PriorityQueue, Maps, ...

EDIT: Aber schön, dass es geholfen hat =)

 

[Pfaeff]

Ich habe halt sehr viele Daten und weiß vorher nicht wie viele und muss häufig add() benutzen und ab und an auch get(). Durch-iterieren geht leider nicht und Löschen muss ich nichts, also denke ich, dass die ArrayList wohl die beste Wahl ist.

danke

 

[Civilazi]

Ich habe halt sehr viele Daten und weiß vorher nicht wie viele und muss häufig add() benutzen und ab und an auch get(). Durch-iterieren geht leider nicht und Löschen muss ich nichts, also denke ich, dass die ArrayList wohl die beste Wahl ist.

Meiner Meinung nach wäre die beste Wahl immer noch eine PriorityQueue, weil die schon tut, was du noch implementieren musstest.