Was wäre der Nachteil, eine Klasse als Unterklasse einer Liste von sich selbst zu definieren?

48

In einem meiner letzten Projekte habe ich eine Klasse mit dem folgenden Header definiert:

public class Node extends ArrayList<Node> {
    ...
}

Nach einer Diskussion mit meinem CS-Professor stellte er jedoch fest, dass die Klasse sowohl für das Gedächtnis "schrecklich" als auch für die "schlechte Praxis" sei. Ich habe nicht festgestellt, dass das erste besonders wahr und das zweite subjektiv ist.

Mein Grund für diese Verwendung ist, dass ich eine Idee für ein Objekt hatte, das als etwas definiert werden musste, das eine beliebige Tiefe haben könnte, wobei das Verhalten einer Instanz entweder durch eine benutzerdefinierte Implementierung oder durch das Verhalten mehrerer gleichartiger Objekte, die interagieren, definiert werden könnte . Dies würde die Abstraktion von Objekten ermöglichen, deren physikalische Implementierung aus vielen miteinander wechselwirkenden Unterkomponenten bestehen würde

Auf der anderen Seite sehe ich, wie schlecht das sein kann. Die Idee, etwas als eine Liste von sich selbst zu definieren, ist nicht einfach oder physikalisch umsetzbar.

Gibt es einen triftigen Grund, warum ich dies in meinem Code nicht verwenden sollte , wenn ich meine Verwendung dafür in Betracht ziehe?


¹ Wenn ich das näher erläutern muss, würde ich mich freuen; Ich versuche nur, diese Frage kurz zu halten.

Addison Crump
quelle
1
@gnat Dies hat mehr damit zu tun, eine Klasse streng als eine Liste von sich selbst zu definieren, als Listen zu enthalten, die Listen enthalten. Ich denke, es ist eine Variante einer ähnlichen Sache, aber nicht ganz das Gleiche. Diese Frage bezieht sich auf etwas in der Art von Robert Harveys Antwort .
Addison Crump
16
Von etwas zu erben, das selbst parametrisiert ist, ist nicht ungewöhnlich, wie das in C ++ häufig verwendete CRTP- Idiom zeigt . Im Falle des Containers lautet die Schlüsselfrage jedoch, warum Sie Vererbung anstelle von Komposition verwenden müssen.
Christophe
1
Ich mag die Idee. Schließlich ist jeder Knoten in einem Baum ein (Unter-) Baum. Normalerweise wird die Baumstruktur eines Knotens in einer Typansicht verborgen (der klassische Knoten ist kein Baum, sondern ein einzelnes Objekt) und stattdessen in der Datenansicht ausgedrückt (der einzelne Knoten ermöglicht den Zugriff auf Zweige). Hier ist es umgekehrt; Wir werden keine Branchendaten sehen, es ist in der Art. Ironischerweise würde das tatsächliche Objektlayout in C ++ wahrscheinlich sehr ähnlich sein (Vererbung wird sehr ähnlich wie Daten enthalten implementiert), was mich glauben lässt, dass es sich um zwei Arten handelt, dasselbe auszudrücken.
Peter - Wiedereinsetzung von Monica
1
Vielleicht fehlt mir ein bisschen, aber müssen Sie wirklich erweitern ArrayList<Node> , im Vergleich zu implementieren List<Node> ?
Matthias

Antworten:

107

Ehrlich gesagt sehe ich hier keine Notwendigkeit für Vererbung. Das ergibt keinen Sinn. Node ist ein ArrayList von Node?

Wenn dies nur eine rekursive Datenstruktur ist, schreiben Sie einfach etwas wie:

public class Node {
    public String item;
    public List<Node> children;
}

Welches macht Sinn; Knoten enthält eine Liste von untergeordneten oder untergeordneten Knoten.

Robert Harvey
quelle
34
Es ist nicht dasselbe. Eine Liste einer Liste einer Liste ad-infinitum ist bedeutungslos, es sei denn, Sie speichern etwas anderes als eine neue Liste in der Liste. Dafür Item gibt es und Itemarbeitet unabhängig von den Listen.
Robert Harvey
6
Oh, ich verstehe jetzt. Ich hatte mich genähert Node ist ein ArrayList von Nodewie Node enthält 0 bis viele Node Objekte. Ihre Funktion ist das gleiche, im Wesentlichen, aber anstatt ist eine Liste von Objekten wie, es hat eine Liste wie Objekte. Der ursprüngliche Entwurf für die geschriebene Klasse war der Glaube, dass jede Klasse Nodeals eine Reihe von Unterarten ausgedrückt werden kann Node, was beide Implementierungen tun, aber diese ist sicherlich weniger verwirrend. +1
Addison Crump
11
Ich würde sagen, dass die Identität zwischen einem Knoten und einer Liste "natürlich" entsteht, wenn Sie einfach verknüpfte Listen in C oder Lisp oder was auch immer schreiben: In bestimmten Designs ist der Kopfknoten "die Liste", im Sinne der Einzigen etwas, das jemals benutzt wurde, um eine Liste darzustellen. Daher kann ich das Gefühl, dass ein Knoten in einigen Kontexten möglicherweise eine Sammlung von Knoten ist (nicht nur hat), nicht vollständig zerstreuen, obwohl ich damit einverstanden bin, dass sich EvilBadWrong in Java anfühlt.
Steve Jessop
12
@ nl-x Dass die eine Syntax kürzer ist, heißt nicht, dass es besser ist. Übrigens ist es ziemlich selten, auf solche Elemente in einem Baum zuzugreifen. Normalerweise ist die Struktur zur Kompilierungszeit nicht bekannt, sodass Sie solche Bäume in der Regel nicht mit konstanten Werten durchlaufen. Die Tiefe ist ebenfalls nicht festgelegt, sodass Sie mit dieser Syntax nicht einmal alle Werte durchlaufen können. Wenn Sie den Code anpassen, um ein herkömmliches Tree-Traversal-Problem zu verwenden, schreiben Sie am Ende Childrennur ein- oder zweimal. Aus Gründen der Code-Klarheit ist es in solchen Fällen in der Regel vorzuziehen , ihn auszuschreiben.
Servy
8
+1 für die Bevorzugung der Komposition gegenüber der Vererbung .
Menelaos Kotsollaris
57

Das Argument "fürchterlich für das Gedächtnis" ist völlig falsch, aber es ist eine objektiv "schlechte Praxis". Wenn Sie von einer Klasse erben, erben Sie nicht nur die Felder und Methoden, die Sie interessieren. Stattdessen erben Sie alles . Jede deklarierte Methode, auch wenn sie für Sie nicht nützlich ist. Und vor allem erben Sie auch alle Verträge und Garantien, die die Klasse bietet.

Das Akronym SOLID bietet einige Heuristiken für eine gute objektorientierte Gestaltung. Hier haben das I nterface Segregation Principle (ISP) und das L iskov Substitution Pricinple (LSP) etwas zu sagen.

Der ISP fordert uns auf, unsere Schnittstellen so klein wie möglich zu halten. Aber durch das Erben von erhalten ArrayListSie viele, viele Methoden. Ist es sinnvoll get(), remove(), set()(ersetzen) oder add()(Einsatz) ein Kind - Knoten an einem bestimmten Index? Ist es sinnvoll, ensureCapacity()von der zugrunde liegenden Liste? Was bedeutet es für sort()einen Knoten? Sollen Nutzer Ihrer Klasse wirklich eine bekommen subList()? Da Sie nicht gewünschte Methoden nicht ausblenden können, besteht die einzige Lösung darin, die ArrayList als Mitgliedsvariable zu haben und alle tatsächlich gewünschten Methoden weiterzuleiten:

private final ArrayList<Node> children = new ArrayList();
public void add(Node child) { children.add(child); }
public Iterator<Node> iterator() { return children.iterator(); }

Wenn Sie wirklich alle Methoden wollen, die Sie in der Dokumentation sehen, können wir zum LSP übergehen. Der LSP sagt uns, dass wir in der Lage sein müssen, die Unterklasse überall dort zu verwenden, wo die Elternklasse erwartet wird. Wenn eine Funktion einen ArrayListas-Parameter annimmt und wir Nodestattdessen unseren übergeben , soll sich nichts ändern.

Die Kompatibilität von Unterklassen beginnt mit einfachen Dingen wie Typensignaturen. Wenn Sie eine Methode überschreiben, können Sie die Parametertypen nicht strenger festlegen, da dies möglicherweise Verwendungen ausschließt, die für die übergeordnete Klasse zulässig waren. Aber das ist etwas, was der Compiler für uns in Java überprüft.

Der LSP geht jedoch viel tiefer: Wir müssen die Kompatibilität mit allem aufrechterhalten, was die Dokumentation aller übergeordneten Klassen und Schnittstellen verspricht. In ihrer Antwort hat Lynn einen solchen Fall gefunden , wo die ListSchnittstelle (die Sie über geerbt haben ArrayList) garantiert , wie die equals()und hashCode()Methoden funktionieren soll. Denn hashCode()Ihnen wird sogar ein bestimmter Algorithmus vorgegeben, der exakt implementiert werden muss. Nehmen wir an, Sie haben folgendes geschrieben Node:

public class Node extends ArrayList<Node> {
  public final int value;

  public Node(int value, Node... children) {
    this.value = Value;
    for (Node child : children)
      add(child);
  }

  ...

}

Dies setzt voraus, dass die valuenicht zum beitragen hashCode()und nicht beeinflussen können equals(). Die ListSchnittstelle, die Sie zu ehren versprechen, indem Sie sie erben new Node(0).equals(new Node(123)), muss wahr sein.


Da durch das Erben von Klassen zu leicht versehentlich ein Versprechen einer übergeordneten Klasse gebrochen werden kann und in der Regel mehr Methoden verfügbar gemacht werden, als Sie beabsichtigt haben, wird im Allgemeinen vorgeschlagen, die Komposition der Vererbung vorzuziehen . Wenn Sie etwas erben müssen, wird empfohlen, nur Schnittstellen zu erben. Wenn Sie das Verhalten einer bestimmten Klasse wiederverwenden möchten, können Sie es als separates Objekt in einer Instanzvariablen speichern, sodass Ihnen nicht alle Versprechen und Anforderungen aufgezwungen werden.

Manchmal deutet unsere natürliche Sprache auf eine Vererbungsbeziehung hin: Ein Auto ist ein Fahrzeug. Ein Motorrad ist ein Fahrzeug. Soll ich Klassen definieren Carund Motorcycledie von einer VehicleKlasse erben ? Bei objektorientiertem Design geht es nicht darum, die reale Welt in unserem Code exakt wiederzugeben. Wir können die reichen Taxonomien der realen Welt nicht einfach in unserem Quellcode kodieren.

Ein solches Beispiel ist das Problem der Mitarbeiter-Chef-Modellierung. Wir haben mehrere Persons, jedes mit einem Namen und einer Adresse. An Employeeist ein Personund hat ein Boss. A Bossist auch a Person. Soll ich also eine PersonKlasse erstellen , die von Bossund geerbt wird Employee? Jetzt habe ich ein Problem: Der Chef ist auch Angestellter und hat einen anderen Vorgesetzten. So scheint es, Bosssollte sich verlängern Employee. Aber das CompanyOwnerist ein Bossaber ist kein Employee? Jede Art von Vererbungsgraph wird hier irgendwie zusammenbrechen.

Bei OOP geht es nicht um Hierarchien, Vererbung und Wiederverwendung vorhandener Klassen, sondern um die Verallgemeinerung des Verhaltens . In OOP geht es um „Ich habe eine Reihe von Objekten und möchte, dass sie etwas Besonderes tun - und es ist mir egal, wie.“ Dafür sind Schnittstellen gedacht. Wenn Sie die IterableSchnittstelle für Ihre implementieren, Nodeweil Sie sie iterabel machen möchten, ist das vollkommen in Ordnung. Wenn Sie die CollectionSchnittstelle implementieren , weil Sie untergeordnete Knoten usw. hinzufügen / entfernen möchten, ist dies in Ordnung. Aber von einer anderen Klasse erben, weil es dir alles gibt, was nicht ist, oder zumindest nicht, wenn du es dir genau überlegt hast, wie oben beschrieben.

amon
quelle
10
Ich habe Ihre letzten 4 Absätze gedruckt, sie mit About OOP and Inheritance betitelt und sie bei der Arbeit an die Wand geheftet. Einige meiner Kollegen müssen das sehen, da ich weiß, dass sie es zu schätzen wissen, wie Sie es ausdrücken :) Vielen Dank.
YSC
17

Das Erweitern eines Containers an sich wird normalerweise als schlechte Praxis angesehen. Es gibt kaum einen Grund, einen Container zu verlängern, anstatt nur einen zu haben. Das Erweitern eines Containers von Ihnen macht es nur noch merkwürdiger.

DeadMG
quelle
14

Zusätzlich zu dem, was gesagt wurde, gibt es einen etwas Java-spezifischen Grund, um diese Art von Strukturen zu vermeiden.

Der Vertrag der equalsMethode für Listen sieht vor, dass eine Liste einem anderen Objekt gleichgestellt wird

Wenn und nur wenn das angegebene Objekt auch eine Liste ist, haben beide Listen dieselbe Größe und alle entsprechenden Elementpaare in den beiden Listen sind gleich .

Quelle: https://docs.oracle.com/javase/7/docs/api/java/util/List.html#equals(java.lang.Object)

Konkret bedeutet dies, dass eine Klasse, die als eine Liste von sich selbst entworfen wurde, Gleichheitsvergleiche teuer machen kann (und Hash-Berechnungen auch, wenn die Listen veränderlich sind). Wenn die Klasse einige Instanzfelder enthält, müssen diese im Gleichheitsvergleich ignoriert werden .

Lynn
quelle
1
Dies ist ein ausgezeichneter Grund, dies aus meinem Code zu entfernen, abgesehen von schlechten Praktiken. : P
Addison Crump
3

Zum Gedächtnis:

Ich würde sagen, das ist eine Frage des Perfektionismus. Der Default-Konstruktor von ArrayListsieht so aus:

public ArrayList(int initialCapacity) {
     super();

     if (initialCapacity < 0)
         throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);

     this.elementData = new Object[initialCapacity];
 }

public ArrayList() {
     this(10);
}

Quelle . Dieser Konstruktor wird auch im Oracle-JDK verwendet.

Überlegen Sie nun, ob Sie mit Ihrem Code eine einfach verknüpfte Liste erstellen möchten. Sie haben gerade erfolgreich Ihren Speicherverbrauch um den Faktor 10x (um genau zu sein sogar geringfügig höher) aufgebläht. Bei Bäumen kann dies auch ohne besondere Anforderungen an die Baumstruktur recht schlecht werden. Die Verwendung einer LinkedListoder einer anderen Klasse sollte dieses Problem lösen.

Um ehrlich zu sein, ist dies in den meisten Fällen nichts anderes als Perfektionismus, selbst wenn wir die Menge des verfügbaren Speichers ignorieren. A LinkedListwürde den Code als Alternative etwas verlangsamen, so dass es ein Kompromiss zwischen Leistung und Speicherverbrauch ist. Meine persönliche Meinung dazu wäre jedoch, nicht so viel Speicherplatz zu verschwenden, wie dies leicht umgangen werden kann.

EDIT: Klarstellung bezüglich der Kommentare (@amon um genau zu sein). In diesem Teil der Antwort wird nicht auf die Frage der Vererbung eingegangen. Der Vergleich der Speichernutzung wird mit einer einfach verknüpften Liste und mit der besten Speichernutzung durchgeführt (in tatsächlichen Implementierungen kann sich der Faktor etwas ändern, aber er ist immer noch groß genug, um einiges an verschwendetem Speicher zusammenzufassen).

In Bezug auf "schlechte Praxis":

Bestimmt. Dies ist aus einem einfachen Grund nicht die Standardmethode zum Implementieren eines Diagramms: Ein Diagrammknoten hat untergeordnete Knoten, nicht eine Liste von untergeordneten Knoten. Es ist eine wichtige Fähigkeit, genau auszudrücken, was Sie mit Code meinen. Sei es in Variablennamen oder in solchen Strukturen. Nächster Punkt: Schnittstellen auf ein Minimum beschränken: Sie haben ArrayListdem Benutzer der Klasse jede Methode über die Vererbung zur Verfügung gestellt. Es gibt keine Möglichkeit, dies zu ändern, ohne die gesamte Struktur des Codes zu brechen. Speichern Sie stattdessen die Listals interne Variable und stellen Sie die benötigten Methoden über eine Adapter-Methode zur Verfügung. Auf diese Weise können Sie der Klasse auf einfache Weise Funktionen hinzufügen und entfernen, ohne alles zu vermasseln.

Paul
quelle
1
10x höher als was ? Wenn ich ein standardmäßig erstelltes ArrayList-Feld als Instanz-Feld habe (anstatt es zu erben), verbrauche ich tatsächlich etwas mehr Speicher, da ich in meinem Objekt einen zusätzlichen Zeiger auf ArrayList speichern muss. Auch wenn wir Äpfel mit Orangen vergleichen und vergleichen, wie von ArrayList geerbt wird, um keine ArrayList zu verwenden, beachten Sie, dass wir in Java immer Zeiger auf Objekte verwenden, niemals Objekte nach Wert, wie dies in C ++ der Fall wäre. Unter der Annahme new Object[0], dass a insgesamt 4 Wörter verwendet, new Object[10]würde a nur 14 Wörter des Speichers verwenden.
Amon
@amon Ich habe es nicht explizit angegeben, sry dafür. Obwohl der Kontext ausreichen sollte, um zu sehen, dass ich mit einer LinkedList vergleiche. Und es heißt Referenz, nicht Zeiger. Und der Punkt mit dem Gedächtnis war nicht, ob die Klasse über die Vererbung verwendet wird oder nicht, sondern einfach die Tatsache, dass (fast) unbenutzte ArrayLists ziemlich viel Gedächtnis verbrauchen .
Paul
-2

Dies scheint wie die Semantik des zusammengesetzten Musters auszusehen . Es wird verwendet, um rekursive Datenstrukturen zu modellieren.

oopexpert
quelle
13
Ich werde das nicht ablehnen, aber deshalb hasse ich das GoF-Buch wirklich . Es ist ein verdammter Baum! Warum mussten wir den Begriff "zusammengesetztes Muster" erfinden, um einen Baum zu beschreiben?
David Arno
3
@DavidArno Ich glaube, es ist der gesamte Aspekt des polymorphen Knotens, der es als "zusammengesetztes Muster" definiert. Die Verwendung einer Baumdatenstruktur ist nur ein Teil davon.
JAB
2
@RobertHarvey, ich bin anderer Meinung (sowohl mit Ihren Kommentaren zu Ihrer Antwort als auch hier). public class Node extends ArrayList<Node> { public string Item; }ist die Vererbungsversion Ihrer Antwort. Ihre Argumentation ist einfacher, aber beide erreichen das eine: Sie definieren nicht-binäre Bäume.
David Arno
2
@DavidArno: Ich habe nie gesagt, dass es nicht funktionieren würde, ich habe nur gesagt, dass es wahrscheinlich nicht ideal ist.
Robert Harvey
1
@DavidArno Hier geht es nicht um Gefühle und Geschmack, sondern um Fakten. Ein Baum besteht aus Knoten und jeder Knoten hat potenzielle Kinder. Ein bestimmter Knoten ist nur zu einem bestimmten Zeitpunkt ein Blattknoten. In einem Verbundwerkstoff ist ein Blattknoten eine Blattkonstruktion, und seine Beschaffenheit ändert sich nicht.
Christophe