Martin
(Martin R)
1
The documentation of Array.dropLast() states that
Complexity: O(n), where n is the length of the sequence.
whereas the documentation of Array.dropLast(_:) states that
Complexity: O(n), where n is the number of elements to drop.
Does that mean that
let slice = someLargeArray.dropLast()
is less efficient than
let slice = someLargeArray.dropLast(1)
?
Actually I would expect a O(1) implementation (independent of array size and number of elements to drop) since arrays are RandomAccessCollections which allow O(1) index calculations.
O(1) would only be possible if it's an Array of a trivial type, such as Int. If it's an array of e.g. class objects, they need to each be released/destroyed.
edit: scratch that, I was thinking of a mutating drop. Yes, O(n) in documentation is surprising. CC @nnnnnnnn in case he knows.
timv
(Tim Vermeulen)
3
The Sequence implementation of dropLast(n) has a time complexity of O(n), so I'm guessing that the Array.dropLast documentation has (incorrectly) been "inherited" from Sequence.dropLast. Array.dropLast absolutely has a time complexity of O(1).
nnnnnnnn
(Nate Cook)
4
Yep, that's the case—those are only declared on either Sequence or Collection, so they need notes about the different performance on BidirectionalCollection and RandomAccessCollection.
Martin
(Martin R)
5
1 Like
