TObjectlst - Index eines Objektes finden

[scrat1979]

Folgendes Problem: Ich möchte in einer TObjectList mehrere GLEICHARTIGE Objekte verwalten. Sagen wir mal, die Objekte haben z.B. alle eine "property ID : Integer...". Nun möchte ich beispielsweise den Index in der ObjectList von demjenigen Objekt herausfinden, welches die ID 37 hat. Eine entsprechende Methode habe ich leider nicht finden können, IMHO bleibt nur noch übrig, die ObjectList mittels Schleife zu durchlaufen und jedes Objekt auf die Eigenschaft ID=37 prüfen. Bei einem Treffer wäre der aktuelle Zähler der Index. Gibt es hierfür eine einfachere Lösung?

SCRaT

[himitsu]

Zitat:

Zitat von scrat1979

IMHO bleibt nur noch übrig, die ObjectList mittels Schleife zu durchlaufen und jedes Objekt auf die Eigenschaft ID=37 prüfen. Bei einem Treffer wäre der aktuelle Zähler der Index. Gibt es hierfür eine einfachere Lösung?

Nee, das is so schon der gängige Lösungsweg.

Nur wenn die Objekte nach ihren IDs sortiert sind, dann könnte man die Suche noch optimieren.

[scrat1979]

Danke!! Wollte nur nicht das Rad neu erfinden :) Dann mach ich es wohl so...

[Hawkeye219]

Hallo Michael,

du könntest auch eine TStringList nehmen und dort zu den Objekten die ID als String hinterlegen. Die Suche über IndexOf() sollte speziell bei einer größeren Anzahl von Objekten relativ schnell gehen, sofern die Stringliste sortiert ist. Bei neueren Delphi-Versionen verfügt die Stringliste übrigens auch über die Eigenschaft OwnsObjects und kann somit die enthaltenen Objekte freigeben.

Abhängig von der Anzahl der Objekte lohnt der Aufwand eventuell gar nicht, und du bist mit einer einfachen Suchschleife schneller.

Gruß Hawkeye

[scrat1979]

Das habe ich auch im Sinn gehabt, muss mal schauen, welche von beiden Lösungen in meinem Fall am praktikabelsten ist. Danke trotzdem für den Tip! :cheers:

[Panthrax]

Warum nicht die Vorteile von Delphi 2010 nutzen, wenn es schon verfügbar ist. (Geht grundsätzlich auch ohne Generika.)

Delphi-Quellcode:

program Project1;

{$AppType Console}

uses
  SysUtils,
  Generics.Collections,
  Generics.Defaults;

type
  TMyObject = class
    strict private
    FValue: Integer;

    public
    property Value: Integer read FValue write FValue;
  end;

  TMyComparer = class(TComparer<TMyObject>, IComparer<TMyObject>)
    function Compare(const Left, Right: TMyObject): Integer;
  end;

  TMyObjectList = class(TObjectList<TMyObject>)
    public
    constructor Create;
    function IndexOfValue(const Value: Integer): Integer;
  end;

{ TMyComparer }

function TMyComparer.Compare(const Left, Right: TMyObject): Integer;
begin
  Result := Left.Value - Right.Value;
end;

{ TMyObjectList }

constructor TMyObjectList.Create;
begin
  inherited Create(TMyComparer.Create);
end;

function TMyObjectList.IndexOfValue(const Value: Integer): Integer;
var
  Temp: TMyObject;
begin
  Temp := TMyObject.Create;
  try
    Temp.Value := Value;
    Result := IndexOf(Temp);
  finally
    Temp.Free;
  end;
end;

{ Hauptprogramm }

var
  MyObjectList: TMyObjectList;
  MyObject: TMyObject;
  Index: Integer;
begin
  try
    MyObjectList := TMyObjectList.Create;
    try
      for Index := 9 downto 0 do
      begin
        MyObject := TMyObject.Create;
        MyObject.Value := Index;
        MyObjectList.Add(MyObject);
      end;

      for Index := -1 to 10 do
        WriteLn(Format(
          'MyObjectList.IndexOfValue(%3d) = %3d',
          [Index, MyObjectList.IndexOfValue(Index)]
        ));

      ReadLn;
    finally
      MyObjectList.Free;
    end;
  except
    on E: Exception do
      WriteLn(E.ClassName, ': ', E.Message);
  end;
end.

Code:

MyObjectList.IndexOfValue( -1) =  -1
MyObjectList.IndexOfValue(  0) =   9
MyObjectList.IndexOfValue(  1) =   8
MyObjectList.IndexOfValue(  2) =   7
MyObjectList.IndexOfValue(  3) =   6
MyObjectList.IndexOfValue(  4) =   5
MyObjectList.IndexOfValue(  5) =   4
MyObjectList.IndexOfValue(  6) =   3
MyObjectList.IndexOfValue(  7) =   2
MyObjectList.IndexOfValue(  8) =   1
MyObjectList.IndexOfValue(  9) =   0
MyObjectList.IndexOfValue( 10) =  -1

[scrat1979]

Habe zwar noch nie mit Generics zu tun gehabt, werde ich mir aber auf jeden Fall mal anschauen!!!!

Danke für den Code!!!

SCRaT

[alzaimar]

Zitat:

Zitat von himitsu

Nur wenn die Objekte nach ihren IDs sortiert sind, dann könnte man die Suche noch optimieren.

Nö, einfach die IDs in eine Hashmap und die Referenz als Nutzdaten: Wupps, ist man optimal schnell.

[himitsu]

Zitat:

Zitat von alzaimar

Nö, einfach die IDs in eine Hashmap und die Referenz als Nutzdaten: Wupps, ist man optimal schnell.

Dann muß doch aber dennoch die ganze Map durchsucht werden?
Es sei denn man sortiert diese Map, bzw. bereitet sie aufandere Weise, zu besseren Suche, auf.

Aber die Suche nach Integer oder Hash ist doch eigentlich keinen großen Unterschied? :gruebel:

[alzaimar]

Zitat:

Zitat von himitsu

Dann muß doch aber dennoch die ganze Map durchsucht werden?

Auch wieder 'nö'. Suchen in einer Hashmap geht in O(1). :zwinker:

Ich glaub, hier ist auch eine 'Integer-Hashmap' dabei. Da kannst Du dir mal anschauen, wie das geht.

[himitsu]

Zitat:

Function TIntegerDictionary.FindHash(aKey: Cardinal; Out h: Cardinal): Pointer;

Delphi-Quellcode:

Begin
  h := HashFromInt(aKey) Mod fHashMod;
  Result := fHashList[h];
  While PIntHashEntry(Result) <> Nil Do
    With PIntHashEntry(Result)^ Do
      If heKey = aKey Then
        Exit
      Else
        Result := heNext;

End;

Da wird also ein Hash von dem Integer gemacht und dann wird einie Liste durchsucht.

Wenn man den Integer nun direkt sucht, dann könnte man sich das Haschen sparen und müßte ebenfalls eine Liste durchgehn.

OK, hier würde man dann im schlimmsten Fall die komplette Liste durchgehn und bei der Map nur einen Teil.
Bei einer sortierten Liste würde man aber auch nur einen Teil der Liste durchgehn müssen.
(bei 1000 Einträgen in 'ner sortierten Liste wären auch nur maximal 10 Vergleiche nötig ... was etwa 'ner Hashmap mit fHashMod=100 entsprechen würde)

Oder seh ich das falsch?

[edit=mkinzler]Delphi-Tag eingefügt Mfg, mkinzler[/edit]

[Khabarakh]

Das mit O(1) darfst du alzaimar ruhig glauben ;) .
Fakt ist: Eine Hashmap benötigt O(n) zum Aufbau und O(1) zum Lookup, dagegen kann eine sortierte Liste mit O(n log n) und O(log n) nicht anstinken.

[himitsu]

Tut mir Leid, aber da ist eine Schleife drin, also kann das O(1) nicht stimmen.

Gut, die Speicherzugriffe zwischen dem Record (Value=Recordpointer-Offset) und Array+Property (Array-Referenz+Property-Zugriff) mag schneller sein, also würde es im idealfall eher so aussehn

Θarray(n) = Θmap(n / fHashMod) / x
> x wäre jetzt der Unterschied zwischen den beiden Zugriffen

Wenn jetzt fHashList[h] direkt den EINEN gesuchten Wert liefern würde, dann täte vielleicht Θ(1) rauskommen.

[Khabarakh]

Zitat:

Zitat von himitsu

Tut mir Leid, aber da ist eine Schleife drin, also kann das O(1) nicht stimmen.

Im Worst Case, ja, aber im Durchschnitt interessiert dann doch eher der durchschnittliche Fall :zwinker: . Und da gilt die angegebene Formel, die in der Quellenangabe auch hergeleitet wird (so viel Wahrscheinlichkeitsrechnung, argh :mrgreen: ).

Zitat:

Zitat von himitsu

Θarray(n) = Θmap(n / fHashMod) / x

Wenn du Vorfaktoren vergleichen willst, ist asymptotische Laufzeit definitiv das falsche Werkzeug ;) .