Welche Datenstruktur um schnell zu suchen?

[plem]

Hi zusammen!

Ich habe relativ viele Benutzerprofile die ich beim Starten der Applikation in's Memory lade. Ein Profil kann mehrere Attribute (keys) haben und jedes dieser Attribute kann mehrere Werte (values) haben.

Was für eine Datenstruktur verwende ich da am besten, um möglichst in kurzer Zeit ein bestimmtes Profil zu finden? (Ich muss nach einem oder mehreren values suchen können.)

Danke im Voraus für eure kreativen replies

 

[bygones]

Profile in einen array laden, den sortieren.

dann über binarySearch (in Klasse Arrays implementiert) suchen lassen....

 

[byte]

wenn ein array nicht wünschenswert ist, tuts auch ein TreeSet mit entsprechendem Comparator und Collections.binarySearch(). dann werden elemente sofort richtig eingefügt (man spart sich das explizite sortieren) und es muss kein array mit ner harten obergrenze an elemente initialisiert werden.

 

[plem]

Danke für die Antwort!

Jedoch weiss ich nicht ob ich das so anwenden kann...
Das Problem ist, dass ein Profil mehrere Attribute haben kann. Bsp.

Profil A:
Alter: von 20 bis 30
Hobbies: Segeln, Schwimmen, Tauchen
Interessen: Reisen

Profil B:
Alter: 25 bis 40
Hobbies Schwimmen, Tauchen, Laufen
Interessen: Literatur, Reisen

Nun möchte ich eine Abfrage machen die mir alle Profile ausgibt bei denen das Alter 27 ist, UND als Hobby Schwimmen UND Tauchen haben, UND als Interessen Reisen eingetragen ist. Bei dieser Abfrage sollten nun Profil A und Profil B ausgegeben werden.

Aber ich hab echt keinen Plan wie ich das machen soll... ???:L
Jede Idee ist willkommen!

 

[Bleiglanz]

Hi zusammen!

Ich habe relativ viele Benutzerprofile die ich beim Starten der Applikation in's Memory lade. Ein Profil kann mehrere Attribute (keys) haben und jedes dieser Attribute kann mehrere Werte (values) haben.

Was für eine Datenstruktur verwende ich da am besten, um möglichst in kurzer Zeit ein bestimmtes Profil zu finden? (Ich muss nach einem oder mehreren values suchen können.)

Danke im Voraus für eure kreativen replies

die wichtige Frage ist: wie viele?




rein logisch gesehen bräuchtest du wohl

Map<String,List<String>> // wenn sowohl keys als auch values strings sind

aber suchen kannst du da drin dann nur nach den keys, für die values müsstest du immer ganz durchiterieren

dazu könntest du dir beim Einlesen schon mal umgekeherte Maps aufbauen

Map<String, List<UserPofile>> // für jedes Attribut eine Liste der Profiles

könnte aber ein Performance/Speicherproblem werden

 

[Bleiglanz]

Nun möchte ich eine Abfrage machen die mir alle Profile ausgibt bei denen das Alter 27 ist, UND als Hobby Schwimmen UND Tauchen haben, UND als Interessen Reisen eingetragen ist. Bei dieser Abfrage sollten nun Profil A und Profil B ausgegeben werden.

ist mit java im speicher schlecht zu machen

nimm eine embedded Datenbank (HSQL, Derby) und machs mit SQL

 

[Limit]

Wenn es mehr Daten sind ist wie schon gesagt eine ausgewachsene Datenbank ala SQL die beste Methode. Wenn die Zahl der Attribute also ( Segeln, Schwimmen, Tauschen, Reisen, ... ) fest!! und nicht zu groß ist, würde ich einfach ein boolean-array nehmen. Geschwindigkeit sollten dann eigentlich recht akzeptabel sein. Dann musst du beim Abfragen einmal durch die Liste durchgehen und passende Einträge in eine Ergebnisliste übernehmen. Ist zwar recht viel Overhead aber sollte mit linearem Aufwand gehen.

 

[Elephant]

Hallo,

dazu habe ich auch noch eine Frage. Ich stelle Datensätze in einer JTable dar, mit Hilfe eines eigenen TableModels. Die Daten liegen auch als Objekte vor, die mehrere Variablen mit verschiedenen Werten haben. Um die Tabelle zu filtern, muss ich auf verschiedenen Spalten eine Suche durchführen, wobei ich ja immer die Variablen in den Objekten durchsuchen muss.

Sollte ich dafür die Daten, auch in eine Datenbank legen, ehe ich sie in der JTable darstelle um schneller dannach suchen zu können oder ergibt es zuviel Last, da ich dann ja immer erst die Daten auslesen und bei Änderungen etc. wieder in die Datenbank speichern muss.

Die Anzahl der Datensätze kann so zwischen 100 und 50000 liegen.

 

[AlArenal]

SQL für Java.-Objekte gefällig?

http://josql.sourceforge.net/

 

[TRunKX]

...... Keine lange Rede

da gibbet nur eins XML

 

[AlArenal]

Das halte ich ja für ein Gerücht.. das einzige Problem mit nur einer einzigen Lösung war die Frage nach dem Leben, dem Universum und allem...

 

[TRunKX]

42


und ich finde XML trotzdem toll.

 

[AlArenal]

und ich finde XML trotzdem toll.

Merkste was? Der Thread heißt nicht "Was findet TRunKX toll?"

Schnelles Suchen und Sortieren gemixt mit der Abfrage unterschiedlicher Kriterien.. hört sich für mich nicht gerade nach einem Paradefall für den XML-Einsatz an. Willste das dann alles in XPath machen, oder wie?

 

[TRunKX]

...du wirst es nicht glauben aber ja!
Sollten die Daten keine Imense Menge erreichen so ist das (m)einer Meinung nach sogar Sinvoll ansonsten mach doch SQL wie es vorgeschlagen wurde aber die DAtenbankanbindung ist das Nadelöhr!

 

[AlArenal]

Du übersiehst dabei, dass ich JoSQL vorschlug und in dem Fall gibt es keine Datenbank und damit auch kein Nadelöhr.

Mich würde mal interessieren von wo er diese Benutzerprofile einliest. Wenn die eh schon in einer SQL-DB hocken sollten...

Wenn nicht: Warum nicht?

Übrigens unterstützt HSQL auch das direkte Arbeiten auf CSV-Dateien...

 

[TRunKX]

Naja dann fragen wir doch mal...

Also Thread ersteller wie liegt das vor? Woher kommen die DAten wohin gehen die Daten was haste vor mit den Daten was sind das für Daten?

 

[Elephant]

Also, ich bin zwar nicht der Thread-Ersteller, aber ich hatte die Frage weiter unten gestellt.

Ich lese eine XML-Datei ein, wandele den Inhalt in Objekte um, ein DOM/JDOM Baum frisst zuviel Speicher und ist auch für meine Zwecke unhandlich, und stelle diese Objekte dann in einer JTable dar oder 'Teile' der Objekte in anderen Views. Die Tabelle soll man sortieren und filtern können (und die Einträge editieren).

 

[AlArenal]

Die Tabelle soll man sortieren und filtern können

http://publicobject.com/glazedlists/

 

[Elephant]

@AlArenal
Danke für den Tip. Ich hab nur mal das Sortieren mit GlazedLists und mit der TableSorter Klasse aus Swing ausprobiert für ca 40.000 Zeilen einer JTable, die TableSorter-Klasse war dabei deutlich schneller. Ich weiß nicht ob dafür das filtern mit GlazedLists schneller geht, GlazedLists hat ja auch den Vorteil, dass sich die Listen automatisch aktualisieren etc.

Weiß jemand vielleicht ob filtern, sortieren, suchen vielleicht doch mit einer Datenbank schneller gehen würde?

 

[AlArenal]

Ich habe zwei Jahren oder so mal ne Anwendung mit integrierter SQL-Datenbank erstellt (HSQLDB). Damals habe ich mal ein TableModel direkt über JDBC implementiert und das war grottig lahm...

Wenn du Live-Daten in Swing über ne DB laufen lässt, würde sich das wohl ähnlich verhalten und ich würde nicht viel Performance erwarten, denn deine Anwendung braucht für jede Sortierung / Filterung Zeit um

- den SELECT auszuführen
- die Daten in ein ResultSet zu laden
- aus dem ResultSet die Daten wieder rauszuholen und
- neue Instanzen mit den daten zu erzeugen und diese dann
- in ein TableModel zu laden, um dieses dann
- eine JTable anzeigen zu lassen

Arbeitest du dagegen direkt auf den Objekten sparst du den ganzen Overhead zur Abfrage und zum Umschichten und Verpacken der Daten.

Hattest du mal JoSQL getestet? Damit arbeitest du ebenfalls direkt auf den Objekten und kannst dennoch die gewohnte und gebräuchliche SQL-Syntax nutzen um Daten zu beackern..

 

[Elephant]

Danke für Deine Antwort.

JoSql habe ich mir erstmal nur kurz angeschaut, wollte es mir aber nochmal näher anschauen. Mir ist eigentlich nur erstmal wichtig wie schnell die Suche etc. funktioniert.

 

[Slava]

ich habe der Link zur josql angeschaut ,der AlArenal angeboten hat.
wau!!!!
coole Sache.

und jetzt zum XML!
Ich verstehe überhaupt nicht varum sch... Xml sich durchgesetzt hat???
Für eine beschreibung von kleinen Dokumenten die speter mit css bearbeitet werden, kann ich das noch verstehen.
Aber algemein ist xml der grösste schpeicherfresser allen zeiten.

Beispiel 1
datei person.cvs

name;vorname;
müller;otto;
heiden;jens;



Beispiel 2
person.xml

<? xml ........?>
<person>
<name>müller</name>
<vorname>otto</vorname>
</person>
<person>
<name>heiden</name>
<vorname>jens</vorname>
</person>

jetzt vergleichen Sie die dateigrössen.

Es tut mir leid das ich von Thema abgekommen bin, aber bei wort xml raste ich aus.

 

[AlArenal]

Das ist Anti-XML-Propaganda

XML ist wunderbar um Daten zu beschreiben, umzuwandeln, zu übertragen. Wen ineressiert da die Größe der Dateien, wo Textdaten sich doch wunderbar komprimieren lassen, wenn nötig?

Was würden denn allerlei große und kleine Systeme machen, könnten sie nicht z.B. via Webservice an andere Systeme und Datentöpfe angebunden werden? XML ist die Schlüsseltechnik Insellösungen abzuschaffen und alles immer weiter zu verzahnen.

In der Praxis wiegt die bessere Handhabbarkeit einer 500 KB großen unkomprimierten XML-Datei den Nachteil der Dateigröße gegenüber einer 50 KB großen CSV-Datei locker auf. In der XML-Datei ist klar wie Daten strukturiert sind und welches Format sie haben, bei CSV & Co. nicht.

Aber das auch alles nur so nebenbei (von jemandem, der relativ wenig mit XML zu tun hat)...

 

[AlArenal]

JoSql habe ich mir erstmal nur kurz angeschaut, wollte es mir aber nochmal näher anschauen. Mir ist eigentlich nur erstmal wichtig wie schnell die Suche etc. funktioniert.

JoSQL bringt auch eine eigene Implementierung von TableModel mit, das dürfte für dich interessant sein:

http://josql.sourceforge.net/manual/9-4.html

Dummerweise zum direkten Verlinken ist die Doku in Frames.

http://josql.sourceforge.net/manual/index.html

 

[Bleiglanz]

und jetzt zum XML!
Ich verstehe überhaupt nicht varum sch... Xml sich durchgesetzt hat???
Für eine beschreibung von kleinen Dokumenten die speter mit css bearbeitet werden, kann ich das noch verstehen.
Aber algemein ist xml der grösste schpeicherfresser allen zeiten.

Beispiel 1
datei person.cvs

name;vorname;
müller;otto;
heiden;jens;

Beispiel 2
person.xml

<? xml ........?>
<person>
<name>müller</name>
<vorname>otto</vorname>
</person>
<person>
<name>heiden</name>
<vorname>jens</vorname>
</person>

jetzt vergleichen Sie die dateigrössen.

Es tut mir leid das ich von Thema abgekommen bin, aber bei wort xml raste ich aus.

du bist noch nicht lange in der EDV? oder schon zu lange?

zur CSV Lösung fällt mir jetzt mal auf die schnelle ein:

1) ist die erste zeile ein Datensatz? oder die Kopfzeile? wo steht das? wird ein Computer in 5 jahren noch wissen ob er die erste zeile überlesen muss oder nicht??

Und bei deinem Beispiel: ist am Zeilenende ein ; oder nicht? wer sagt einem das??

2) Escape Schrott: wenn man mit ; trennt, dürfen die Einträge keine ; mehr enthalten, aber welches Escapezeichen soll man verwenden

3) Encoding Schrott: was ist mit ÄÖÜ und chinesischen Schriftzeichen

4) Komplexität: was ist, wenn man mal nicht eine dämliche "Aufzählung von Zeilen" hat, sondern wenn z.B. jede Person noch eine in der Größe variable Liste von "Attributen" zugeordnet hat

5) Keine Constraints: in einer CSV darf jeder SCH* rein, während man bei XML mit Schemas relativ starke Constraints erzwingen kann

usw. usf


Es gibt natürlich Fälle in denen die Dateigrösse ein wichtiger Faktor ist, aber manchmal spielts eben keine Rolle

 

[Elephant]

Hallo,

ich wollte nur noch ergänzen, dass ich JoSql ausprobiert habe und dass es wirklich gut funktioniert und während meinen Tests auch ziehmlich schnell war.