Wie verwalte ich so viele Daten?

[Neutral General]

Hi,

Ich würde gerne eine Datei nach 4-Byte-Folgen durchsuchen und diese Zählen. Also z.B. wie oft kommt

$25$75$DA$2F

in Datei.xyz vor. Nur das ich nicht nur 1 4-Byte-Folge zählen will, sondern alle von $00000000 bis $FFFFFFFF...

Also bräuchte ich theretisch sowas wie:
Zaehlarray: Array[0..High(Cardinal)] of Word; Aber das sprengt ja alle Rahmen...

Wie mache ich sowas am besten?

Gruß
Neutral General

[Medium]

Ein Großteil wird ja garnicht vorkommen. Also nimm statt eines Arrays eine Liste, und füge jede Folge die du neu findest in diese ein. Findest du diese öfter, dann einen Zähler jeweils mit erhöhen.

[Neutral General]

Ja dachte ich mir auch schon aber das nachgucken, ob eine Folge schon in der Liste ist, dass dauert ja auch ne Weile... Wird das nicht irgendwann zu aufwendig (CPU)?

[marabu]

Hallo,

wenn die Liste sortiert ist, dann kannst du mittels binärer Suche sehr effizient zugreifen.

Übrigens hat ein Word nur zwei Byte ...

Grüße vom marabu

[Neutral General]

Zitat von marabu:

Hallo,

wenn die Liste sortiert ist, dann kannst du mittels binärer Suche sehr effizient zugreifen.

Übrigens hat ein Word nur zwei Byte ...

Grüße vom marabu

Zu der binären Suche müsste ich mich mal informieren... Das ein Word 2 Byte groß ist, wusste ich.

Das ganze sollte ja ungefähr so laufen (theorie)

Delphi-Quellcode:

var Arr: Array[0..High(Cardinal)] of Word;
    buf: Cardinal;
begin
stream.LoadFromFile(datei);
stream.Read(buf,4);
inc(Arr[buf]);

Gruß
Neutral General

[Apollonius]

Wenn du das nicht mit MMFs machst, bist du verloren.

[Neutral General]

Und was sind MMFs ? Mapped Files?

Und wenn ja - wie benutze ich die?

[Die Muhkuh]

Memory Mapped Files

[marabu]

Hi Michael,

mit zwei Byte zählst du nur bis 64K - das könnte in einigen Fällen zu wenig sein.

Dein statisches Array würde in jedem Fall 2^34 Byte (16GB) belegen. Mit einem entsprechenden Server unter 64bit Windows kein Problem - ich beneide dich um deine HW Austattung.

Nimm eine TList und erweitere sie um die binäre Suche - besser ist dass.

Freundliche Grüße

[alzaimar]

Ich würde sogar noch weiter gehen, und eine Hashmap verwenden. Hier ist eine.

Eine binäre Suche dauert doch etwas, wenn auch nicht viel, aber der Suchaufwand nimmt mit der Größe der Liste doch zu. Das passiert bei einer Hashmap nicht. Die Hashmap wächst dynamisch.

Bei der o.g. Hashmap (TIntegerDictionary) wird zu jedem 4-Byte Schlüssel eine Nutzerinformation (Pointer) gespeichert. So würde die Zählfunktion aussehen:

Delphi-Quellcode:

Procedure Count (aDict : TIntegerDictionary; aCardinal : TCardinal);
Var
  cnt : PInteger;

Begin
  If aDict.Find (aCardinal, Cnt) Then // Wenn schon in der dictionary
    Cnt^ := Cnt^ + 1                  // ... Zähler erhöhen
  Else Begin
    new (Cnt);                        // Ansonsten neuen Zähler anlegen
    Cnt^:= 1;                         // Initalisieren
    aDict.Add (aCardinal, Cnt);       // und ab in die dictionary
  End
End;

Das geht -wie schon erwähnt- sehr schnell, schneller gehts eigentlich nicht (ok, eine Skiplistei ist marginal schneller, wenn sie nicht zu groß wird).

Klitzekleiner Pferdefuß: Die Ergebnisse sind unsortiert, du musst sie am Schluss auslesen, in eine Liste packen und diese dann sortieren, aber das hättest Du bei einer Liste ja auch.