Ist die List-Schnittstelle eine undichte Abstraktion?

Wenn ich eine Variable habe, die a Listenthält, kann sie Objekte vieler verschiedener Typen enthalten, z . B. ArrayListoder LinkedList. Der Unterschied zwischen a LinkedListund an ArrayListist ziemlich groß. Das große O-Verhalten der Methoden ist sehr unterschiedlich. Zum Beispiel ist das Sortieren Listund anschließende Verwenden für binäre Suchen für a vollkommen in Ordnung ArrayList, würde aber mit a keinen Sinn ergeben LinkedList.

Das würde ich nicht sagen.

Eine undichte Abstraktion zwingt Sie dazu, sich mit Implementierungsdetails zu befassen, die abstrahiert werden sollen. Die Leistung ist jedoch zwischen den Implementierungen immer unterschiedlich. Wenn Sie dies als undicht betrachten, gibt es keine nicht undichten Abstraktionen.

Wenn etwas als Listohne weitere Dokumentation deklariert wird , sollte klar sein, dass es einfach keine Garantien für die Leistung gibt, und wenn Sie etwas leistungsabhängiges damit machen wollen, sollten Sie eine Kopie erstellen und damit arbeiten.

Vergessen Sie auch nicht, dass es eine noch allgemeinere Benutzeroberfläche gibt, deren Funktionalität häufig ausreicht und die Sie nicht dazu verleitet, so viele Annahmen über die Leistung zu treffen : Collection.

Alle nicht trivialen Abstraktionen sind bis zu einem gewissen Grad undicht. Trotzdem bin ich mir nicht sicher, ob es hier zutrifft. :-)

Abstraktionen befassen sich mit Verhalten. Sofern das Verhalten Listkeine bestimmte Leistung angibt (was Java nicht tut), handelt es sich um ein Implementierungsdetail - dh irrelevant.

In Java können Sie keine Mindestleistung für Schnittstellen außerhalb der Dokumentation angeben, und mir sind keine Sprachen bekannt, die dies tun. Die Überprüfung durch den Compiler wäre unglaublich schwierig (unmöglich?). Ich kann einige Optionen sehen, wenn die Leistung ein Problem darstellt:

1. Dokumentieren Sie es in der Klasse / Schnittstelle, zu der die Listeninstanz gehört.
2. Erstellen Sie eine neue Schnittstelle - z. B. BinarySearchPerformantList(yuck!) -, die die Leistungsanforderungen der verschiedenen Methoden angibt.

Option 2 ist wahrscheinlich die bessere Abstraktion, bringt jedoch zusätzlichen Aufwand mit sich.

In Java gibt es eine RandomAccess- Schnittstelle, die als Liste mit im Allgemeinen konstanter Direktzugriffszeit (O (1) get, put usw.) definiert ist. Wenn Sie der Meinung sind, dass für Ihr Modul eine Liste mit diesen Leistungsmerkmalen erforderlich ist, sollten Sie RandomAccessstatt verwenden List. Wenn Sie nicht das Bedürfnis haben, diese Änderung vorzunehmen (und nur wenige tun dies), ist List möglicherweise nicht so undicht.

Sie haben Recht, eine Liste ist eine undichte Abstraktion. Die STL verwendet die Idee von Konzepten , um dieses spezifische Problem zu modellieren. Um Ihr Beispiel zu verwenden, ArrayListmodelliert eine einen Iterator mit wahlfreiem Zugriff, während eine LinkedList einen Vorwärtsiterator modelliert . Unterschiedliche Konzepte haben unterschiedliche Leistungsanforderungen, wodurch sie für unterschiedliche Algorithmen geeignet sind .