I agree with all the previous points about why time/space complexity is useful info in general But at the same time, and remembering other proposals that I see going through this mailing list, I often see that the decision goes a lot towards preserving the clarity of the documentation, especially when it comes to less experienced developers.
I think a good compromise would be to add this information to the collection module top-level documentation, or a separate page for example. This has already been suggested a couple of times in this thread. But documenting complexity for every collection function individually seems like it won't be very helpful. I'd argue that, if you know what time & space complexity means, then it's likely that you already have at least some understanding of how that works, and you'll know at least the basics, rendering that extra documentation less interesting for you. Or at the very least, you'll know that the concept exists, and that for certain use cases you may have to think about what the most appropriate structure will be. At that point, you can do any additional research outside of the Elixir documentation. And for those who don't know the meaning, it will just be an additional barrier to their understanding of the documentation. On Fri, Jul 19, 2019 at 10:38 AM Mário Guimarães < mario.luis.guimar...@gmail.com> wrote: > > I like the proposed names of time_complexity and space_complexity; it > can't be more clear. > > Some points in clarifying Big-O: > - it captures the time and space performance of algorithms > - time and space are quality factors, thus improving them does not break > the API of the algorithm > - it is really useful as an indicator of algorithm performance in the > presence of large inputs (asymptotic performance) > - as such, it is really useful in predicting the performance of algorithms > used large software systems, like those on the Internet > - it guides the design and choice of algorithms > - it educates people on algorithm design > - and because of all this, it is thought in every serious data structures > and algorithms course > > No known computer design can automatically improve the asymptotic > performance of algorithms; what it can do, is to raise the bar on the size > of the input that an algorithm can take before it starts to show its > asymptotic behavior > > As the previous points stated, Big-O is a guide of asymptotic performance > on large inputs; obviously, if the inputs are small, then most competing > algorithms will show equivalent performance. It is for large inputs that > Big-O is a great aid on choosing among competing algorithms. > > Big-O is never an excuse to avoid testing our programs for their real > performance; again, Big-O is just an indicator of what this might be for > large inputs, and overall, a great tool to base the initial design of our > programs before tuning and realease to the world. > > Functional programming is penetrating a world in which mutable data > structures and their algorithms dominate, and for which Big-O indicators > are very well documented and accessible. This is not the case for the > Big-Os of immutable data structures and their algorithms, whose > implementation details are yet somewhat obscure to the general audience. > > In short, I think this will be a great addition to the Elixir > documentation. > > Thanks > Mário > > quinta-feira, 18 de Julho de 2019 às 23:37:59 UTC+1, Michał Muskała > escreveu: >> >> 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...@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.lui...@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-l...@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 >>> <https://groups.google.com/d/msgid/elixir-lang-core/7e570c16-9cbc-44af-a42b-18b4f39f2742%40googlegroups.com?utm_medium=email&utm_source=footer> >>> . >>> 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-l...@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 >> <https://groups.google.com/d/msgid/elixir-lang-core/CAGnRm4%2BX2LWZ2Z4xDxa67ovo8rtWOJjVqc_8oy5ukWoE-kiZCg%40mail.gmail.com?utm_medium=email&utm_source=footer> >> . >> 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/7442e39a-5926-4b80-8a9d-fd28173bb7ba%40googlegroups.com > <https://groups.google.com/d/msgid/elixir-lang-core/7442e39a-5926-4b80-8a9d-fd28173bb7ba%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- Best, Miguel Palhas -- 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/CAEmrurp%3DrTRvMBQkcFuMumfbLUWWSB9DyysJqgYRmQCHtO5LVQ%40mail.gmail.com.
