Czy interfejs listy jest nieszczelną abstrakcją?

Jeśli mam zmienną zawierającą List, może zawierać obiekty wielu różnych typów, np . ArrayListLub LinkedList. Różnica między a LinkedLista ArrayListjest dość duża. Duże zachowanie O metod różni się znacznie. Na przykład sortowanie Listi używanie go do wyszukiwania binarnego jest w porządku, ArrayListale nie ma sensu z LinkedList.

Nie powiedziałbym tak.

Nieszczelna abstrakcja to taka, która zmusza cię do radzenia sobie ze szczegółami implementacji, które ma abstrahować. Ale wydajność zawsze różni się w zależności od implementacji, więc jeśli uważasz to za przeciekające, nie ma nie przeciekających abstrakcji.

Jeśli coś zostanie zadeklarowane jako Listbez dodatkowej dokumentacji, należy rozumieć, że po prostu nie ma gwarancji wydajności, a jeśli zamierzasz zrobić z tym cokolwiek wrażliwego na wydajność, powinieneś zrobić kopię i pracować z tym.

Nie należy również zapominać, że jest jeszcze bardziej ogólny interfejs, który jest często wystarczające funkcjonalność i nie kusić, aby jak wiele założeń dotyczących wydajności: Collection.

Wszystkie nietrywialne abstrakcje są do pewnego stopnia nieszczelne. To powiedziawszy, nie jestem do końca pewien, czy to dotyczy tutaj. :-)

Abstrakcje dotyczą zachowania. O ile zachowanie nie określa konkretnej wydajności (której Listnie ma Java ), jest to szczegół implementacyjny - tzn. Nieistotny.

Java nie pozwala ci określić minimalnej wydajności interfejsów poza dokumentacją i nie znam żadnych języków, które by to zrobiły - weryfikacja kompilatora byłaby niezwykle trudna (niemożliwa?). Widzę kilka opcji, jeśli wydajność stanowi problem:

1. Dokumentuj to w klasie / interfejsie, do którego należy instancja listy.
2. Utwórz nowy interfejs - np. BinarySearchPerformantList(Fuj!) - który określa wymagania wydajnościowe różnych metod.

Opcja 2 jest prawdopodobnie lepszą abstrakcją, ale wiąże się z dodatkowymi kosztami.

W Javie istnieje interfejs RandomAccess , który jest zdefiniowany jako lista z ogólnie stałym czasem losowego dostępu (O (1) get, put itp.). Jeśli uważasz, że Twój moduł wymaga listy z tymi cechami wydajności, rozważ użycie RandomAccesszamiast niego List. Jeśli nie czujesz potrzeby dokonywania tej zmiany (a niewielu to robi), być może Lista nie jest tak nieszczelna.

Masz rację, lista jest nieszczelną abstrakcją. STL wykorzystuje ideę pojęć do modelowania tego konkretnego problemu. Na przykład, ArrayListmodeluje iterator o swobodnym dostępie , a LinkedList modeluje iterator do przodu . Różne koncepcje mają różne wymagania dotyczące wydajności, co czyni je odpowiednimi dla różnych algorytmów .