Time taken on Collection.underestimatedCount?

Using Swift
1

Sequence.underestimatedCount is supposed to work at O(1) time, according to the docs on Apple’s developer website. On the other hand, Collection.count works at O(n) time, except for RandomAccessCollection where it can work at O(1) time. I’ve been playing around with creating various Collection types, and it seem that their underestimatedCount has a default implementation that just dumps to count, even when the latter is O(n)!

I think that underestimatedCount should call count only for RandomAccessCollection, while Collection and BidirectionalCollection call isEmpty as needed. Is this a good idea? Should I post a bug report (somewhere)?

···

—
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com

2

Hi Daryle,

Good spot! This is definitely a bug. The documentation on Sequence should read something different (though what it ought to say is somewhat debatable…).

Could you file a bug on bugs.swift.org?

Thanks!

···

On Dec 29, 2017, at 17:54, Daryle Walker via swift-users <swift-users@swift.org> wrote:

Sequence.underestimatedCount is supposed to work at O(1) time, according to the docs on Apple’s developer website. On the other hand, Collection.count works at O(n) time, except for RandomAccessCollection where it can work at O(1) time. I’ve been playing around with creating various Collection types, and it seem that their underestimatedCount has a default implementation that just dumps to count, even when the latter is O(n)!

I think that underestimatedCount should call count only for RandomAccessCollection, while Collection and BidirectionalCollection call isEmpty as needed. Is this a good idea? Should I post a bug report (somewhere)?

—
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users

3

It’s SR-6693 <Issues · apple/swift-issues · GitHub; (“Collection.underestimatedCount shouldn't call .count when the latter isn't O(1).").

···

—
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com

On Jan 2, 2018, at 11:29 PM, Ben Cohen <ben_cohen@apple.com> wrote:

Hi Daryle,

Good spot! This is definitely a bug. The documentation on Sequence should read something different (though what it ought to say is somewhat debatable…).

Could you file a bug on bugs.swift.org <Issues · apple/swift · GitHub?

Thanks!

On Dec 29, 2017, at 17:54, Daryle Walker via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:

Sequence.underestimatedCount is supposed to work at O(1) time, according to the docs on Apple’s developer website. On the other hand, Collection.count works at O(n) time, except for RandomAccessCollection where it can work at O(1) time. I’ve been playing around with creating various Collection types, and it seem that their underestimatedCount has a default implementation that just dumps to count, even when the latter is O(n)!

I think that underestimatedCount should call count only for RandomAccessCollection, while Collection and BidirectionalCollection call isEmpty as needed. Is this a good idea? Should I post a bug report (somewhere)?