Algorithmus Suche csv-datei

[Landler]

Hallo,
habe hier gerade ein kleines Problem. Es liegen mir paar hundert Gigabyte Daten vor, die in .txt-Files abgelegt sind. Im Prinzip sind die Dateien so organisiert:

blabla 234 blublub 893xxxzos &3asi-343 123828_2321
blabla 234 blublub 845xxxzos &3asi-343 123828_2321
blabla 234 blublub 855xxxzos &3asi-343 123828_2321
blabla 244 blublub 893xxxzos &3asi-343 123828_2321
blabla 244 blublub 845xxxzos &3asi-343 123828_2321
blabla 244 blublub 855xxxzos &3asi-343 123828_2321

Pro Datei handelt es sich vielleicht um 200.000 - 1.000.000 Zeilen

das ganze wird mit fgetcsv geparst:

  
while ( ($line = fgetcsv ($handle, 1000, "\n")) !== FALSE ){  
  // do some stuff with each line  
}  
  

allerdings benötige ich immer nur Zeilen, die den String "855xxxzos" enthalten. Diese Zeile kommt in echt so alle 40-80 Zeilen vor. Dafür nutze ich dann mal das continue-Statement, um gleich aus der weiteren Verarbeitung rauszukommen.

  
while ( ($line = fgetcsv ($handle, 1000, "\n")) !== FALSE ){  
  // do some stuff with each line  
  if(strpos($line, "855xxxzos") === false)) continue;  
}  
  

Das ganze dauert bei ein paar hundert Gigabyte natürlich ne Weile. Wie könnte man das performanter machen?

Könnte man nach gefundener Zeile pauschal mal ein paar Zeilen überspringen?
Ich habe irgendwie keine Idee... oder bleibt nur das komplette Durchforsten Zeile für Zeile?

über eine Idee würde ich mich freuen.
danke

[Kai345]

[latex]Mae  govannen![/latex]

allerdings benötige ich immer nur Zeilen, die den String "855xxxzos" enthalten. Diese Zeile kommt in echt so alle 40-80 Zeilen vor. Dafür nutze ich dann mal das continue-Statement, um gleich aus der weiteren Verarbeitung rauszukommen.

[...]

Könnte man nach gefundener Zeile pauschal mal ein paar Zeilen überspringen?

Kann man nicht beantworten, da hier niemand weiß, wie die Daten erzeugt werden/aufgebaut sind. Kann die Zeichenkette _theoretisch_ auch in zwei aufeinanderfolgenden Zeilen auftreten (und dafür bspw. in den nächsten 100 Zeilen nicht mehr) oder ist _garantiert_, daß nach einer "Trefferzeile" erst mal andere Daten kommen? (garantiert bedeutet hier vom Programm vorgegeben, nicht, daß dieser Fall durch Zufall noch nicht eingetreten ist)
Anhand dieser Kriterien mußt du die Entscheidung treffen.

Stur lächeln und winken, Männer!
Kai

[M.]

Das ganze dauert bei ein paar hundert Gigabyte natürlich ne Weile. Wie könnte man das performanter machen?

Mal abgesehen davon, dass ich bei solchen Datenmengen kein PHP nutzen würde sondern ein Bash-Script oder was in C, solltest du erstmal testen, ob deine Festplatte überhaupt eine höhere Performance hergibt.

Denn wenn die Daten nicht schnell genug von der Platte kommen, hilft dir kein optimiertes Programm.

[Gunther]

Hi!

Das ganze dauert bei ein paar hundert Gigabyte natürlich ne Weile. Wie könnte man das performanter machen?

Mal abgesehen davon, dass ich bei solchen Datenmengen kein PHP nutzen würde sondern ein Bash-Script oder was in C, solltest du erstmal testen, ob deine Festplatte überhaupt eine höhere Performance hergibt.

Ich hätte ja jetzt spontan gesagt, man nehme dafür etwas, was genau für diesen Zweck "vorgesehen" ist, nämlich eine Datenbank der Wahl ...!

Ich frage mich sowieso, "woher" man solche Datenmengen als CSV hat, zumal wenn diese später noch "ausgewertet" werden sollen ...!?

Gruß Gunther

[Landler]

Hi
PHP ist leider Vorschrift. Sicher, ich könnte ein bash-script starten, keine schlechte Idee. Timeout gibts nicht, das Programm kann von mir aus Tage laufen. Nur möchte ich es gerne "beschleunigen"

Ich hätte ja jetzt spontan gesagt, man nehme dafür etwas, was genau für diesen Zweck "vorgesehen" ist, nämlich eine Datenbank der Wahl ...!

Die Daten liegen als Datei vor. Da bringt mir ne DB erstmal gar nischt.

Ich frage mich sowieso, "woher" man solche Datenmengen als CSV hat, zumal wenn diese später noch "ausgewertet" werden sollen ...!?

wissenschaftliche Berechnungen. Ich benötige nur eine Submenge davon.

[M.]

PHP ist leider Vorschrift.

Sorry, aber der, der das vorschreibt, ist ein Vollidiot. Du kannst mich gerne zitieren.

Und wenn irgendwo wissenschaftliche Berechnungen so gemacht werden, dass solche Datenmengen in einer falschen Form bereitgestellt, bzw. gespeichert werden, sag  mir bitte, wo das ist, denn dieses Institut oder diese Firma werde ich nie in Anspruch nehmen, da ich deren Kompetenz massiv in Frage stelle.

[Landler]

PHP ist leider Vorschrift.

Sorry, aber der, der das vorschreibt, ist ein Vollidiot. Du kannst mich gerne zitieren.

brr, ruhig Blut, Brauner. Es ist zur Zeit so, dass auf dem Server eine PHP-Webapplikation läuft, und disese muss mit vorübergehend mit dem Parser kompatibel sein. Ich baue gerade noch einen Parser in einer anderen Sprache. Hat schon alles seine Gründe.

Und wenn irgendwo wissenschaftliche Berechnungen so gemacht werden, dass solche Datenmengen in einer falschen Form bereitgestellt, bzw. gespeichert werden, sag  mir bitte, wo das ist, denn dieses Institut oder diese Firma werde ich nie in Anspruch nehmen, da ich deren Kompetenz massiv in Frage stelle.

Wir haben hier ein System aus den 80ern, und das generiert nunmal diese Datenmengen. Es geht hier um Geodaten, und wer sich nur ein Fünkchen mit Geodaten auskennt, weiß, dass es sich hier meist um sehr große Datenmengen handelt.

Und wie kommst du auf "falsche Form"? Andere Systeme nutzen zum Beispiel das generierte Format generisch. Da ist nix falsch. Falsch denkst du.

[M.]

Und wie kommst du auf "falsche Form"?

Weil eine csv-Datei für solche Datenmengen die falsche Form ist.
Es gab auch schon in den 80ern passendere Systeme, aber wer nach30 Jahren immer noch sowas antiquiertes nutzt, hat IMO die Entwicklung verschlafen.

Mal ehrlich, würdest du Aufträge an eine solche Firma vergeben? Ich nicht.

Was ich aber nicht verstehe, was hat dieser Parser mit der vorhandenen Applikation zu tun? Kompatibilität erreicht man durch entsprechende Schnittstellen, nicht durch die gleiche Programmiersprache.

Das eine hat mit dem anderen absolut nichts zu tun.

[ralphi]

Hi zuammen,

ich kann mich nur anschließen. Wenn die Daten (bei der Größe) nicht adhoc - in echtzeit ausgewertet werden müssen, bietet sich natürlich an, die Daten in der Mittagspause oder Übernacht mit VB6 oder Pascal oder wie auch immer, in eine DB zu schreiben und dann ganz elegant nach Wunsch auzulesen.

php bietet sich zum auslesen von GByte-files sowieso wenig an - servertimeout etc.

Grüße aus LA
ralphi

[M.]

php bietet sich zum auslesen von GByte-files sowieso wenig an - servertimeout etc.

Mal ehrlich, würdest du sowas wirklich als Browseranwendung realisieren?
In der Kommandozeile oder GUI gibt es keinen Servertimeout.

[Landler]

Hi,

ich kann mich nur anschließen. Wenn die Daten (bei der Größe) nicht adhoc - in echtzeit ausgewertet werden müssen, bietet sich natürlich an, die Daten in der Mittagspause oder Übernacht mit VB6 oder Pascal oder wie auch immer, in eine DB zu schreiben und dann ganz elegant nach Wunsch auzulesen.

wenn ich > 200 GB Daten in ne DB schreibe, bringt mich mein Chef um...

php bietet sich zum auslesen von GByte-files sowieso wenig an - servertimeout etc.

sehe ich nicht zwingend so. PHP 5.3.x kann das mittlerweile genausogut oder schlecht wie PERL oder Python. Zumindest mit PERL und Python habe ich Benchmarks gemacht, das tut sich nicht viel. Du denkst, VB6 tut das schneller? Zur Zeit baue ich mir einen kleinen C-Parser. Mal gucken, wie schnell der das durchzieht.

[M.]

wenn ich > 200 GB Daten in ne DB schreibe, bringt mich mein Chef um...

Ähm .... welcher Chef hat denn was gegen effiziente Arbeit? Oder hast du deinem Chef nicht erklärt, wieso eine Datenbank massive Vorteile hat?

[ralphi]

Hi

wenn ich > 200 GB Daten in ne DB schreibe, bringt mich mein Chef um...

musst ja nicht die gute orakel oder informix vom chef beschmuddeln, schnapp dir halt einen 'alten Rechner' und klatsch MYSQL drauf ;-)

Das es, wenns in einer DB drin ist, eleganter geht, siehst Du ja auch so - oder?
hast du wahrscheinlich eh schon so gemacht!?

grüßle ralphi

[Encoder]

Ergänzend zum schon gesagten

blabla 234 blublub 893xxxzos &3asi-343 123828_2321

Alle gleich lang?
Dann könntest du in der Datei springen und da weiterlesen wo du glaubst dass die nächste Zeile sein könnte. Vorher sollte natürlich keine sein, das müsstest du sicher wissen.

Es kommt dann noch drauf an wie lang die Zeilen überhaupt sind. Dateien werden in Blöcken gelesen. Wenn du mit Springerei nicht mehrere Blöcke überspringst, bringts schon mal nichts mehr.
Du könntest natürlich auch größere Blöcke der Datei auf einmal lesen und da dann springen.

Aber vielleicht wirklich nicht mit PHP.

[hotti]

Moin,

möglicherweise ist unpack() performanter als ein zeichenorientiertes Splitten. In Perl würde das so aussehen je Zeile:

  
my $r = [unpack("A7A4A8A10A10A11", 'blabla 244 blublub 893xxxzos &3asi-343 123828_2321')];  
print $r->[3]; # 893xxxzos  

Das wäre mal zu testen und zu vergleichen.

Hotti

[hotti]

Zur Info ;)

möglicherweise ist unpack() performanter als ein zeichenorientiertes Splitten.

Bei meinem Test war der Unterschied unwesentlich. Zum Testen habe ich eine Datei mit 52MB erzeugt und 1 Mio Zeilen "blabla 244 blublub 893xxxzos &3asi-343 123828_2321".

Perl braucht auf meiner Kiste ca 6 Sekunden für einen Durchgang durch die Datei. Mit [split] oder [unpack] auf jede Zeile verlängert sich die Zeit auf ca 12 Sekunden. Unwesentlich länger dauert es jedoch, wenn eine RegEx auf jede Zeile angewandt wird, das geht in ca 7 Sekunden durch die Datei.

Hotti

[Azure]

Hallo,

vielleicht die Daten aus der CSV-Datei schon mal im RAM cachen, so dass das langsame Einlesen das schnelle Durchsuchen nicht ausbremst.

Desweiteren wäre das IMHO eine Aufgabe die sich wunderbar parallelisieren lässt. Also bspw. irgendwie über Multithreading.

Viele Grüße

[Linuchs]

while ( ($line = fgetcsv ($handle, 1000, "\n")) !== FALSE ){
  // do some stuff with each line
  if(strpos($line, "855xxxzos") === false)) continue;
}

  
Ich würde nicht den ganzen Suchstring abfragen, sondern zuerst eine grobe Selektion auf eine Stelle machen, um die meisten Zeilen schon mal ausscheiden zu können:  
  
blabla 234 blublub 893xxxzos &3asi-343 123828\_2321  
\----.----1----.----2----.----3----.-----4----.----5  
  
Auf Stelle 21 suchst du die 5, alle anderen Zeilen interessieren nicht.  
if ( $line[20]=="5" ) ...  
Von den Gültigen muss auch Stelle 22 eine 5 haben.  
Erst an dritter oder vierter Stelle den gesamten Suchstring in den verbleibenden ca. 2% der Zeilen abgleichen.