Wahl der Datenstruktur für die Suche.

[145145145]

Hallo!

Ich habe eine Datei wie:

4 2 5 3 2
1 1 5 1 12
1 1 13 1 19
1 4 1 8 3
....

In jeder Zeile steht eine Kombination aus n Zahlen. Diese Datei muss ich einlesen (was kein Problem ist) und dann durchsuchen können. Dabei soll als Ergebniss die Zahl rauskommen, wo oft die gesuchte Kombination (z.B. 1 4 1 8 3 ) oder eine Schema (z.b. 1 * 1 8 3 oder * * * 5 3, * steht für beliebig) vorhanden ist. Da es sich um die Dateien mit mehr als 50000 Zeilen handelt ist die Wahl der Datenstruktur für die effiziente Suche wichtig.
Kann mir jemand dabei helfen?
Danke!

Igor

 

[tfa]

Am einfachsten wäre es, jede Zeile als String zu speichern und in einer Liste abzulegen.
Zur Suche wird jeder String der Liste dann mit dem Suchkriterium als regulärem Ausdruck verglichen.

Alternativ könnte man auch int-Arrays abspeichern und diese dann mit einer selbstgebastelten Vergleichsfunktion suchen.
Das könnte performanter sein, aber auch aufwendiger zu programmieren.

 

[Guest]

gibts eine Sortierung der Zahlen in deiner Datei? Wenn nicht musst du entscheiden ob du durch eine Sortierung Vorteile hast, wenn du zum Beispiel die Datei einmal am Programmstart einlesen musst und dann im weiterem Verlauf keine Änderungen an den Daten und viele Abfragen stattfinden wirst du mit einer sortierten Datenstruktur wesentlich besser fahren.

 

[Marco13]

Was einem die Sortierung bei einer Anfrage wie
* * * * 1
bringt, weiß ich jetzt aber nicht... dafür müßte man nach wie vor die gesamten Daten durchsuchen...

 

[nebulo]

Gib mal ein paar mehr Informationen. Wird z.B. auf einem Satz Daten diese Suche öfter ausgeführt?

 

[Marco13]

Das Problem ist ja das gleiche wie "SELECT FROM WHERE"-Anfragen wie bei Datenbanken - da habe sich viele Leute schon Gedanken drüber gemacht. Aber wenn es wirklich nur um die Anzahl der Zeilen geht (und nicht um die Zeilen selbst), sehe ich im wesentlichen zwei Möglichkeiten: Etweder, bei jeder Anfrage brute-force durch die Zeilen laufen, und die ints nacheinander vergleichen. Oder sich beim Einlesen "irgendeine" "Indizierungs-Struktur" aufzubauen, die dann aber evtl. ziemlich kompliziert und platzhungrig sein könnte....

 

[Guest]

Was einem die Sortierung bei einer Anfrage wie
* * * * 1
bringt, weiß ich jetzt aber nicht... dafür müßte man nach wie vor die gesamten Daten durchsuchen...

indem Fall schon, wenn du allerdings 1 1 * * * als Anfrage hast musst bei Sortierung nur nach 11 als die ersten beiden Stellen suchen, was sehr viel schneller geht als die kompletten 50000 Datensätze zu durchlaufen. Wenn man zum Beispiel ein TreeSet nimmt kann man bei der suche nach 11*** ein einfaches subSet(11000,12000) ausführen und schon hat man seine Ergebnisse in O(log n). Bei einer unsortierten Datenstruktur müsste man den kompletten Datenbestand durchlaufen, d.h. O(n).

Die Frage ob sich der zusätzliche Aufwand für die Sortierung lohnt kann man aber mit den bekannten Infos nicht beantworten

 

[Guest]

Die Daten in der Datei sind nicht sortiert. Die Datei wird während der Abarbeitung nicht verändert. Es geht nur darum zu zählen wie oft eine bestimmte Kombination bzw. Schema da ist.

Die Suche wird sehr oft durchgesucht. mind. (Anzahl der Zeile)*0.1. Deswegen auch die Optimierungsversuche. Die Implementierung mit int-Arrays ist leider zu langsam...

 

[nebulo]

Ich habe jetzt nicht genauer darüber nachgedacht aber wenn du tatsächlich oft in den Daten suchst würde es sich wahrscheinlich lohnen auf irgendeine Art zu sortieren.

Ich habe mal einen Ansatz, sehr viel habe ich nicht darüber nachgedacht und es gibt sicher Bessere:

1. Daten in einen Int-Array einlesen und sortieren
2. Per Interpolationssuche nach dem entsprechenden Element suchen

Bei den * musst du wohl jeweils einmal für alle Sterne eine 0 und einmal für alle Sterne eine 9 eintragen. Dann bekommst du einen Bereich in dem sich das entsprechende Element befinden könnte....

Natürlich ist der Algorithmus im WC (***...*x) sehr schlecht. Aber ich denke das lässt sich kaum umgehen.

 

[Marco13]

Den Ansatz hatte ich einen Moment lang auch im Kopf: Wenn man eine Anfrage hat wie
1 * * * *
Dann lässt man sozusagen für die Sterne die Zahlen 0 0 0 0 bis 9 9 9 9 durchlaufen, und macht für jede dieser Zahlen eine Anfrage, und bekommt damit das Endergebnis. Dann habe ich aber gemerkt, dass in dem Beispiel auch Zahlen >9 vorkommen, d.h. man kann offenbar NICHT für jeden * nacheinander alle möglichen Zahlen einsetzen. (bzw. es würde zu lange dauern, jede dieser Stellen von -Integer.MAX_VALUE bis Integer.MAX_VALUE laufen zu lassen :lol: )

50000 Zeilen sind nicht sehr viel. Zum Durchsuchen IST es viel, insbesondere wenn die Suchanfragen mit *** gestellt werden, und es VIELE Suchanfragen gibt. Aber in bezug auf den Speicher sind 50000 int-Arrays schon verdammt wenig. D.h. es wäre in diesem Fall wohl vertretbar, eine (in bezug auf den Speicher) "veschwenderische" Index-Datenstruktur aufzubauen, die Suchanfragen dann in O(n) erlaubt (n ist die Anzahl der Zahlen in einer Zeile, und NICHT Anzahl der Zeilen!!!), also (bei konstanter Zeilenlänge) in konstanter Zeit.

Ich hatte schon angefangen, sowas zu versuchen, hatte aber nicht genug Zeit. Falls es nicht klappt, versuch' ich's bei Gelegenheit nochmal. Ich wüßte auch nicht, wie man eine ECHT konstante Anfrage-Zeit hinkriegen könnte, aber mein erster Ansatz war der folgende:
Man liest die Zeilen nacheinander ein
...
4 2 5 3 2
1 1 5 1 12
1 1 13 1 19
1 4 1 8 3

Für jede Zeile speichert man sich ein "Zeile"-Objekt, das die Zahlen enthält. Diese Zeilen legt man in einer Datenstruktur ab, die einem
- zu einer Stelle k innerhalb der Zeile
- für die Zahl x, die an der k-ten stelle steht
- die Menge der Zeilen liefert, die an der Stelle k die Zahl x haben.

Also sinngemäß sowas:

Map<Integer, Set<Line>> lineMaps[] = new HashMap<Integer, Set<Line>>[n]; // n = Anzahl der Zahlen in einer Zeile
for (i=0..n) lineMaps[i] = new new HashMap<Integer, Set<Line>>();
for (all Lines)
{
    line = readLine();
    for (i=0..n)
    {     
         int x = line.at(i); 
         HashMap<Integer, List<Line>> lineMap = lineMaps[i];
         Set<Line> setOfLinesWithXatI = lineMap.get(x);
         if (setOfLinesWithXatI==null) createItAndPutItIntoLineMap();
         setOfLinesWithXatI.add(line);
    }
}

Wenn man dann eine Anfrage stellt wie
3 8 13 5 21
dann schaut man in dieser liste nach, und erhält die Mengen der Zeilen die
eine 3 an Stelle 0 haben
eine 8 an Stelle 1 haben
..
eine 21 an Stelle 5 haben

Man holt sich also

Set<Line> set0 = lineMaps[0].get(3);
Set<Line> set1 = lineMaps[1].get(8);
Set<Line> set2 = lineMaps[2].get(13);
Set<Line> set3 = lineMaps[3].get(5);
Set<Line> set4 = lineMaps[4].get(21);

(eigentlich natürlich als Set<Line>[n]-Array...)

Die * Sternchen behandelt man entsprechend über eine Vereinigung der Mengen. Bei einer Anfrage wie
3 8 13 * 21
holt man sich also

Set<Line> set0 = lineMaps[0].get(3);
Set<Line> set1 = lineMaps[1].get(8);
Set<Line> set2 = lineMaps[2].get(13);

Set<Line> set3 = new HashSet<Line>();
for (Set<Line> subSet : lineMaps[3].values())
{
    set3.addAll(subSet);
}

Set<Line> set4 = lineMaps[4].get(21);

Bis dahin hat man die Information in "konstanter" Zeit erhalten (wobei die Sternchen die Zeit schon "ein bißchen" drücken können auf "linear in bezug auf die Anzahl der Mengen, für die ein Sternchen steht").

Was jetzt definitiv NICHT konstant (und - je nachdem, wie die Liste der Zeilen aussieht - leider u.U. noch recht aufwändig (und im schlechtesten Fall sogar noch aufwändiger als die Brute-Force-Suche) ist) ist, festzustellen, welche Zeilen ALLE diese Bedingungen erfüllen. Das kann man dann über eine Schnittmengenbildung aller sets machen:

Set<Line> finalSet = set0;
finalSet.retainAll(set1);
finalSet.retainAll(set2);
finalSet.retainAll(set3);
finalSet.retainAll(set4);

Die gesuchte Zahl erhält man am Ende

int numberOfLinesMatchingTheQuery = finalSet.size();

Ich glaube kaum, dass es eine Möglchkeit gibt, die Schritte (bis auf den letzten) schneller zu machen. Abgesehen vom letzten Schritt sind es eigentlich nur lookups in Arrays oder HashMaps.

Der letzte Schritt ist ... :? .. hmja.... im worst case eben übelst langsam. Wenn man NUR Zeilen der Form
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
...
hat, und als Anfrage dann
1 2 3 4 5
stellt, holt man sich 5 mal die gleiche Set mit jeweils 50000 Elementen und bildet von denen dann die Schnittmenge (die wieder die gleiche ist), d.h. man hat 250000 Operationen. Diese Operationen wären zwar evtl. immernoch schneller als der echte Vergleich der einzelnen Zeilen-Elemente bei der Brute-Force-Suche, aber trotzdem bestünde da noch Optimierungspotential: FALLS in der Eingabemenge sehr of die gleichen Zeilen vorkommen würde es sich dann lohnen, die Datenstruktur aufzubohren, so dass nicht wirklich die Zeilen gespeichert werden sondern, die Anzahl der Zeilen. D.h. man würde sich in obigem Beispiel nicht 50000 mal die Zeile
1 2 3 4 5
speichern, sondern sich nur EIN mal merken, dass die Zeile "1 2 3 4 5" genau 50000 mal vorgekommen ist. Das wäre dann sowas wie eine

HashMap<Integer, Map<Line, Integer>> lineMaps[] = ...

Dafür würde man sich wohl eine "komfortablere" Klasse schreiben, und bei der Vereinigung/Schnittmengenbildung müssten entspechend nicht die Sets selbst, sondern die KeySets vereinigt/geschnitten und die hinteren "Integers" (die die für jede Zeile speichern, wie oft sie vorgekommen ist) entsprechend angepasst werden....

Vielleicht hilft's als möglicher Ansatz.