Java:Frage zur Datenstruktur

[SGT.Hawk]

Welche Datenstruktur würdet ihr nehmen bei folgenden Vorraussetzungen:Es sollen Kontake mit Namen,Adresse,usw abgespeichert werden.NAtürlich muss dann auch gesucht werden,aber es mussen nach allen gesucht werden können,dass heisst es gibt keine eindeutigen Keys.Es kann nach Name,Adresse usw gesucht werden.Man kann eben mehrere Ergebnisse haben.Und wie kann man das am besten mit welcher GUI Komponente lösen.Also ich dachte eher an einem Table.

[HellHorse]

Von wie vielen Objekten reden wir hier?

[Monger]

Vielleicht gibt es eine elegantere Möglichkeit, aber ich denke gerade an diese:

Objekte können ja vergleichbar gemacht werden, wenn sie das "Comparable" Interface implementieren. Sie müssen dann die Methode "CompareTo" erfüllen, um sagen zu können ob zwei Objekte des selben Typs gleichgroß, größer oder kleiner sind.


Normalerweise implementiert man diese CompareTo Methode statisch, d.h. das Objekt wird IMMER zuerst nach Name, dann nach Vorname, dann nach Adresse usw. sortiert.

Du könntest aber die Sortierungsreihenfolge von einem Attribut abhängig machen, das z.B. statisch in die Klasse eingebettet ist.

Also z.B. :



class Person implements Comparable{

public String nachname;
public String vorname;
public String adresse;
// usw.

public static int sortiermodus;

public int CompareTo(Object o){
Person anderePerson = (Person) o;
int comparator = 0;
/* Wirft Class Cast Exception. Möglicherweise gibt es aber mit
Generics auch inzwischen eine saubere Lösung dafür */
comparator = this.nachname.compareTo(anderePerson.nachname);
if (comparator != 0) return comparator;
comparator = this.vorname.compareTo(anderePerson.vorname);
if (comparator != 0) return comparator;

// so oder ähnlich Logik aufbauen, und an den sortiermodus koppeln.
}
}


Wenn erstmal deine Person mit einer anderen auf die Weise vergleichbar ist, kannst du jede beliebige Datenstruktur nehmen die auf dem Comparable Interface aufbaut. Mit Hilfe eines "List" Objektes kann man sich z.B auf die Weise Teile eines Vectors sortieren lassen.

[SGT.Hawk]

@Ja,also Sortierung ist nicht gebraucht,weil ich ja nach verschiedenen Begriffen suchen kann,und dann wird eh nach dem Begriff sortiert,also muss ganz flexibel sein.Ich werde es nicht nach einen Memeber sortieren,sonst hätte ich einen Set genommen,der das Comparable implementiert.

Also,Objekt Anzahl in Blick auf die Zukunft,sagen wir mal 1000.

[Monger]

Hrm...

Hilft es was, wenn du die "equals" Methode überschreibst? Damit kannst du dann Mehrdeutigkeit erzwingen. Du müsstest dir dann aber trotzdem noch etwas basteln, was alle Einträge prüft ob sie jetzt dem Suchkriterium entsprechen oder nicht, und diese dann in eine neue Liste einordnen.

Wie performant das aber letztendlich ist, kann ich nicht sagen.

[SGT.Hawk]

Ja,so habe ich mir das auch gedacht.Alle Einträge rausholen und das in eine temporäre List abspeichern.
equals muss ich sowieso für die Daten überschreiben,da sonst ein Vergleich nicht möglich ist.

[Pinoccio]

@Ja,also Sortierung ist nicht gebraucht,weil ich ja nach verschiedenen Begriffen suchen kann,und dann wird eh nach dem Begriff sortiert,also muss ganz flexibel sein.Ich werde es nicht nach einen Memeber sortieren,sonst hätte ich einen Set genommen,der das Comparable implementiert.

Also,Objekt Anzahl in Blick auf die Zukunft,sagen wir mal 1000.Es hängt stark vom konkreten Zweck ab, aber wenn du nur selten neue hinzufügst bzw alte lsöchst aber viel suchst, lohnt sich eine Sortierung schon. (Denk ans Telefonbuch zB)
Wenn du selber was schreiben willlst, dann eine mehrfach verkette Liste.
Und für deine/eigene Objekt ist es meistens sinnvoll, schon von Anfang an sich zu überlegen, welche Interfaces man, sei es nun cloneable, seriable oder eben comparable.

mfg Sebastian

[SGT.Hawk]

Also,ich denke mal,es wird viel hinzugefügt und wieder gelöscht,sind ja nur Kontakte.Also würde eigenlich eine LinkedList Sinn machen.Bei einer Sortierung wäre das einfügen langsamer,da die richtige Stelle erst mal gesucht werden muss und Worst Case wäre dann O(N),während bei unsortiert O(1),da man einfach am Ende einfügt.Beim Suchen wäre natürlich das Sortierte schneller.

[Pinoccio]

Also,ich denke mal,es wird viel hinzugefügt und wieder gelöscht,sind ja nur Kontakte.Also würde eigenlich eine LinkedList Sinn machen.Bei einer Sortierung wäre das einfügen langsamer,da die richtige Stelle erst mal gesucht werden muss und Worst Case wäre dann O(N),während bei unsortiert O(1),da man einfach am Ende einfügt.Beim Suchen wäre natürlich das Sortierte schneller.Hm, Einfügen in sortierte Liste im Schnitt O(log n), was natürlich immer noch langsamer als O(1) ist.
Beim Suchen ist es dann ähnlich, sortiert im Schnitt O(log n) gegen O(n).
(alles imho)

mfg Sebastian

[Monger]

Das Beispiel mit dem Telefonbuch ist gut...


Angenommen ich suche X Einträge, die alle gleich heißen. Wenn ich vorher sortiere, müssen alle Einträge direkt nebeneinander liegen.Einen davon zu treffen, ist per Baumsuche O(log n). Die jeweils angrenzenden zu treffen, ist jeweils O(1), bis man halt oben oder unten keinen Treffer mehr hat. Dann kann man sich die restliche Suche auch sparen.

Ich denke, wenn es wirklich um Performance geht, kommt man mit dieser Variante relativ glücklich weg. Ich glaube nur nicht, dass es sowas im JDK schon gibt, möglicherweise müsste man sich da selbst was stricken.

[Pinoccio]

Ich glaube nur nicht, dass es sowas im JDK schon gibt, möglicherweise müsste man sich da selbst was stricken.Geben im JDK nicht, aber es gibt zum Selberstricken genug Vorlagen (http://www.google.com/search?num=100&hs=br5&hl=en&lr=&safe=off&client=firefox-a&rls=org.mozilla%3Ade-DE%3Aofficial&q=java+sortedlist&btnG=Search), die man nutzen kann.
Problem für dich wäre wohl, daß du ja nach verschieden Schlüsseln deine Objekte sortieren willst, das wird viel Arbeit, da du ja eigentlich nicht sortierst, sondern nur passendeinfügst und löschst.
Ist halt die Frage, Performance zur Laufzeit oder schnelle Entwicklung.

mfg Sebastian

[ethrandil]

Joah, wenns auf die seek-time ankommt: einfach für jedes Objekt eine TreeMap.

Geht aber nur, wenn du nach exakten Attributen suchst! Wildcards (ethra*) gibts dann nicht.

- Eth