[Programmieren] Ist es üblich, mehrere Objekte für verschiedene Funktionen anzulegen ?

...komplette Frage anzeigen

3 Antworten

Ja. Klar möglich - und auch irgendwo üblich.

Also mehrere Datenstrukturen zu kombinieren, dass man die Vorteile von beidem nutzen kann.

Was dir aber bewusst sein sollte: Du hast dadurch immer auch irgendwelche Nachteile. Auf jeden Fall erhöhten Speicherbedraf. Aber auch Nachteile beim Einfügen oder Löschen.

Fraglich ist immer, ob du deinen erhoften Performancegewinn bekommst, ob der erforderte Mehraufwand sich lohnt (implementieren, tests schreiben, dokumentieren und so weiter) und dass du z.B. nicht langsamer wird.

Aber angenommen du hast einen Fall, wo du sehr viele Elemente hast. Du kaum inserts oder delets hast. Aber extrem häufig Zugriffe - und zwar auf verschiedene Arten - wieso nicht?

Wichtig ist in jedem Fall, dass du das richtig kapselst..

In deinem Fall ist "MeineKlasse" eine Datenstruktur, die du dann am besten auch so nennst (vielleicht in deinem Fall LinkedTreeHashMap). Und dann z.B. auch IList oder so etwas implementieren lässt.

UND außer Daten Speichern nichts in dieser Klasse machst! Denn alles andere wäre ziemlicher Mist und Widerspruch gegen grundlegende Objektorientierte Prinzipien.

Du benutzt dann LinkedTreeHashMap wie eine ganz normale Liste.

Es lohnt sich im Internet nach bestehenden Implementierungen zu schauen

Gibt nämlich häufig so etwas vorgefertigt.

Ich also Java-Programmierer kenne z.B. https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html

Das ist eine Unterklasse von einer normalen HashMap, in die aber noch Verkettung eingearbeitet wurde. Also mix aus LinkedList und HashMap. Ist somit einfach auch effizienter als 2 Datenstrukturen zu haben.

Ein Blick über den Tellerrand

Wenn man so auf Performance trillt, stellt sich durchaus auch die Frage, ob C# die richtige Sprache ist. Vielleicht ist dann doch C++ oder Rust (in meinen Augen deutlich schöner) die bessere Sprache?

Möchte auch noch dazu sagen, dass im Zweifelsfall eine HashMap eine sehr gute Wahl ist.

Es gibt Programmiersprachen wie Lua, die haben HashMap als einzige Datenstruktur. Und dann ist ein Array eine HashMap wo du Zahlen von 1 bis n als Index nimmst (ja, lua beginnt man mit 1 das zählen).

Was ich damit sagen will:

Programmier erst einmal dein Programm.

Arbeite - wie du das bereits gemacht hast - bei Typen immer mit Interfacen.

Und wenn du dann feststellst, das Programm funktioniert und du hast noch Zeit und du möchtest die Performance verbessern, dann kannst du immer noch so eine optimierte Datenstruktur schreiben und Performancetests durchführen.

Gruß

Tuxgamer

Nein das ist eher unüblich, wenn ein bestimmter Typ deine Anforderungen nicht unterstützt würde man eher die bestehenden Klassen erweitern und diese Funktionen implementieren.

Der Sinn der Klasse ist ja die Kapsellung, wenn du aber jetzt verschiedene Klassen für die gleichen Objekte nutzt wird dein Programm schnell komplex und fehleranfällig.

Dann passieren so Sachen wie, ein Objekt wird in Liste 1 eingetragen aber im Baum nicht etc.

Außerdem kannst müsstest du überall wo du diese Struktur verwendest sie neu anlegen, mit einer Klasse geht das wesentlich einfacher.

Btw ich kenne die C# implementierung nicht, aber zum Suchen von Objekten ist der Baum an sich am schnellsten, weil die Werte bereits sortiert sind und das die Suche extrem vereinfacht, als in unsortierten Daten.


Crysali 05.07.2017, 11:55

Danke für deine Antwort,

(...) verschiedene Klassen für die gleichen Objekte nutzt wird dein Programm schnell komplex und fehleranfällig. Dann passieren so Sachen wie, ein Objekt wird in Liste 1 eingetragen aber im Baum nicht etc (...)

Könnte man das nicht über Properties lösen ? Man könnte, wenn man beispielsweise eine Add( T item) Methode implementiert, dort dann alles entsprechend einsortieren, in die Liste, den Baum, ...
Man kommt denke ich nicht häufig in eine Situation, wo so etwas hilfreich ist, mir fällt spontan kein gutes Beispiel ein, aber beispielsweise wäre es zum Suchen doch hilfreich, wie folgt:

Btw ich kenne die C# implementierung nicht, aber zum Suchen von Objekten ist der Baum an sich am schnellsten, weil die Werte bereits sortiert sind und das die Suche extrem vereinfacht, als in unsortierten Daten.

Soweit mir bekannt, hat ein B-Baum eine Komplexität von O(log(n)), während ein Dictionary/ Hashtabelle eine Komplexität von O(1) besitzt ( weiß ich eigentlich nur für Hashtabelle, sollte aber gleich sein). Wenn man viel Suchen müsste, würde es sich dann nicht lohnen, ein Dictionary/ eine Hashtabelle anzulegen, statt den B-Baum zum Suchen zu benutzen, diesen dann nur zum Sortieren zu verwenden ?

Laut https://en.wikipedia.org/wiki/B-tree#B-tree_usage_in_databases braucht man beispielsweise bei einem Baum mit 1.000.000 Objekten 20 Vergleiche, naja, dahin muss man erstmal kommen, zu so einer großen Zahl von Objekten, sagt man dann, das es darauf auch nicht ankommt und man statt Speicherplatz für das Dictionary zu verwenden auf selbiges verzichtet ?

0
PeterKremsner 06.07.2017, 11:54
@Crysali

Könnte man das nicht über Properties lösen ? Man könnte, wenn man
beispielsweise eine Add( T item) Methode implementiert, dort dann alles
entsprechend einsortieren, in die Liste, den Baum, ...

Natürlich kann man es lösen, allerdings wiederspricht das wie gesagt dem Konzept der Abstraktion welches man mit OOP ja anstrebt.

Wenn eine Klasse etwas nicht kann was man aber von ihr möchte erweitert man diese einfach.

Du kannst also durchaus die Klasse B-Baum mit deinem Suchalgorithmus erweitern wenn er dir ein schnelleres Suchen erlaubt und den zusätzlichen Arbeitsspeicher verbrauch rechtfertigt.

Soweit mir bekannt, hat ein B-Baum eine Komplexität von O(log(n)),
während ein Dictionary/ Hashtabelle eine Komplexität von O(1) besitz

Ich sag mal jein, ein Baum hat immer die Komplexität O(log(n)) und eine Hashtabelle meistens die Komplexität O(1).

Allerdings muss die Komplexität der Hashtabelle nicht konstant sein, wenn zB der Hashalgorithmus viele Kollisionen erzeugt kann die Komplexität im worst case O(n) sein, weil dann die Hashtabelle zu einer Linked List degradiert.

Zudem ist die Komplexität nicht immer mit der Geschwindigkeit direkt vergleichbar. Sollte zB der Hashalgorithmus langsam sein, kann es sein, dass das berechnen des Hashwertes länger dauert als das Suchen im Baum, wo bei jedem Knoten im Prinzip nur ein größer kleiner vergleich notwendig ist.

Ich würde allerdings behauten, dass der Geschwindigkeitsgewinn zwischen einem B-Baum und einer Hashtabelle im RAM keinen großen unterschied macht und den zusätzlichen Ram verbrauch durch die doppelte Speicherung der Daten nicht rechtfertigt.

Was aber durchaus möglich ist, ist eine Kombination aus Baum und Hashtabelle, du kannst zB die Daten im Baum speichern und in der Hashtabelle legst du unter dem Hashwert einen Index im Baum ab, welcher deinen Knoten eindeutig identifiziert, dadurch kannst du auch in einem Baum mit ca. O(1) suchen und den Speicherverbrauch trotzdem klein halten, auch wenn der reine B-Baum natürlich immer noch kleiner ist.

1

Das widerspricht meiner Ansicht nach gegen das Single-Responsibility-Prinzip

https://de.wikipedia.org/wiki/Single-Responsibility-Prinzip

, und auch mit KISS (Keep it simple, stupid) und DRY (don't repeat yourself) geht das nicht so ganz konform. 

Denn in deiner Beispielklasse musst du immer darauf achten, dass die Daten immer in allen drei Repräsentationen in der Klasse synchron sind. Du musst sie in allen dreien hinzufügen, löschen und bearbeiten, wenn du ein Element veränderst. Und dabei entsteht eine Menge Aufwand, zumal du den dreifachen Speicherverbrauch hast.

In deinem Beispiel würde ich entweder nur den Binary-Tree nutzen - um die Existenz eines Elementes zu prüfen, kannst du auch die Suche nutzen. Wenn das Element nicht drin ist, dann wird es nicht gefunden.

Oder ich würde die Liste immer sortiert halten und mit einer binären Suche arbeiten. 

Gleichzeitig lege ich aber auch ein Dictionary an, damit ich leicht überprüfen kann, ob ein Objekt in meiner Liste ist ( ich missbrauche hier den Schlüssel als schnelle Suchfunktion, speichere ja unter dem Objekt das Objekt).

Hier läuft intern sehr wahrscheinlich eine lineare Suche, und die ist ineffizienter als die binäre Suche / der binäre Baum. 

Crysali 05.07.2017, 12:12

Danke für deine Antwort,

Hier läuft intern sehr wahrscheinlich eine lineare Suche, und die ist ineffizienter als die binäre Suche / der binäre Baum.

Laut https://stackoverflow.com/questions/7532678/what-is-the-complexity-of-these-dictionary-methods besitzt ein Dicionary eine Komplexität von O(1) und müsste demnach schneller sein, wenn ich das richtig verstanden habe. Fraglich, ob das dann aber von anderen Gesichtspunkten her gut ist, wie du schön ausführst.

3
ceevee 05.07.2017, 13:30
@Crysali

Da hast du recht, O(1) ist schneller als das O(log n) der binären Suche. 

https://www.hackerearth.com/practice/notes/sorting-and-searching-algorithms-time-complexities-cheat-sheet/

Der Unterschied zwischen O(1) und O(log n) ist allerdings minimal, auf den kleinen Performance-Vorteil kann man zugunsten eines besser les- und wartbaren Codes mMn. verzichten. Denn der User (der dein Programm nutzt), muss wohl schon ein paar Milliarden Datensätze haben und damit arbeiten, damit er den Unterschied zwischen den beiden Algorithmen spürt. 

0
Crysali 05.07.2017, 18:41
@ceevee

Da stimme ich dir zu, bei "kleineren" Datensätzen macht das dann keinen Sinn, vielen Dank!

0

Was möchtest Du wissen?