[SR-6693] Collection.underestimatedCount shouldn't call .count when the latter isn't O(1). #49242
Comments
|
O👎 / O(n) strikes again! |
|
The documentation has already been updated to reflect actual practice by Thomas Di Meco in PR#13111. |
|
Comment by Daryle Walker (JIRA) I know having .underestimatedCount blindly forward to .count is current practice; I’m also saying keeping it that way is wrong. In old versions of Swift, was it possible to specialize on RandomAccessCollection over the others? If not, maybe declaring Collection.underestimatedCount as O👎 was a retroactive justification. We’re not limited by that now, and we have an alternative (using .isEmpty) to retain O(1). As-is, there’s no advantage to using .underestimatedCount over .count, not even at least speed. |
|
Changing behavior now presents the possibility of silently changing user code in very difficult-to-debug ways. I would be strongly opposed to such an action. |
Additional Detail from JIRA
md5: 1c211f9ba3face77d56f58149370eaa0
Issue Description:
Browsing the Collection source code at Apple's GitHub site, I noticed that the default implementation of Collection.underestimatedCount always forwards to .count. The "count" method is O👎 except when it's O(1) for random-access collections. Meanwhile, Sequence.underestimatedCount is supposed to be O(1).
So .underestimatedCount should forward to .count only for RandomAccessCollection. The wimpier, traversal-wise, Collection types should forward to .isEmpty instead. That keeps all Collection.underestimatedCount variants at O(1). Using .isEmpty limits the results of .underestimatedCount to 0 or 1, but that's OK since it's an under-estimate.
The text was updated successfully, but these errors were encountered: