Assoziative Array in FPC ?

[pluto]

Hallo,
für ein Projekt, brauche ich unbedingt Assoziative. Alles was ich dazu bisher gefunden habe, basiert auf schleifen. Die sind jedoch für mich zu langsam.
Zum Problem:
Ich habe genau 15 Objekt Listen. Dort speichere ich ein bestimmen eigenen Typ ab. z.b. TPLTestItem.
Alle Einträge haben unter anderem eine ID. Die ist einmalig.

Nun habe ich verschiedene ID-Listen. Wo nur die id's drin stehen. z.b. pl01, pl02, pl03.
Davon habe ich sehr sehr sehr viele. Zu viele um per Schleife ständig in meinen 15 Listen zu suchen.
Ich dachte an Pointer. Aber ich weiß noch nicht genau wie das gehen soll.

mit Property hätte ich ja schon mal einen string ähnlichen zugrieff:

Code: Alles auswählen

TMyClass ....
property StringItem[const aString:String] read GetStr write SetStr.
 
procedure TMyClass.GetStr(const aText:String)
begin
  //....
end;

Über StringItem kann jetzt z.b. so zugegriffen werden:
writeln(StringItem['pl01']);

Problem ist hier, in GetStr und SetStr müsste ich über eine schleife jeweils die passende Index Nummer finden. Aber das währe mir zu langsam.
Ich hoffe ihr könnt das Problem nach vollziehen. Gibt es dafür eine Möglichkeit ? Eventuell könnte ich auch die Index Nummer berechnen. Allerdings sind die Objekte nicht immer gleich groß. Besitzen aber immer die gleichen Variablen.

Ich weiß das Delphi keine "echten" Assoziative wie in PHP, Perl unterstützen. Ich glaube fast ohne eine schleife ist sowas nicht möglich.

[Hitman]

Was du wohl meinst, sind HashListen ...

uses contnrs .... TFPHash(Object)List

[pluto]

ich habe mir die entsprechenden Klassen angeschaut, sie basieren ebenfalls auf Schleifen. Wenn ich es richtig verstanden. habe. Die Liste kann man leider nicht mit einem direkten array ansprechen.
Mir ist noch eine andere Lösung eingefallen(teilweise): Ich könnte eine art Pointer Liste erzeugen, wo alle Objekte drin sind. Das sind nur pointer. Ich muss nicht wissen wo sich das Objekt befindet, ich brauche nur das eigentliche Objekte. Währe es möglich wenn die Struktur in etwa so aussehen würde, direkt über ein Pointer zu einen Eintrag zu springen, ohne eine schleife zu nutzen ?
Hier das Schema:
Es gibt 15 Objekt Listen. Hier werden die "Echten" Objekte gespeichert, jetzt gibt es eine weitere Listen, wo alle Einträge in folgender Form gespeichert werden:
ID:DataObjekt
Jetzt könnte müsste ich nur noch ein Pointer nutzen um zum gewünschten Dataobjekt zu springen, ohne eine schleife zu nutzen, und ich könnte prüfen ob es die ID schon gibt oder nicht.
Die Frage ist also, wie sieht das aus ? Das währe praktisch so eine art Tabelle. Es hat seinen Grund, warum ich einmal 15 Objekt Listen habe und dann noch eine weitere brauche. Wie gesagt, das Projekt nutzt sehr ausgiebig schon jetzt Pointer.

uses contnrs .... TFPHash(Object)List

Ich werde mir die Klassen etwas genauer ansehen, Eventuell habe ich was übersehen.

Edit01
Die meisten Methoden nutzen diese Funktion. Hier wird eine while schleife verwendet und zwar eine Endlos schleife. Die so lange läuft bis fünft ausdrücke erfüllt sind.
Verstehe ich diese Funktion Falsch ? Tatsache ist jedoch das sie überall verwendet wird. Wen ich es richtig verstehe sind diese HashListen mit Doppelt Verketten Listen vergleichbar.....

Code: Alles auswählen

function TFPHashList.InternalFind(AHash:LongWord;const AName:shortstring;out PrevIndex:Integer):Integer;
var
  HashIndex : Integer;
  Len,
  LastChar  : Char;
begin
  HashIndex:=AHash mod LongWord(FHashCapacity);
  Result:=FHashTable^[HashIndex];
  Len:=Char(Length(AName));
  LastChar:=AName[Byte(Len)];
  PrevIndex:=-1;
  while Result<>-1 do
    begin
      with FHashList^[Result] do
        begin
          if assigned(Data) and
             (HashValue=AHash) and
             (Len=FStrs[StrIndex]) and
             (LastChar=FStrs[StrIndex+Byte(Len)]) and
             (AName=PShortString(@FStrs[StrIndex])^) then
            exit;
          PrevIndex:=Result;
          Result:=NextIndex;
        end;
    end;
end;

[Hitman]

1. TObjects sind Pointer ... wenn du direkt Pointer verwenden kannst, ohne einen Lookup durchführen zu müssen, wo ist dann das Problem? Deiner Ausführung nach schließe ich aber, dass es ohne Lookup nicht geht ...

2. Wie genau denkst du denn, dass intern assoziative Arrays funktionieren? Magie? Natürlich kommen dort ebenfalls Schleifen zum Einsatz. Die Kunst ist doch, die Datenstruktur so zu wählen, dass du eben nicht ständig mit O(n) oder noch schlimmer drüber iterierst. Schau dir vlt. lieber erstmal an, was assoziative Arrays überhaupt sind ... http://en.wikipedia.org/wiki/Associative_array
In dem Zusammenhang kannst du dann auch gleich nachlesen, was Hash Lists und Hash Tables sind Dann siehst du vlt. auch ein, dass das ziemlich genau das ist, was du willst.

[mschnell]

für ein Projekt, brauche ich unbedingt Assoziative. Alles was ich dazu bisher gefunden habe, basiert auf schleifen. Die sind jedoch für mich zu langsam.

Da der Rechner keine Hardware für per Programm benutzbaren Assoziativ-speicher hat, basiert jede Software, die Assoziativ-Speicher realisiert auf Schleifen. Und wenn Du keine siehst, basieren die Systemroutinen auch auf Schleifen (z.B. bei einer Array-Property mit String als Index oder TList.IndexOf).

Da kannst Du gar nichts machen, außer eine Hardware-Kiste zusammenlöten

Natürlich kann man die Software optimieren (64-Bit Modus, Loop enrolling, Assembler, ...)

Hashen funktioniert (beispielsweise) so:

Der assoziative Index eines Arrays ist z.B. ein 100 Byte großer Wert (also 2**800 Ausprägungen). Du weißt, dass es nicht mehr (für gute Performance: deutlich weniger als) als 100 Einträge geben kann.

Nun rechnest Du über eine "Hash-Funktion" aus dem Index einen Wert mit weniger Ausprägungen aus. Beispielsweise die Summe der 100 Bytes modulo 100: 100 verschiedene Auspürägungen.

Du verwaltest jetzt zusätzlich ein Array mit einem Integer Index mit 100 Einträgen, Jedes Element ist ein Pointer auf einen Datensatz im ursprünglichen Array (oder NIL).

Ein Eintrag in das Array kommt so zustande:
- Zuerst is alles NIL
- ein neuer Eintrag kommt an die Stelle die die Hash-Funktion errechnet
- ist diese Stelle bereits belegt wird nach einem festen Algorithmus eine beliebige andere leere Stelle gesucht, (z.B. einfach vorwärts suchen, am Ende wieder bei 0 beginnen)

Das Auffinden eines Elements ist dann natürlich so:
- Mit der Hash-Funktion den Hash-Index ausrechnen.
- Wenn das Element das in der Hash-Tabelle referenziert wird den richtigen 100 Byte Index hat, sind wir Fertig,
- ansonsten (auch bei NIL, das Konkurrenz-Element könnte ja gelöscht sein) nach dem Fortschreite-Algorithmus) weiter suchen, bis das richtige Element gefunden ist.

Offensichtlich geht die Performance rapide in den Keller, wenn die Hash-Tabelle voll wird, oder wenn viele Lösch-Vorgänge passiert sind. (Letzteres kann ein Neu-Erstellen der Hash-Tabelle beheben).

-Michael

[pluto]

Offensichtlich geht die Performance rapide in den Keller, wenn die Hash-Tabelle voll wird, oder wenn viele Lösch-Vorgänge passiert sind. (Letzteres kann ein Neu-Erstellen der Hash-Tabelle beheben).

Der Vorteil bei mir währe, ich muss gar nicht löschen.

@Hitman
Eventuell habe ihr nicht ganz unrecht. Z.B. könnte ich die Liste ja auch Sortieren. Das währe eine kleine Optimierung.
Ich dachte halt, das ich um die Verwendung von Schleifen umher komme. Den Link kannte ich schon, allerdings nur den Deutschen. Ihr meint, in allen sprachen, wird in diesen Fall eine schleife verwendet ?

[mschnell]

Eventuell habe ihr nicht ganz unrecht. Z.B. könnte ich die Liste ja auch Sortieren. Das währe eine kleine Optimierung.

Sortieren wäre ein Riesige Optimierung ! (Suchzeit proportional zu log(n) statt zu n). Dann werden die Elemente mit binärer Suche statt linearer Suche gefunden.

TList macht das automatisch, da berauchst Du außer der Vergleichsfunktion, welches Element als "größer" angesehen wird, nix programmieren.

--Michael

[pluto]

TList macht das automatisch, da berauchst Du außer der Vergleichsfunktion, welches Element als "größer" angesehen wird, nix programmieren.

Der größte Nachteil hier, ist halt, dass das erstellen von solchen listen mehr zeit in Anspruch nimmt. Aber ich glaube das würde sich lohnen.
Bisher basiert alles auf TObjectList. Ich werde verschiedene Tests machen mit der TList und mit der "Hash Tabelle". Ich denke, erst dann könnte ich sagen, welche Liste schneller ist und für mich besser geeignet ist.

Erstmal danke für die Tipps, weil vor diesem Probleme stehe ich bald in meinem Projekt.

[mschnell]

Da TObjectList eine TList ist, kann man sie natürlich auch sortieren

Vermutlich kann man Haschen und sortieren auch irgendwie kombinieren.

Und dann gibt es da auch noch balancierte Binär-Bäume....

-Micheal

[pluto]

Und dann gibt es da auch noch balancierte Binär-Bäume....

Ich habe mir bei Wikipedia einiges dazu durchgelesen, sogar mehrmals, aber ich verstehe das noch nicht so ganz. ist halt ein neues Gebiet für mich mit so großen Daten Mengen um zu gehen.

Zum Projekt:
http://www.pluto.lazarusforum.de/dokuwi ... lonkeditor
da habe ich versucht das Projekt einigermaßen gut zu beschreiben, und die Probleme. Eventuell fällt euch ja noch eine andere Lösung ein. Ganz Aktuell ist die seite auch nicht, bietet aber eine gute Übersicht. Glaube ich.