Czy interfejs listy jest nieszczelną abstrakcją?

9

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.

java object-oriented-design Palisada
źródło
Co oznacza „duże O”?
Tulains Córdova,
@ user61852 en.wikipedia.org/wiki/Big_O_notation
Paling

Odpowiedzi:

25

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.

Michael Borgwardt
źródło
9
Jest nawet bardziej ogólny interfejs, który jest często wystarczające funkcjonalność: Iterable.
emory
Oczekiwane są różnice w wydajności między różnymi implementacjami. Np. Istnieją różnice między Vector a ArrayList, ale operacja get na LinkedList wydaje się dziwna.
Paling
17

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.

Vaughandroid
źródło
1
+1. Technicznie tak, lista jest nieszczelną abstrakcją , ale tak samo jak Obiekt do ukrywania złożoności związany z używaniem equalsdo porównywania obiektów.
Neil,
2
@Neil Myślę, że jest dyskusyjna ... Ponieważ abstrakcja nie wspomina o wydajności, nie sądzę, aby zawiodła w tym przypadku (jak argumentowałem). Powiedziałbym, że jeśli myślisz o wydajności, potrzebujesz innej / węższej abstrakcji. Będzie edytować, aby o tym wspomnieć.
vaughandroid
To zależy od tego, co ukrywasz. Czy złożoność użytkowania jest związana z użytkowaniem i wdrażaniem pamięci? Ponieważ jeśli jest to klasa abstrakcyjna, jedna lub więcej z tych złożoności ukrywa się w taki czy inny sposób.
Neil,
Grałem około wiele lat wstecz realizacji odmianę wariantu 2 przy użyciu interfejsów markerów jak LinearSpacei LogarithmicTime, a następnie deklarowania klas jak public class BinarySearch : ISearchStrategy<T>, LogarithmicTime. Inne klasy mogą przyjmować parametry takie jak public T find<T, S>(IList<T> list, S strategy) where S : ISearchStrategy<T>, LogarithmicTime { }wymuszanie ograniczeń wydajności.
Lucas,
2
Jeśli chodzi o artykuł Joela Spolsky'ego, myślę, że jest „do pewnego stopnia nieszczelny”. Zobacz następujący cytat z tego artykułu: „Jeśli spóźniłeś się z administratorami systemu w swojej firmie i ukarali cię podłączeniem Cię do przeciążonego koncentratora, tylko niektóre twoje pakiety IP przejdą i TCP zadziała, ale wszystko będzie działać bądź naprawdę powolny ”Myślę, że to dotyczy
programista Amish
4

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.

MikeFHay
źródło
1

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 .

Matthew Finlay
źródło