Является ли интерфейс List утечкой абстракции?

9

Если у меня есть переменная, содержащая a, Listона может содержать объекты разных типов, например, ArrayListили LinkedList. Разница между а LinkedListи ArrayListдовольно большая. Поведение больших О методов сильно отличается. Например, сортировка Listи последующее использование его для выполнения бинарного поиска вполне подходит для, ArrayListно не имеет смысла для a LinkedList.

java object-oriented-design частокол
источник
Что значит "большой О"?
Тулаинс Кордова
@ user61852 ru.wikipedia.org/wiki/Big_O_notation
Paling

Ответы:

25

Я бы так не сказал.

Утечка абстракции - это та, которая заставляет вас иметь дело с деталями реализации, которые она должна абстрагировать. Но производительность всегда различается между реализациями, поэтому, если вы считаете это утечкой, то нет никаких утечек абстракций.

Если что-то объявлено как Listбез дополнительной документации, следует понимать, что просто нет никаких гарантий относительно производительности, и если вы собираетесь делать с этим что-либо чувствительное к производительности, вы должны сделать копию и работать с этим.

Кроме того , не стоит забывать , что есть еще более общий интерфейс , который часто бывает достаточно функциональности и не искушать вас , чтобы сделать так много предположений о производительности: Collection.

Майкл Боргвардт
источник
9
Существует еще более общий интерфейс , который часто бывает достаточно функциональности: Iterable.
Эмори
Ожидаются различия в производительности между различными реализациями. Например, существуют различия между Vector и ArrayList, но операция get для LinkedList просто кажется странной.
Paling
17

Все нетривиальные абстракции, в какой-то степени, негерметичны. Тем не менее, я не совсем уверен, что это применимо здесь. :-)

Абстракции связаны с поведением. Если в поведении не указана конкретная производительность (а в Java Listэто не так), это - деталь реализации, т.е. не имеет значения.

Java не позволяет вам указывать минимальную производительность для интерфейсов вне документации, и я не знаю ни одного языка, который бы это сделал - компилятору было бы невероятно сложно (невозможно?) Проверить это. Я могу увидеть несколько вариантов, если производительность является проблемой:

  1. Документируйте это в классе / интерфейсе, к которому будет принадлежать экземпляр списка.
  2. Создайте новый интерфейс - например BinarySearchPerformantList(yuck!) - который определяет требования к производительности различных методов.

Вариант 2, вероятно, является лучшей абстракцией, но имеет дополнительные издержки.

vaughandroid
источник
1
+1. Технически да, List - это утечка абстракции , но так же и Object для сокрытия сложности, связанной с использованием equalsдля сравнения объектов.
Нил
2
@Neil Я думаю , что это спорно ... Так как абстракция , не говоря уже о производительности я не думаю , что это провал в этом случае (как я утверждал). Я бы сказал, что если вы думаете о производительности, вам нужна другая / более узкая абстракция. Отредактирую, чтобы упомянуть об этом.
vaughandroid
Я полагаю, это зависит от того, что вы скрываете. Сложность в использовании или в использовании памяти и ее реализации? Потому что, если это абстрактный класс, одна или несколько из этих сложностей так или иначе скрываются.
Нейл
Я играл много лет назад реализации вариации варианты 2 с использованием маркеров интерфейсов , как LinearSpaceи , LogarithmicTimeа затем объявить классы , как public class BinarySearch : ISearchStrategy<T>, LogarithmicTime. Другие классы могут принимать такие параметры, как public T find<T, S>(IList<T> list, S strategy) where S : ISearchStrategy<T>, LogarithmicTime { }принудительное ограничение производительности.
Лукас
2
Если мы подойдем к статье Джоэла Спольски, я думаю, что она «в некоторой степени утечка». См. Следующую цитату из статьи: «Если вы были недовольны системными администраторами в вашей компании, и они наказали вас, подключив вас к перегруженному концентратору, только некоторые из ваших IP-пакетов пройдут, и TCP будет работать, но все будет работать будь очень медленным "Я думаю, что это применимо
Амишский Программист
4

В Java есть интерфейс RandomAccess, который определяется как список с обычно постоянным временем произвольного доступа (O (1) get, put и т. Д.). Если вы чувствуете, что вашему модулю требуется список с этими характеристиками производительности, рассмотрите возможность использования RandomAccessвместо List. Если вы не чувствуете необходимости вносить это изменение (а это делают немногие), то, возможно, List не так уж и плох.

MikeFHay
источник
1

Вы правы, список - это дырявая абстракция. STL использует идею концепций для моделирования этой конкретной проблемы. Чтобы использовать ваш пример, ArrayListмоделируется итератор произвольного доступа, а LinkedList моделирует прямой итератор . Различные концепции имеют разные требования к производительности, что делает их подходящими для разных алгоритмов .

Мэтью Финлей
источник