Рекурсивные коллекции в Scala, такие как List

Цель состоит в том, чтобы использовать коллекцию Scala, размер которой не нужно вычислять итеративно или рекурсивно.

Например, List оказывается рекурсивной конструкцией (рассмотрите, например, https://stackoverflow.com/a/8197826/3189923 ), и для получения размера необходимо перебрать его; а именно операция O(N) над количеством элементов в списке.

Таким образом, чтобы спросить, для каких коллекций эта операция O(1)? Огромное спасибо.


collections scala recursive-datastructures
person elm    schedule 31.01.2014    source источник
comment
Недавно я нашел доклад Даниэля Спивака, он говорил о функциональных структурах данных в scala. Вот ссылка infoq.com/presentations/Functional-Data-Structures- in-Scala Возможно, вы сможете извлечь нужные вам знания.   -  person tgr    schedule 31.01.2014

Ответы (2)


arrow_upward
7
arrow_downward

Стоимость метода size для основных неизменяемых коллекций (согласно быстрому просмотру кода):

Seq:
  LinearSeq:
    List - O(N)
    Stream - O(N)*
    Queue - O(N) // Implemented using List
    Stack - O(N)* // Implemented using List, with additional complexity
  IndexedSeq:
    Vector - O(1)
    NumericRange - O(1)
    Array - O(1) // WrappedArray, ArrayOps
    String - O(1) // WrappedString, StringOps
    Range - O(1)
Set:
  HashSet - O(1) // HashSet.HashTrieSet
  TreeSet - O(N) // RedBlackTree.count - recursive with stack usage 
  BitSet - O(Max)* // fast enough. O(1) for collections of small ints
  ListSet - O(N)
Map:
  HashMap - O(1) // HashMap.HashTrieMap
  TreeMap - O(N) // RedBlackTree.count - recursive with stack usage
  ListMap - O(N)

Поток

Из документации:

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

Куча

Stack#length сложность намного хуже, чем List#length сложность: она создает N новых объектов для повторения Stack.

Битсет

BitSet предназначен для коллекций небольших целых чисел.

Сложность BitSet#size зависит от максимального элемента, а не от количества элементов. Это около O(Max/64). См. также реализация BitSet#size< /а>.

TreeSet/TreeMap

Я не уверен насчет сложности TreeSet и TreeMap, это похоже на рекурсию с использованием стека (а не на хвостовую рекурсию). См. реализация RedBlackTree.count .

person senia    schedule 31.01.2014

arrow_upward
1
arrow_downward

  • Для неизменяемых коллекций Vector имеет постоянную size операцию
  • Изменяемый Array имеет постоянную операцию size
  • Для изменяемых коллекций и ListBuffer, и ArrayBuffer имеют постоянные size операции.
person 0__    schedule 31.01.2014