C# Datentypenauswahl

[Ben]

Hallo zusammen

Zuallererst: Bin noch nicht wahnsinnig bewandert in der Objektorientierung. Ich stehe nun vor einer Frage, auf die ich keine wirkliche Antwort weiss.

Nehmen wir mal an, ich habe eine Strasse, in der Strasse hat es Häuser. Ich habe also eine Strasse-Klasse und eine Haus-Klasse. Das Haus hat eine Nummer. In der Strasse-Klasse (bzw. natürlich dann im Objekt) habe ich dann eine Liste/Hashtable/... in der die Häuser drin sind. Ich möchte über die Hausnummer das gewünschte Haus bekommen.

Welcher Datentyp ist da geeignet? Nehme ich eine (sortierte) Liste, muss ich ja evtl. alle durchackern, bis ich das gewünschte gefunden habe. Nehme ich aber eine Hashtable (da könnte ich ja das Haus über den Key finden, wenn ich dafür die Haus# nehme) habe ich wieder das Problem dass ich die Hausnummern nicht ändern kann. Ich müsste sie ja dann auch in der Hashtable anpassen und das kann ja nicht Sinn der Sache sein.

Gibt es für dieses Problem eine einfachere Lösung oder muss ich mich jedesmal durch die Liste kämpfen?

Danke für eure Antworten!

Gruss Ben

[Daniel Thoma]

Hallo Ben,

Hausnummern sind meist ziemlich lückenlos vergeben, damit würde sich eine normale Liste mit Index-basiertem Zugriff (also bspw. eine Array-Liste, wie immer die bei C# heißt, die Namensgebung ist da hochgradig bescheuert).
Dann kannst Du Haus Nr. 123 einfach mit list.get(123) bekommen und das geht in konstanter Zeit. Gibt es kein Haus mit der Nummer, kommt halt null zurück. Diese leeren Listenplätze sind akzeptabel, da es davon typischerweise eben nicht viele gibt.
Nun kommen noch so Sachen wie Haus 1a, 1b, 1c ins Spiel. Das könnte man abbilden, indem man Listen schachtelt. Für a,b,c muss man dann eben in einer Liste nochmal linear suchen.
Außerdem gibt es sortierte Tabellen, z.B. solche, die auf Binärbäumen aufbauen (irgendwo hat C# auch sowas). Diese speichern die Elemente sortiert und der Zugriff geht in O(log(n)). Nicht so schnell wie die Array-Liste aber immerhin. Da könnte man dann auch direkt die Nummern mit Buchstaben ablegen, wenn man die Ordnung entsprechend definiert.

Zu guter Letzt gibt es aber noch eine Designfrage zu dem Thema: Was hat die Nummerierung mit der Anordnung der Häuser zu tun? Typischerweise werden in Deutschland Häuser abwechselnd rechts links nummeriert, es gibt aber meines Wissens auch Länder/Orte bei denen einfach die eine Seite hoch und die andere runter nummeriert wird/wurde. Außerdem gibt es da natürlich immer kleine Abweichungen vom Schema.
Du musst Dir also überlegen, welche Information Du eigentlich aus der Ordnung der Hausnummern ziehen willst, und ob das so wirklich funktioniert.

Grüße

Daniel

[Ben]

Hallo Daniel

Erstmal vielen Dank für deine Antwort.

Ich möchte nochmals nachhaken, wenn ich schon einen Experten habe den ich löchern kann. :-) Das mit den Hausnummern war eigentlich eher ein Beispiel für meine grundlegende Frage, wie man das machen muss wenn man Objekte anhand einer bestimmten Eigenschaft finden muss.

Wenn ich jetzt mal von dem Beispiel mit den Hausnummern abstrahiere und annehme dass die gesuchte Eigenschaft veränderbar ist (was wahrscheinlich bei Hausnummern nicht so der Fall ist), wäre es ja nicht sehr sinnvoll, diese Eigenschaft als Schlüssel für etwas wie eine ArrayList oder ähnliches zu nehmen, oder? Sonst hätte ich ja dann redundante und gegebenenfalls auch inkonsistente Informationen im Objekt und bei der Liste. In diesem Fall bliebe mir also nichts anderes übrig als das richtige Objekt in der Liste oder einem ähnlichen Datentypen zu suchen?

Nochmals Danke und Gruss
Ben

Hallo Ben,

Hausnummern sind meist ziemlich lückenlos vergeben, damit würde sich eine normale Liste mit Index-basiertem Zugriff (also bspw. eine Array-Liste, wie immer die bei C# heißt, die Namensgebung ist da hochgradig bescheuert).
Dann kannst Du Haus Nr. 123 einfach mit list.get(123) bekommen und das geht in konstanter Zeit. Gibt es kein Haus mit der Nummer, kommt halt null zurück. Diese leeren Listenplätze sind akzeptabel, da es davon typischerweise eben nicht viele gibt.
Nun kommen noch so Sachen wie Haus 1a, 1b, 1c ins Spiel. Das könnte man abbilden, indem man Listen schachtelt. Für a,b,c muss man dann eben in einer Liste nochmal linear suchen.
Außerdem gibt es sortierte Tabellen, z.B. solche, die auf Binärbäumen aufbauen (irgendwo hat C# auch sowas). Diese speichern die Elemente sortiert und der Zugriff geht in O(log(n)). Nicht so schnell wie die Array-Liste aber immerhin. Da könnte man dann auch direkt die Nummern mit Buchstaben ablegen, wenn man die Ordnung entsprechend definiert.

Zu guter Letzt gibt es aber noch eine Designfrage zu dem Thema: Was hat die Nummerierung mit der Anordnung der Häuser zu tun? Typischerweise werden in Deutschland Häuser abwechselnd rechts links nummeriert, es gibt aber meines Wissens auch Länder/Orte bei denen einfach die eine Seite hoch und die andere runter nummeriert wird/wurde. Außerdem gibt es da natürlich immer kleine Abweichungen vom Schema.
Du musst Dir also überlegen, welche Information Du eigentlich aus der Ordnung der Hausnummern ziehen willst, und ob das so wirklich funktioniert.

Grüße

Daniel

[Daniel Thoma]

Hallo Ben,

Wenn ich jetzt mal von dem Beispiel mit den Hausnummern abstrahiere und annehme dass die gesuchte Eigenschaft veränderbar ist (was wahrscheinlich bei Hausnummern nicht so der Fall ist), wäre es ja nicht sehr sinnvoll, diese Eigenschaft als Schlüssel für etwas wie eine ArrayList oder ähnliches zu nehmen, oder?

Eigenschaften, die als Schlüssel dienen, dürfen sich nicht ändern, jedenfalls nicht, so lange das entsprechende Objekt in der Datenstruktur ist, richtig. Wenn man effizient über solche veränderlichen Eigenschaften zugreifen muss, muss man aber Hash-Tabellen, Binärbäume oder andere Datenstrukturen verwenden.

Sonst hätte ich ja dann redundante und gegebenenfalls auch inkonsistente Informationen im Objekt und bei der Liste.

Redundant ist die Information in jedem Fall. Das ist aber kein Problem. Redundanz ist notwendig, um effizient Zugreifen zu können. Auch Indizes, wie sie Datenbanken anlegen, sind ja redundant, in dem Sinne, dass man die Information auch schon so gespeichert hat.

In diesem Fall bliebe mir also nichts anderes übrig als das richtige Objekt in der Liste oder einem ähnlichen Datentypen zu suchen?

Nein, je nach Szenario gibt es zwei Möglichkeiten:
1. Du kannst temporäre Datenstrukturen aufbauen. Wenn Du bspw. eine Berechnung durchführst, und weist, dass sich die Daten während dieser Berechnung nicht ändern, kannst Du dafür Datenstrukturen aufbauen.
2. Du kannst die Datenstrukturen bei Änderungen aktualisieren. Das erfordert allerdings, dass Dein Datenmodell eine Möglichkeit bietet, auf Änderungen der Daten zu reagieren. Dann kannst Du abfangen, dass ein "Schlüssel" geändert wird, das Element löschen und neu einfügen. Das klingt erstmal relativ aufwendig und ist es tatsächlich auch. Allerdings kommt man bei komplexeren Anwendungen und Datenmodellen praktisch nie darum herum, ein solches Event-Handling zu implementieren.

Grüße

Daniel

[Ben]

Hallo Daniel

Vielen Dank, ich denke jetzt sind alle Fragen geklärt... :-)

Gruss Ben