[Delphi] Effectief zoeken in grote tekstfile

[TheLunatic]

Ik zit hier (nog steeds ) met een hele grote tekstfile, waar ik snel data uit wil halen. Ik wil NIET gebruik maken van een StringList, daarvoor is de file gewoon de groot.

Het gaat om een aantal (6 miljoen nogwat) gesorteerde records. Ik heb de index. Daarbij horen gegevens, die in die tekstfile staan. Wat ik dus kan doen is halverwege de tekstfile kijken, en kijken welke index die regel heeft. Is mijn index groter, kijk ik halverwege de achterste helft, etcetera, een bekende methode lijkt me.

Alleen, ik heb vanalles geprobeerd dit te realiseren in Delphi, maar het lukt me gewoon niet. Ik kan niet op een snelle manier achter het aantal regels komen, ik kan niet naar een bepaalde regel springen (wel naar een bepaalde positie zijnde karakter), met andere woorden, ik kom er gewoon niet uit.

<sub>Ik weet niet of zo'n soort topic wel mag, omdat het misschien een erg luie weg van programmeren lijkt, maar ik wil het gewoon weten

Dus als het niet mag dan gaat het slotje erop, maar dat risico loop ik dan maar.</sub>

[whoami]

Me dunkt dat je tekstfiles enkel sequentieel kunt inlezen.
Dus als je regel n wilt inlezen, zul je regels 1 tem n-1 ook moeten inlezen.

[Killemov]

Ehm ... je hebt een index ... Leuk, maar wat heb je eraan als het niets indexeert? Wat je dus moet doen, als je die index niet aan kan passen, is een pointer bij je indexveld opnemen. Dus jansen0001->23423424, dan is jansen0001 je index en 23423424 de offset in je file. Hiermee heb je in feite een flat-file table gemaakt.

[TheLunatic]

Misschien wordt het zo duidelijker:

Stukje uit FILE1

code:

0543516825  265787145
0543516827  265826094
0543516830  128361536
0543516831  169632976
0543516834  265824732
0543516835  145399283
0543516836  126630186
0543516837  265824096
0543516838  265823966
0543516839  337231966
0543516840  265823765

De eerste kolom, dat is de index (of eigenlijk alle mogelijke indexen) die ik heb. Het tweede getal, die verwijst naar de offset in FILE2.

Ik krijg de index binnen. Die moet ik opzoeken in FILE1. Vervolgens lees ik de hele regel in, en weet ik dus de offset. Dan moet ik in FILE2 naar die offset gaan.

De vraag is dus eigenlijk, hoe ga ik snel naar een bepaalde regel in een tekstfile?

[Verwijderd]

Gebruik TFileStream. Met Seek kun je de file pointer positioneren.

Probleem is dus om op een willekeurige positie in de file de index en de regel te identificeren. Ik neem aan dat de regels verschillende lengtes hebben, anders was het wel erg makkelijk. Je geeft geen info hoe zo'n index/regel eruit ziet, dus daar kan ik je niet helpen.
[edit]
Ah, meer info, moet nu wel lukken, denk ik

[Verwijderd]

Op dinsdag 09 juli 2002 22:17 schreef TheLunatic het volgende:
Ik krijg de index binnen. Die moet ik opzoeken in FILE1. Vervolgens lees ik de hele regel in, en weet ik dus de offset. Dan moet ik in FILE2 naar die offset gaan.

De vraag is dus eigenlijk, hoe ga ik snel naar een bepaalde regel in een tekstfile?

Ervan uitgaand dat je de file benadert via een Windows file handle (een stuk sneller dan de standaard Pascal file routines van Delphi), hier een stukje code uit m'n LargeIniFile unit (zit in aangepaste vorm ook in de IniFiles unit van de FPC compiler):

code:

const
  MAXLINELENGTH = 255;
  FILEBEGIN = 0;
  CURRENTPOS = 1;
  FILEEND = 2;
  EOL = #$0D#$0A;

function TLargeIniFile.GetLine(const iPos: integer): string;
var
  iRead: integer;
  Buffer: PChar;
  sTemp: string;
begin
  Result := '';
  Buffer := PChar(AllocMem(MAXLINELENGTH+length(EOL)));
  try
    FileSeek(FHandle, iPos, FILEBEGIN);
    iRead := FileRead(FHandle, Buffer^, MAXLINELENGTH+length(EOL));
    sTemp := string(Buffer);
    Result := Trim(Copy(sTemp, 1, Pos(EOL, copy(sTemp, 1, iRead))-1));
  finally
    FreeMem(Buffer);
  end;
end;

Nog niet getest met 6 miljoen records (zoiets wil je niet in een tekstfile onderhouden), maar wel met enkele 10-duizenden records, en dan blijft 'ie akelig snel.

[elevator]

Op dinsdag 09 juli 2002 22:17 schreef TheLunatic het volgende:
De vraag is dus eigenlijk, hoe ga ik snel naar een bepaalde regel in een tekstfile?

vroeger deden we dat zo:
(code uit SWAG)

code:

procedure TextSeek(Var f : Text; n : LongInt);
var SaveMode,
    SaveRecSize : Word;
    Temp_F  : File ABSOLUTE F;
begin
 SaveMode := FileRec((@F)^).Mode;
 SaveRecSize := FileRec((@F)^).RecSize;

 FileRec((@F)^).Mode:=fmInOut;                 { Set to binary mode }
      { (The (@F)^ part is to let TP 'forget' the type of the structure, so }
    { you can type-caste it to everything (note that with and without (@X)^ }
     { can give a different value, longint(bytevar) gives the same value as }
                { bytevar, while longint((@bytevar)^) gives the same as }
       { longint absolute Bytevar (i.e. all 4 bytes in a longint are readed }
                    { from memory instead of 3 filled with zeros))) }

  FileRec((@F)^).RecSize := 01;        { Set record size to 1 (a byte) }
  {$i-}
    Seek(File((@F)^), N);
  {$i-}

 TextRec(F).Mode := SaveMode;                { Set back to text mode }
 TextRec(F).BufSize:= SaveRecSize;       { BufSize overwritten by RecSize }
 TextRec(F).BufEnd := TextRec(F).BufPos;
end; { func. TextSeek }

maar de code die Afterlife post is wat gemakkelijker te gebruiken.

[TheLunatic]

Mhhh hier ga ik s ff mee aan de gang...


Als iemand zich verveelt, kan die gene mij dan ook misschien wat meer inzicht geven over hoe ik op moet gaan met een FileStream? Ik bedoel, bijvoorbeeld hoe de cursor naar het begin van een regel gaat, en hoe ik data uit de filestream haal enzo? De help geeft hierin niet veel inzicht, zitten ook geen examples bij enzo

[LordLarry]

Op woensdag 10 juli 2002 14:38 schreef TheLunatic het volgende:
Als iemand zich verveelt, kan die gene mij dan ook misschien wat meer inzicht geven over hoe ik op moet gaan met een FileStream? Ik bedoel, bijvoorbeeld hoe de cursor naar het begin van een regel gaat, en hoe ik data uit de filestream haal enzo? De help geeft hierin niet veel inzicht, zitten ook geen examples bij enzo

TFileStream is een letter stroom, het houdt geen rekening met woorden en/of zinnen. Je kan dus nooit opdracht geven om naar het begin van een zin te gaan. Wel naar het begin van het bestand. TStringStream kan dat wel, maar deze is weer geen file stream en heeft dus ook geen direct nut voor jouw. Alleen als je het file eerst helemaal inleest.

Ik kan me vaag herinneren dat er een TStringFileStream bestaad, maar dat moet je maar even googlen ofzo.

Ik denk dat je bij een tekst file weinig kan optimaliseren als de lengte van de strings op een regel geen vaste lengte hebben. Misschien kan je er beter een tabel van maken. Misschien met een eenmalige conversie programma om het van tekst naar de tabel omzetten.

[Sponz]

code:

var f : file of byte;
...
assign(f,'filenaam.ext');
reset(f);

Niet echt Delphi, maar misschien heb je er wat aan.

[Verwijderd]

Je zegt dat je een tekstfile hebt van +/- 6 miljoen regels, dat kan toch nooit efficient zijn. Maak een programma die het bestand opsplits ofzo. Maak er 10 duizend bestanden van met duidelijke bestandsnamen zoals: '0543516825-0543517825.txt'
Dan kan je het bestand zoeken waar de index in zou moeten staan, die in 1 keer in je geheugen dumpen en vervolgens (super snel) in gaan zoeken.

Wat lastiger misschien als er ook aan toe gevoegd moet worden, maar dat is sowiezo lastig.

[TheLunatic]

Weet je wat het is, ik heb een ander programmatje (zonder source), die het ook doet ! En echt in n halve seconde ofzo elk record gevonden. Dus het kan wel. Dit in reactie op Unteraarsch.

[Gerco]

Die binary search kun je wel zo doen:

code:

Seek(helft van de file in bytes)
Loop
  Zoek eerstvolgende newline
  Bekijk nummer, 
    nummer goed?    klaar
    nummer te laag? Seek(3/4e van de file in bytes)
    nummer te hoog? Seek(1/4e van de file in bytes)
Ga naar loop

Je moet gewoon het midden van de file in bytes nemen (dat zal grofweg het midden van de file in regels zijn, al ligt het er wel een paar honderd/duizend vanaf, da's niet erg. Dan zoek je dus de eerstvolgende newline en vergelijk je de regel die je dan gevonden hebt met wat je zoekt.. herhaal indien nodig.

Maar een vaste regellengte is een stuk beter, dan kun je gelijk naar elke willekeurige regel Seek() 'en

[TheLunatic]

Ik denk dat ik dan toch maar ff ga zorgen dat alle regels even lang zijn, door ze simpelweg aan te vullen met spaties ofzo... Dan moet het inderdaad wel aardig te doen zijn lijkt me ja ! Als er iemand nog tips heeft.....

[elevator]

Op woensdag 10 juli 2002 18:32 schreef TheLunatic het volgende:
Ik denk dat ik dan toch maar ff ga zorgen dat alle regels even lang zijn, door ze simpelweg aan te vullen met spaties ofzo... Dan moet het inderdaad wel aardig te doen zijn lijkt me ja ! Als er iemand nog tips heeft.....

Is het een probleem om zelf (eenmalig) index te genereren (eventueel filestamp in die idx zodat je automatisch kan rebuilden) ?

Je hebt een index zeg je, maar die gebruik je niet. Ik snap het probleem niet precies hoor. Als je een index genereert met file offsets, en je slaat vervolgens in die index de file offset op, dan ben je er toch?

[TheLunatic]

Klopt, het probleem is meer dat ik niet weet hoe ik dat moet verwerken in een programma. Zo weet ik niet hoe ik aan het begin van een regel kom als ik FileStream gebruik, en nog meer van dergelijke handelingen waar ik al eerder overgesproken heb.

Ik heb nu de code van Elevator (hee dat ben jij ! ) gebruikt, en ik moet zeggen dat ziet er goed uit. Als ik nu nog zorg dat de index-file goed er uit ziet (zitten nu tabs in enzo), dan moet het denk ik lukken.

Dus bij deze bedankt voor je stukkie code !

[Verwijderd]

Voor de gein heb ik een stukje van jouw code gemaakt, je moet maar kijken of je er wat aan hebt:

Een procedure om van een bepaalde index de regel in te lezen:

code:

function TSearch.LeesRegel(const Index: Integer; var S: string): Boolean;
var
  Offset: Integer;
begin
  Result := FindIndex(Index, Offset);
  if not Result then
    Exit;

  Result := LeesRegelOffset(Offset, S);
end;

FindIndex zoekt de index dus op in de index-bestand en geeft een offset terug.

LeesRegelOffset zoekt de offset op in het grote bestand en geeft een regel terug.

FindIndex heb ik met een binairy-search geimplementeerd:

code:

function TSearch.FindIndex(const Index: Integer; var OffSet: Integer): Boolean;
var
  Lower, Upper, Mid: Integer;
  MidIndex, MidOffset: Integer;
begin
  Lower := 0;

  if IndexCount = 0 then
  begin
    Result := False;
    Exit;
  end;

  { Binary search }
  Upper := IndexCount;
  while Lower + 1 <> Upper do
  begin
    Mid := (Lower + Upper) div 2;
    ReadIndexRegel(Mid, MidIndex, MidOffset);
    if MidIndex > Index then
    Upper := Mid
    else if MidIndex < Index then
    Lower := Mid
    else
    begin
    Result := True;
    Offset := MidOffset;
    Exit;
    end;
  end;
  ReadIndexRegel(Lower, MidIndex, MidOffset);
  Result := MidIndex = Index;
  if Result then
    Offset := MidOffset;
end;

IndexCount is een property die het aantal indexen in de index-bestand geeft.

ReadIndexRegel leest een index-regel [index + offset] uit het index-bestand.

code:

type
  { Ik ga er maar effe vanuit dat elke regel er hetzelfde 
    uitziet, 10 cijfers, een tab [ofzo] 10 cijfers en een
    CR + LF }
  TRegel = packed record
    RIndex: array[0..9] of Char;
    RSpace: array[0..0] of Char;
    ROffset: array[0..9] of Char;
    RCRLF: array[0..1] of Char;
  end;

function TSearch.ReadIndexRegel(const ID: Integer; var Index,
  Offset: Integer): Boolean;
var
  Regel: TRegel;
  ReadCount: Integer;
begin
  { Waarschijnlijk niet zo efficient om steeds vanaf het
    begin te kijken, mag je zelf een oplossing voor vinden
    :) }
  FFileStream.Seek(SizeOf(Regel) * ID, soBeginning);
  ReadCount := FFileStream.Read(Regel, SizeOf(Regel));
  Result := ReadCount = SizeOf(Regel);
  if Result then
    with Regel do
    begin
    Index := StrToIntDef(RIndex, -1);
    Offset := StrToIntDef(ROffset, -1);
    Result := (Index >= 0) and (Offset >= 0);
    end;
end;

LeesRegelOffset mag je zelf implementeren

[TheLunatic]

Wow da's wel een hele berg code zo ineens... thanks !


Kan iemand me ook ff uitleggen hoe ik om moet gaan met TFileStream.Read of TFileStream.ReadBuffer ?? Ik krijg daar steeds een AccessViolation

[LordLarry]

Kan iemand me ook ff uitleggen hoe ik om moet gaan met TFileStream.Read of TFileStream.ReadBuffer ?? Ik krijg daar steeds een AccessViolation

Ik neem aan dat je eerst

MijnBestand := TFileStream.Create(blablabla);

gedaan hebt. Het klinkt alsof je dat niet gedaan hebt.

Maar voor strings is een TFileStream niet echt het makkelijkst te gebruiken hoor...

[TheLunatic]

Ik heb em wel gecreerd ja, dat zeker. Maar het gaat er me ook niet omdat ie voor strings is, ik wil gewoon een x aantal karakters kopieren uit die file naar een string.

[Killemov]

1 - Ik zou proberen zoveel mogelijk van je index in het geheugen opslaan. (Waar zoek je eigenlijk op met die enorme key ?)
2 - Je kan natuurlijk ook een index op je index maken! (= B-tree)
3 - Je gaat eens nadenken over professionaliseren en de boel in een dbms stoppen.

[TheLunatic]

Op zich zijn alle problemen nu verholpen, dus een DBMS lijkt me niet meer nodig. Het enige probleem wat er nog is, is dat ik niet weet hoe ik informatie uitlees uit een FileStream. Als iemand me dat eens vertelt, dan ben ik uit de problemen !!

Concreet de vraag dus : Hoe haal ik informatie (tekst, strings, integers, characters of wat dan ook) uit een FileStream ? Liefst een voorbeeldje erbij!

[Tomatoman]

Het zoeken duurt zo lang, omdat je iedere keer die hele file vanaf het begin moet doorzoeken. Daar komt nog bij dat de file eigenlijk te groot is om in het geheugen te proppen.

Daarom zou je eigenlijk het bestand in brokken willen knippen. Bijvoorbeeld brokken van ongeveer een megabyte. Met een (trage) zoekactie zou je eenmalig de volgende tabel kunnen maken:

code:

Index    Positie (decimaal)
========    ==================
01234567    1.000.005       (ongeveer de eerste megabyte)
09023453    2.000.012       (weer ongeveer een megabyte)
17213432    3.000.002
26243034    4.000.007
...    ...           enzovoort

Stel dat je nu index 10694400 zoekt. Deze index moet zich ergens in de tweede megabyte bevinden. Nu hoef je alleen nog maar naar die index te zoeken van positie 3.000.002 tot 4.000.007. Met een beetje geschikte opdeling kun je het zoeken zo behoorlijk versnellen.

Het gedeelte dat effectief in het geheugen wordt geladen, kun je beperken door een memory mapped file te gebruiken en daarin te zoeken. Een memory mapped file geeft je de mogelijkheid om een gedeelte van een bestand op schijf in het geheugen te plaatsen, dus het hoeft niet het gehele bestand te zijn.

Met die opdeling in brokken (bijvoorbeeld wanneer je programma start) en het gebruik van memory mapped files kun je enorm veel tijd winnen.
1. Je doorzoekt veel minder tekst.
2. Een blok van 1 MB past best in het RAM-geheugen, terwijl een bestand van 60 MB waarschijnlijk een hoop swapping naar je harddisk (traaaagggg) zal veroorzaken.

[LordLarry]

Op donderdag 11 juli 2002 17:27 schreef TheLunatic het volgende:
Concreet de vraag dus : Hoe haal ik informatie (tekst, strings, integers, characters of wat dan ook) uit een FileStream ? Liefst een voorbeeldje erbij!

Start een nieuwe thread zou ik zeggen. En zet er dan meteen even wat code bij hoe je the TFileStream nu gebruikt, want zo moeilijk kan het niet zijn. Je hebt waarschijnlijk gewoon ergens een foutje gemaakt waardoor je die access violation krijgt.

[D2k]

je wil wel heel veel met voorbeeldjes he? wat dacht je ervan de gekregen code eens goed te bestuderen en dan zelf eerst eens iets te proberen. Dan kan je met eventuele vragen altijd nog trugkomen