Description
@PeteX commented on Fri May 18 2018
Hello,
I was wondering if it would be possible to expand the System.Collections documentation so it spells out the big-O cost of the different operations. (Alternatively, it would be enough to state the underlying algorithm, because then the complexity is easy to determine.)
For example, I've just had a need for a sorted list of objects, which must support efficient insertion and deletion. I assume that SortedSet is a red-black tree and will do what I want, but this doesn't seem to be spelt out in the documentation. Another reasonable implementation would be a sorted list, which would support more efficient retrieval (by binary search) but less efficient insertion and deletion.
Thanks for all your work on the documentation and .NET Core itself.
Pete
Document details
⚠ Do not edit this section. It is required for docs.microsoft.com ➟ GitHub issue linking.
- ID: 26b9b071-fac4-e286-3dd0-107ed2687a03
- Version Independent ID: 2356f35d-5784-d763-125b-8c5625600a63
- Content: System.Collections.Generic Namespace
- Content Source: xml/ns-System.Collections.Generic.xml
- Service: unspecified
- Product: .net
- GitHub Login: @mairaw
- Microsoft Alias: mairaw
@svick commented on Sat May 19 2018
Some methods and types have their asymptotic complexity documented, so I think it would help if you listed where exactly do you think complexity is missing.
For example, the documentation for SortedSet<T>.Remove says that it's an O(log n) operation. Though the documentation for SortedSet<T>.Add does not mention complexity, so that's something that should be added.
As for the implementation, it is indeed a red-black tree.
@PeteX commented on Mon May 21 2018
@svick Yes some of the methods do mention complexity, but as you say not all do, and that's my point really.
Rather than add the asymptotic complexity to all the method descriptions, perhaps a simpler approach would be a summary paragraph in the description of each of the container classes. For example: 'SortedSet is a balanced tree structure which is designed to support O(log n) insertion, retrieval, and deletion.'
@ezzy1337 commented on Tue Oct 30 2018
I think this would be ridiculously helpful. I can't tell you the number of times I wish libraries would document this.
I wouldn't mind giving this issue a little bit of my time. Can PR's come in incrementally i.e. one per class or would you prefer one PR with all the changes.
@BillWagner commented on Tue Oct 30 2018
@ezzy1337 That would be awesome! One per class would be a great scope. That would help us review and merge in a timely fashion. Ping us if you have any questions as you start making changes.
@ezzy1337 commented on Tue Oct 30 2018
Just to be sure this is the .NET framework and not .NET Core right? I didn't see anything specifically spelling out which.
@BillWagner commented on Tue Oct 30 2018
@ezzy1337 To be useful, I think it would need to cover .NET Framework and .NET Core. Adding @safern who is responsible for the System.Collections namespace(s).
My thought is the big-O metrics should be similar across implementations, but he would be the authority.
@ezzy1337 commented on Tue Oct 30 2018
@BillWagner It looks like the specific documentation is going to live in the dotnet-api-docs repo i.e. for SortedSet.Remove. So after making the change in that repo is there a follow-up PR needed for this repo?
@BillWagner commented on Wed Oct 31 2018
@ezzy1337 A PR in dotnet-api-docs will update the docs. No need for a second PR. You can reference this issue there, using dotnet/docs#<issueNumber>
@dotnet-bot commented on Mon Jan 25 2021
This issue has been closed as part of the issue backlog grooming process outlined in #22351.
That automated process may have closed some issues that should be addressed. If you think this is one of them, reopen it with a comment explaining why. Tag the @dotnet/docs team for visibility.
@PeteX commented on Mon Jan 25 2021
This is still an issue with the documentation I believe. @BillWagner , I saw your comment that you would reopen issues when this was necessary. Would you be able to do that with this one please? I don't have the necessary access to do it myself. I'm also including @dotnet/docs but I'm not sure if that will work; Github's completion didn't recognise it as valid.
@BillWagner commented on Mon Jan 25 2021
reopening and moving to dotnet-api-docs