Entwickler-Ecke :: Thema anzeigen - Ähnliche Objekte in TObjectList verhindern?

sunnyandy - Do 04.10.07 13:09
Titel: Ähnliche Objekte in TObjectList verhindern?

Hallo!

Ich füge in einer angepassten TObjectList (abgeleitet von TObjectList für Kunden-Objekte) Objekte vom Typ TKunde hinzu.
An anderer Stelle im Programm erstelle ich z.B. noch ein Kunden-Objekt, welches die gleichen Daten wie Kundennummer hat.

Nun möchte ich also prüfen, ob bereits ein Kundenobjekt mit der Kundennummer in der TObjectList vorhanden ist. Könnt ihr mir einen Tipp geben, wie ich das Problem lösen kann?

Danke!
Andy

alzaimar - Do 04.10.07 13:25

sunnyandy hat folgendes geschrieben:

dann habe ich aber eine Laufzeit O(n) wenn ich n Einträge habe. Ich dachte eigentlich, die ObjectList bietet mir dafür irgendwas.

Meinst Du, so eine TObjectList kann zaubern?

WEnn Du die Suche beschleunigen willst, dann sortiere die Liste und verwende binary search O(log n), oder merke Dir in einer Hashmap / Dictionary die Kundennummern, die schon eingefügt wurden O(1).

jaenicke - Do 04.10.07 13:30

Weniger als linearen Aufwand wirst du kaum bekommen können...
Schließlich müssen ja alle Einträge durchsucht werden, und der Aufwand ändert sich ja nicht, nur weil dies in einer Funktion einer Klasse gemacht wird, die du nur einmal aufrufst. Man könnte zwar eine sortierte Liste im Speicher halten, so dass du nur so lange suchen musst wie die gesuchte Kundennummer noch vorkommen kann, nur dürfte sich der Geschwindigkeitsvorteil erstens in Grenzen halten und zweitens durch den erhöhten Aufwand der Sortierung amortisiert werden.

Der Punkt ist aber, dass die TObjectList ja nur beliebige Objekte verwaltet, deren Inhalt aber nicht kennt. Es werden ja nur die Adressen der Objekte verwaltet. Und deshalb kann die TObjectList selbst auch keinerlei Operationen mit Eigenschaften der Objekte o.ä. durchführen.

alzaimar - Do 04.10.07 14:36

jaenicke hat folgendes geschrieben:

Weniger als linearen Aufwand wirst du kaum bekommen können...

Das stimmt nicht. Mit einer Hashmap liegt er bei O(1). Ähnlich schnell ist eine SkipList. Ich würde die 'Add'-Methode überschreiben und hier eine Hashmap (TStringDictionary, müsste hier im Forum irgendwo rumschwirren) nehmen.

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

Procedure TMyDerivedObjectList.Add (anObject : TOBject);
Begin
  If fMyHashmap.Contains (TMyObject (anObject).UniqueIdentifier) Then
    Exit
  Else
    Inherited
End;

jaenicke - Do 04.10.07 16:08

O(1)? Also ich weiß zwar was eine Hashmap ist und habe auch schon zur Übung eine implementiert (in Java), aber auf diesen geringen Aufwand würde ich bei dieser Art von Daten (Kundennummern als Schlüssel, die ja jede Zahl bis zu einer Maximalzahl annehmen können) niemals kommen mit meiner Implementierung. (Es sei denn mit einem viel zu großen Arbeitsspeicheraufwand oder einer relativ kleinen Maximalzahl.)

Aber vielleicht sehe ich auch den Wald vor lauter Bäumen nicht...

jaenicke - Do 04.10.07 16:43

Also ich habe mir die Implementierung kurz angesehen. Wo ist da die Komplexität O(1)?

Eine Komplexität von O(1) hätte ich, wenn ich ein Array von zum Beispiel 100 möglichen Hash-Funktionswerten habe und dann direkt mit einem Schritt (Zugriff auf den Eintrag an der Stelle des Arrays, den mit die Hashfunktion vorgibt) den ersten Eintrag erreiche.
Wenn die Funktion gut gewählt ist, werde ich dann nicht viele Einträge an der Stelle haben und schnell die Liste der wenigen Einträge mit diesem Hashwert durchschauen können.

Da die Kundennummer aber jeden Wert von 1 bis einem n annehmen kann, kann ich diese kaum per Funktion auf eine geringere Anzahl von Hashwerten reduzieren. Und damit habe ich dann nicht mehr O(1) als Komplexität, es sei denn ich benutze ein Array mit n Einträgen.

alzaimar - Do 04.10.07 17:24

Also:
O(n) bedeutet, das der Algorithmus, bei doppelter Anzahl der Elemente auch doppelt so lange dauert.
O(1) bedeutet, das der Algorithmus immer gleich lang dauert, egal wie viele Elemente es sind.

Hashmaps haben die Eigenschaft, das es ihnen völlig wurscht ist, ob sie nun in einer Liste mit 100.000.000 Elementen suchen müssen, oder ein einer Liste mit 1 Element.

Was Du ansprichst, nennt sich 'Kollision', wenn also zwei Hashwerte (mod Listenlänge) auf den gleichen Eintrag gemappt werden. Um das zu vermeiden, wird die Liste bei einem bestimmten Füllgrad einfach vergrößert. Ich verdopple die Listengröße und mappe alle Einträge kurzerhand um. Das ist einmalig etwas langsam, aber da es nur maximal 20x passiert (wenn man die Liste kontinuierlich mit 2 Mrd. Werten füllt, ist das zu verkraften).

Trotzdem kann es sein, das zwei Elemente an die gleiche Stelle gemappt werden. Dafür gibt es wiederum diverse Strategien, ich habe mich für Chained Hashing entschieden. Auch hier ist jedoch die durchschnittliche Anzahl von Kollisionen/Listengröße konstant, insofern spielt das dann bei der Big-Oh-Betrachtung auch keine Rolle.

Du sprichst weiterhin den worst case an, der aber bei der Big-Oh-Betrachtung auch keine Rolle spielt. Dann wäre Quicksort O(n*n) aber wer behauptet sowas schon.

Ich schlage vor, Du analyierst einfach mal die Ausführungszeiten, denn die Realität ist immer noch das beste Argument.

Übrigens sind Skiplisten beinahe noch schneller. Es handelt sich zwar 'nur' um mehrfach verkettete Listen, aber da die Verkettung sehr geschickt (mit Random) gemacht wird, ist sie trotzdem rasend schnell und liegt auch bei O(1).

jaenicke - Do 04.10.07 18:50

Das ist mir schon klar, ich bin nur der Meinung, dass die Art der Daten hier eher zum worst case führt. Das war jedenfalls meine Erfahrung bei einem Projekt. (Bei dem ging es um Inventarnummern, die ja ähnlich geartet sein dürften wie die hier angesprochenen Kundennummern.)

Aus verschiedenen Gründen war eine Sortierung der Daten bei diesem Projekt nicht möglich (es handelte sich um externe Daten), so dass auch diese zur Optimierung ausfiel. Aber dies war auch ein Einzelfall, der natürlich nicht unbedingt verallgemeinerbar auf diesen Fall ist.
Die Frage ist eigentlich, wie die Kundennummern aussehen und wie viele es sind.

Wenn du jedenfalls sagst, dass auch bei einem derartigen Fall eine Lösung möglich ist, deren Aufwand günstig ist, dann glaube ich das einfach mal. Ich wüsste da zwar keine Umsetzung, auch nicht mit der verlinkten Unit, aber wenn du das sagst, ok, und ich muss es ja auch nicht umsetzen :mrgreen:.

alzaimar - Do 04.10.07 20:20

jaenicke hat folgendes geschrieben:

Das ist mir schon klar, ich bin nur der Meinung, dass die Art der Daten hier eher zum worst case führt.

Die Hash-Funktion muss allgemeingültig und so konstruiert sein, das eine möglichst gleichverteilte Transformation der Schlüssel stattfindet. Ich verwende für Strings den ELF-Hash, der zur Passwortverschlüsselung in Unix-Systemen Verwendung findet. Du kannst auch einen CRC nehmen, der allerdings langsam ist.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!