Scala中的递归集合,例如List

Question

目的是使用Scala集合,其中不需要迭代或递归计算大小.

例如,List证明是递归构造(例如考虑/sf/answers/573847851/),并且为了获得大小,有必要迭代它; 即O(N)对列表中元素数量的操作.

那么要问这个操作是哪个集合O(1)？非常感谢.

Answer 1

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实现.