Textindexierungs Algorhitmen

Jester

hm, vielleicht hängt er an dem UraltSTL-Bug vom VC6?

Ansonsten mal mit nem istreambuf_iterator drüberlaufen, das ist eigentlich recht flott.

Bashar: nicht eher nach "\nP\n"?

Bashar

Äh ja richtig Plus Spezialfall, dass "P\n" am Anfang der Datei steht, und evtl. ob "\nP" am Ende der Datei steht, falls man nicht Newline-abgeschlossene Dateien zuläßt.

the_alien

Optimizer schrieb:

Wenn du nicht mehr Informationen über den zu durchsuchenden Text hast, wirst du wahrscheinlich den Algorithmus nicht verbessern können. Aber 50 Sekunden für lächerliche 8 MB ?? Liest du jedes Byte einzeln von der Platte?

Ums gleich vorweg zu sagen, ich machs mit Java. Aber wir sind ja in "Rund um die Programmierung"

Das mit den 50 Sekundne für 8 MB stößt mir auch ziemlich auf.
Eigentlich gehe ich hin und lese eine Zeile aus der Datei und guck ob sie nur ein Zeichen lang ist und ein "P" enthält.

Leider hab ich im vorhinein keine Informationen über die Datei, also Länge der Seite, Anzahl der Zeichen oder sonstiges...

Alles was ich weiss ist, dass die Zeile entweder ein Leerzeichen am Anfang hat, oder ein einzelnes "P" in ihr steht.

Schalte einen BufferedStream dazwischen oder poste doch gleich mal ein bisschen Code, so groß kann der nicht sein. Das darf auf keinen Fall so lange dauern.

Und dann wäre es noch interessant zu wissen, in welcher Zeichenkodierung die Datei gespeichert ist. Wenn es UTF-8 oder ISO bla blubb ist, wäre es töricht, nen Reader zu nehmen, der alles in Java-chars umwandelt.

the_alien

while(buff.indexOf("null") != 0){
			if(buff.indexOf("P") == 0 && buff.length() == 1){
				PageCount ++;
				CurrentLineCount = 0;
				FilePosWrapper = new Long(pos);
				PageFilePointers.addElement(FilePosWrapper);
//				when updated to 1.5 use this: PageFilePointers(Long.valueOf(file.getPos()));
			}
			pos = file.getPos();
			buff.delete(0, buff.length()); 					
			buff.append(file.readLine());
		}

Ich denke der Quelltext ist verständlich genug.
Wie schalte ich einen BufferedStream dazwischen?

Achja: file ist ein RandomAccessFile

Termite

Hi

[edit]
ich habs geant das er sowas in der art macht

String line = in.getLine(); // Zeile der Textdatei besorgen

if (line.length() == 1) // Zeilenlänge prüfen
{
  if (line.getChar(0) == 'P') // inhalt ein P
  {
    // DO something
  }
}

ich würd versuchen das auf Byte ebene zu lösen.

\nP\n währe ja dann unter windows 0x13 0x10 0x50 0x13 0x10 für Unix/Linux und Appel siehts dann entsprechend anders aus 0x10 0x50 0x10 oder 0x13 0x50 0x13.

man müsste dan dafür eine nentsprechenden Automaten basteln. ( der hat ja nur 3/5 zustände)

einen BufferdReader/BufferdInputStream dazwischen schieben ist ein muss

ZeilenNummern mit zählen währe auch kein problem.

das was mir dann noch einfällt wird dan aufwendiger zu implementieren. würde Multithreading was bingen?
1 thread kümmert sich um das einlesen der datei, ein oder mehre andere threads um das auswerten des ByteArrays. Ich weis nähmlich nicht wie effizient so ein BufferdReader implementiert ist.

[edit]

von welchem typ sind buffer und file? das anlegen dieser Variablen währe auch interesant

gruss Termite

Shade Of Mine

wozu brauchst du buff?
der ganze code ist komisch.

Vorschlag:

String line;
int pos=0;
while( (line=file.readLine()) != null)
{
  if(line.equals("P"))
  {
    //wozu auch immer?
    ++pageCount;
    currentLineCount=0;

    pageFilePointers.addElement(new Long(pos));
  }
  pos+=line.length();
}

das "while(buff.indexOf("null") != 0)" verstehe ich nicht

file sollte natuerlich ein BufferedReader sein.

Wozu eigentlich ein RandomAccessFile??

the_alien

Ja, so ziemlich genau so läuft das ganze ab.

Ich weiss nicht, was mich da so Performance kostet, aber das RandomAccessFile dürfte es nicht sein.

Wenn ich die Datei nach den P's durchsuche dauert das ein paar mal so lang, als wenn ich einfach hingehe und die Datei von vorne nach hinten einlese, Steuerzeichen über reguläre Ausdrücke ersetzen lasse und das dann auf der Konsole ausgebe.

while(buff.indexOf("null") != 0)

Was ist das?
Was ist buff überhaupt?
[hier stand wahrscheinlich Unsinn]

Und warum brauchst du Random Access? Für was anderes noch? Wenn nicht, wäre es reichlich... unnötig.

Shade Of Mine

the_alien schrieb:

Ich weiss nicht, was mich da so Performance kostet, aber das RandomAccessFile dürfte es nicht sein.

offensichtlich ist mal buffer, der absolut sinnlos ist und ne menge kopieren muss.
Dann verwendest du scheinbar keinen BufferedReader was ziemlich starke IO Last verursacht.

und wieviel ein RandomAccessFile an overhead mitbringt, weiss ich nicht, aber gratis ist das sicher auch nicht.

ist aber schwer genaueres zu sagen, wenn du keine informationen hergibst...

Termite

Hi

das convertieren eines byteArrays in einen String kostet erstam zeit.
Ohne Bufferd.... wird jede zeile einzeln von der Festplatte angefordert. kostet auch wieder zeit.

gruss

virtuell Realisticer

Termite schrieb:

Hi

das convertieren eines byteArrays in einen String kostet erstam zeit.
Ohne Bufferd.... wird jede zeile einzeln von der Festplatte angefordert. kostet auch wieder zeit.

gruss

Stichwort: Memory Mapped I/O

mfg
v R

the_alien

Ok, ich versuche das jetzt mal komplett auszulagern, so dass ich kein RandomAccessFile mehr nutze und das hin und herkopieren zu unterlassen, ich meld mich dann im laufe des Tages nochmal

Bashar

Termite schrieb:

\nP\n währe ja dann unter windows 0x13 0x10 0x50 0x13 0x10 für Unix/Linux und Appel siehts dann entsprechend anders aus 0x10 0x50 0x10 oder 0x13 0x50 0x13.

Gibts in Java keine Textstreams?

Termite

@Bashar

mein gedanke war die Strings einfach zu umgehen, und diereckt auf einem byte[] zu arbeiten. mit einer art switch case do while konstruction. jesesmal wenn ein String angelegt wird wird ein neues Object angelegt, was wieder zeit kostet.

// WINDOWS LOESUNG
      File file = new File( fileName );
      BufferedReader in = new BufferedReader( new FileReader( file ) ); // Dateiinput

      int lineCount = 0; // zeilenzähler
      int pos = 0; // byte position

      int state = 0; // für die Statemachine
      int c = 0; // das zuletzt gelesene zeichen

      while ( ( c = in.read() ) != -1 ) // ggf optimierungs möglichkeit wenn wir auf einen 
                                        // Array arbeiten, das ein anderer Thread einliest.
      {
         pos++;
         switch (state)
         {

            case 0 :
               if ( c == 0x13 )
                  state = 1;
               else
                  state = 0;
               break;
            case 1 :
               if ( c == 0x10 )
               {
                  state = 2;
                  lineCount++;
               }
               else
                  state = 0;
               break;
            case 2 :
               if ( c == 0x44 )
                  state = 3;
               else
                  state = 0;
               break;
            case 3 :
               if ( c == 0x13 )
                  state = 4;
               else
                  state = 0;
               break;
            case 4 :
               if ( c == 0x10 )
               {
                  // Do something
                  // jetzt haben wir eine zeile gefunden mit nur einem P gefunden
                  lineCount++;
                  System.out.println("Page gefunden L: " + lineCount + " pos " + pos  );
                  state = 2; // es könnte ja direckt drunter noch ein P kommen ;)
               }
               else
                  state = 0;
               break;
         }
      }

ich post eigentlich ungern fertigen Code. aber vileicht wirds dadurch verständlicher was ich mein.

gruss

Bashar

Von Strings hab ich nichts gesagt. Heißt das also, in Java gibts Textstreams nur über Strings? OK dann fällt das offensichtlich flach.

Korbinian

also nachdem java ja bekanntermassen nicht so der hammer ist, wenn dauernd irgendwelche variablen erstellt gelöscht etc werden, würde die ganze datei auf einen haps in einen string (oder vergleichbares) hauen, und dann über diesen laufen. dann haste auch nicht nervige io zugriffe (die meines erachtens die monsterzeit bei dir ausmachen). wenn dir alles auf einmal etwas viel ist, dann lies doch immer 512 byte oder so, und laufe über die. afaik kannste mit java auch auf byte ebene runter gehn

the_alien

Habe jetzt so ziemlich genau Shadow of Mine's Lösung übernommen und die Zeit auf weniger als 1 Sekunde (800 ms) für die 8 MB Datei runterbekommen.

Termites Lösung werde ich auch einmal einem Speedtest unterziehen sobald ich wirklich große Dateien zum testen kriege.

Danke euch, ihr habt mir den Tag gerettet

(Blöd wenn alle Java Programmierer hier im Betrieb auf der Cebit sind ;))

@Bashar: In Java gibt es an I/O wirklich alles, was man sich nur vorstellen kann. :p
Meinste sowas? Wenn nicht, dann bitte genauer spezifizieren (dass char != byte ist, weißt du ja sicher). http://java.sun.com/j2se/1.5.0/docs/api/java/io/InputStreamReader.html

Korbinian schrieb:

also nachdem java ja bekanntermassen nicht so der hammer ist, wenn dauernd irgendwelche variablen erstellt gelöscht etc werden, würde die ganze datei auf einen haps in einen string (oder vergleichbares) hauen, und dann über diesen laufen. dann haste auch nicht nervige io zugriffe (die meines erachtens die monsterzeit bei dir ausmachen). wenn dir alles auf einmal etwas viel ist, dann lies doch immer 512 byte oder so, und laufe über die. afaik kannste mit java auch auf byte ebene runter gehn

Hmmmm was spricht denn dagegen, nen Stream ordentlich zu buffern und einfach alles nacheinander auszulesen? Wir brauchen ja nur sequentiellen Zugriff. Also etwa so:

[BufferedReader <= InputStreamReader] (oder auch nicht, wenn man direkt auf den bytes arbeiten will) <= BufferedInputStream <= FileInputStream