I'd like to actually argue against this addition. For one — it adds complexity to the documentation - you have to know what the big-O notation means in the first place — I'd argue it will make the documentation less approachable for people without formal CS education. It only becomes worse with some of the more complex data structures that feature "amortised" or "expected" big-O performance. To give just one example - all operations on maps implemented as HAMT are rather complex to express in this notation and would probably need a paragraph if not more to explain.
Secondly, it might prove problematic in a way that it bounds the standard library not to change those in the future. Changing an implementation where it would affect the complexity of the function could be considered a breaking change. I believe that for that reason, for example, the Rust standard library does not feature such documentation in general. But there's also a much bigger issue and that's if this is actually useful in real programs beyond most simple divagations. Modern computers with out-of-order CPU execution, expensive and complex caching mechanisms and other such features mean that the classical notion of big-O notation rarely directly reflects on real-world performance. Even worse if the function at hand allocates - should it also consider the potential impact it could have on garbage collection? There are numerous algorithms that theoretically should be worse, but are much better in practice. I fear that adding such information would lead to people deciding which potential implementation is better just by looking at that documentation instead of benchmarking for their own use case, which is the only reliable method of testing for performance. To summarise - I think this will only add additional, superfluous information to the documentation that is of questionable usefulness but that might prove problematic in the future. Michał. On 19 Jul 2019, 00:01 +0200, José Valim <jose.va...@plataformatec.com.br>, wrote: > I like that. Maybe time_complexity / space_complexity for clarity. > > > José Valim > www.plataformatec.com.br > Skype: jv.ptec > Founder and Director of R&D > > > > On Thu, Jul 18, 2019 at 11:49 PM Mário Guimarães > > <mario.luis.guimar...@gmail.com> wrote: > > > I would suggest then to have > > > > > > @doc time: "O(n)" > > > > > > and > > > > > > @doc space: "O(n^2)" > > > > > > > > > to clearly refer to time and space complexity of the function. > > > > > > Mário > > > > > > > > > quinta-feira, 18 de Julho de 2019 às 17:36:04 UTC+1, Mário Guimarães > > > escreveu: > > > > Hi, > > > > > > > > I find this can be useful in selecting the collections and their > > > > manipulating functions to be used in our code. > > > > > > > > The case is that in an immutable language it may not be evident what is > > > > the O(...) of the insert, read, update, delete and sort, in our > > > > collections. > > > > > > > > For example, what is the complexity of sorting an immutable enumerable > > > > via `Enum.sort`? I really do not know. > > > > > > > > This could be documented with a table at the start of the documentation > > > > for the collection. > > > > > > > > This effort could be decomposed in as many issues as the number of > > > > collections to document. > > > > > > > > Experienced people may know many of these Big-O details, but for > > > > newcommers to Elixir (and Erlang) it could be very helpful. > > > > > > > > Thanks > > > > Mário > > > -- > > > You received this message because you are subscribed to the Google Groups > > > "elixir-lang-core" group. > > > To unsubscribe from this group and stop receiving emails from it, send an > > > email to elixir-lang-core+unsubscr...@googlegroups.com. > > > To view this discussion on the web visit > > > https://groups.google.com/d/msgid/elixir-lang-core/7e570c16-9cbc-44af-a42b-18b4f39f2742%40googlegroups.com. > > > For more options, visit https://groups.google.com/d/optout. > -- > You received this message because you are subscribed to the Google Groups > "elixir-lang-core" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to elixir-lang-core+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/elixir-lang-core/CAGnRm4%2BX2LWZ2Z4xDxa67ovo8rtWOJjVqc_8oy5ukWoE-kiZCg%40mail.gmail.com. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "elixir-lang-core" group. To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-core+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/70b115b3-2d8b-4e61-a837-0a7a224b4ef8%40Spark. For more options, visit https://groups.google.com/d/optout.
