search

dotnet / dotnet-api-docs

.NET API reference documentation (.NET 5+, .NET Core, .NET Framework)
https://docs.microsoft.com/dotnet/api/
Other
718 stars 1.56k forks source link

It will be useful to have algorithmic complexity of standard operations provided by the .NET library #5179

Open gewarren opened 3 years ago

gewarren commented 3 years ago

Issue moved from MicrosoftDocs/feedback#3306

From @katoch on Wednesday, December 2, 2020 3:23:26 AM

Is your feature request related to a problem? Please describe. I'm surprised that most microsoft references for .NET library do not provide complexity information for standard operations. In comparison the C++ standard library documentation has this for all standard library operations.

Describe the solution you'd like A brief mention of space/time complexity for operations will be useful in determining optimal solutions while writing code in .NET. The references are not complete without this information in my opinion.

Describe alternatives you've considered A clear and concise description of any alternative solutions or features you've considered.

Additional context Add any other context or screenshots about the feature request here.

gewarren commented 3 years ago

Issue moved from MicrosoftDocs/feedback#3306

From @welcome[bot] on Wednesday, December 2, 2020 3:23:28 AM

Thank you for creating the issue! One of our team members will get back to you shortly with additional information. If this is a product issue, please close this and contact the particular product's support instead (see https://support.microsoft.com/allproducts for the list of support websites).

Dotnet-GitSync-Bot commented 3 years ago

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

svick commented 3 years ago

Which operations are you talking about specifically? Because some already provide their time complexity, e.g. the documentation for List<T>.Insert says:

This method is an O(n) operation, where n is Count.

gewarren commented 3 years ago

@katoch Please see the question that @svick posed ⬆

katoch commented 3 years ago

Ok, I think the documentation does list the complexity of operation in the very end in the ‘Remarks’ section. I think it might be useful to have a separate complexity section which just provides that information. I was looking at the documentation for KeyedCollection .

On Sun, Dec 20, 2020 at 7:24 PM Genevieve Warren notifications@github.com wrote:

@katoch https://github.com/katoch Please see the question that @svick https://github.com/svick posed ⬆

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/dotnet/dotnet-api-docs/issues/5179#issuecomment-748735669, or unsubscribe https://github.com/notifications/unsubscribe-auth/AADXVRV6Y7D5BJANIGWFXUDSV25XNANCNFSM4U6TCLBQ .

eiriktsarpalis commented 3 years ago

I think it might be useful to have a separate complexity section which just provides that information.

Does the C++ standard library have a section like that? At quick glance I couldn't find something. I agree we could have included this information in some places (collections jump to mind), but in others it's probably counterproductive.

svick commented 3 years ago

@eiriktsarpalis The documentation at cppreference.com does, for example:

udlose commented 1 week ago

Which operations are you talking about specifically? Because some already provide their time complexity, e.g. the documentation for List<T>.Insert says:

This method is an O(n) operation, where n is Count.

and it is not clear which complexity metric this is referring to: Time Complexity or Space Complexity (memory usage). One can only assume it is Time Complexity. Which brings up another issue: Space Complexity is missing everywhere. This is extremely important for Data Types and methods/extension methods that are considered "go-to's" for performance tuning nowadays with performance efforts very frequently focused on reduction of memory consumption. The only other way to accomplish this is to write benchmarks using BenchmarkDotNet to try and measure memory consumption. However, this technique is both time-consuming and, more importantly, results depend on how well (comprehensive) the benchmarks are written. Most devs aren't going to spend the time to write comprehensive benchmarks considering that writing these benchmarks is time consuming. Thus, they end up possibly selecting the wrong type or method for their use-case.