Асимптотическое поведение методов Scala

Question

Где-нибудь я могу найти ожидаемые время и пробел сложности операций с коллекциями, такими как HashSet, TreeSet, List и т. Д.?

Ожидается ли, что кто-нибудь узнает это по свойствам самих абстрактных типов данных?

Я знаю о Характеристики производительности для коллекций Scala , но здесь упоминаются только некоторые очень основные операции. Возможно, остальные операции для этих коллекций построены исключительно из небольшого базового набора, но тогда, кажется, я просто должен знать, что они реализовали их таким образом?

Answer 1

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

Большинство других массовых операций над коллекциями (операций, которые обрабатывают каждый элемент в коллекции): O(n),поэтому они там не упоминаются.Примерами являются filter, map, foreach, indexOf, reverse, find ...

Методы, возвращающие итераторы или потоки типа combinations и permutations, обычно O(1).

Методы, включающие 2 набора, обычно O(max(n, m)) или O(min(n, m)).Это zip, zipAll, sameElements, corresponds, ...

Методы union, diff и intersect: O(n + m).

Варианты сортировки, естественно, O(nlogn).groupBy - O(nlogn) в текущей реализации.indexOfSlice использует алгоритм KMP и равен O(m + n), где m и n являются длинами строк.

Методы, такие как +:, :+ или patch, обычно являютсяO(n) также, если только вы не имеете дело с конкретным случаем неизменяемой коллекции, для которой рассматриваемая операция более эффективна - например, добавление элемента к функционалу List или добавление элемента к Vector.

Методы toX обычно O(n), так как они должны выполнять итерации всех элементов и создавать новую коллекцию.Исключение составляет toStream, которое создает коллекцию лениво - так что это O(1).Кроме того, всякий раз, когда X является типом коллекции, toX просто возвращает this, будучи O(1).

Реализации итератора должны иметь O(1) (амортизированные) next и hasNextоперации.Создание итератора должно быть наихудшим O(logn), но в большинстве случаев O(1).

Answer 2

Рабочие характеристики других методов действительно трудно утверждать.Рассмотрим следующее:

• Все эти методы реализованы на основе foreach или iterator и обычно на очень высоких уровнях в иерархии.Например, Vector map реализовано на collection.TraversableLike.Чтобы добавить оскорбление ране, какая реализация метода используется, зависит от линеаризации наследования класса.Это также относится к любому методу, называемому помощником.Это произошло до того, как изменения привели к непредвиденным проблемам с производительностью.Поскольку foreach и iterator являются O(n), любая улучшенная производительность зависит от специализации других методов, таких как size и slice.
• Для многих из них существует дополнительная зависимость отхарактеристики производительности предоставленного построителя, который зависит от сайта вызова, а не от сайта определения.

Таким образом, в результате место, где метод определен - и задокументирован - неиметь достаточно информации для определения своих характеристик производительности и может зависеть не только от того, как другие методы реализованы наследующей коллекцией, но даже от характеристик производительности объекта Builder, полученного из CanBuildFrom, который передается в Звоните на сайт .

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