I agree with all of the points made by Michał and Paul. Additionally, most functions will never need to specify this information. In the few cases where you might want to specify this information it seems like it would be very reasonable to use module docs and function docs. This is especially true because asymptotic time _isn't_ the most useful way to measure immutable data structures. Often you'll want to look at both asymptotic and amortized time complexities. But even if we set amortized time to the side for a second, how would you document a data structure that internally uses a list until the list size reaches a certain amount and then switches to a HAMT with a branching factor of 32? Do you say that searching this data structure is O(n) when n < 32 and O(log32(n)) when n >= 32? In my mind putting this information in the module doc is clearer and allows me to write a full explanation.
It seems to me that the core problem is communicating relative performance of different data structures and algorithms. I don't think this proposal is needed to solve that problem and it creates more complexities than benefits. On Fri, Jul 19, 2019 at 7:26 AM Mário Guimarães < mario.luis.guimar...@gmail.com> wrote: > > The idea of this proposal is to document time and space complexity of > collections in a more structured / organized way instead of being missing > or spread opportunistically here and there throughout the documentation. > > I also think that such information could be presented in a proper section > at the top part of a collection's module documentation before the function > list. > > Using `@doc` annotations on functions are not strictly necessary, but > provide a way to capture that information that is ameanable for > post-processing, for example, to generate a table at the top of the > documentation page. Moreover, they do not need to be presented next to the > documentation of the functions they annotate. > > > The Big-O annotation practice is not to write "O(2n+3)" but to reduce this > to its pattern of asymptotic growth, which in this case is simply "O(n)". > > This means that I totally agree that complex mathematical formulas do not > belong to this documentation. > > Among the several existing predictors, Big-O is the one generally used and > that people are most aware of. It is also the one that predicts the > worst-case asymptotic performance an algorithm can get when systems are put > under the stress of large inputs. Adding other indicators introduces > unnecessary complexity and confusion, which obviously is not what we want > in our documentation. > > In general, the "n" relates to the number of elements in the collection, > and I suppose that in cases of functions involving two collections, they > can be annotated with something like "O(n+m)", where "n" and "m" are the > number of elements in each collection. > > These are very simple expressions every software developer should know or > be interested to learn for the sake of understanding algorithms better and > the quality of the software systems they write. > > > > sexta-feira, 19 de Julho de 2019 às 11:32:22 UTC+1, Fernando Tapia Rico > escreveu: >> >> To give a bit more context: the top level documentation for Enum, >> Keyword, List, Map, MapSet, and Stream already contain some "*hints"* about >> time complexity :) >> >> On Friday, July 19, 2019 at 12:28:56 PM UTC+2, Wiebe-Marten Wijnja wrote: >>> >>> Having read all of the replies, I like the suggestion to add simple >>> readable documentation to the data structures' module docs the best. >>> >>> Adding new documentation metadata seems to me not worth it. Besides the >>> already mentioned problems, I would like to mention that >>> complexity-documentation is not *that* structured: >>> >>> - Besides Big-O, there is Big-Omega and Little-o, which are also very >>> useful and relatively common in literature. Do we also need to add new >>> metadata names for those? >>> - Time-complexity and Space-complexity are by no means the only >>> complexities that are being measured for data structures. Do we also need >>> to add new metadata names for e.g. communication complexity, >>> - What about amortized complexities? >>> - In regards to *what* is the complexity measured? (i.e. "what is `n` >>> in O(2n+3)"?) >>> >>> And that, combined with the fact that I think it is important to also >>> accommodate people who are new to this mathematical way of writing >>> algorithmic complexities, makes me conclude that it is a bad idea to create >>> a rigid structured way for it, and that adding some humanly-readable >>> unstructured documentation for common operations on commonly-used >>> datastructures would be the way to go. These unstructured documentation >>> snippets might be accompanied by their formal complexity notations, but >>> should not only consist of these. >>> >>> ~Qqwy/Marten >>> >>> On Thursday, July 18, 2019 at 6:36:04 PM UTC+2, Mário Guimarães wrote: >>>> >>>> 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/d8bd66d7-4328-4c2d-8d9b-19002a8d6bc9%40googlegroups.com > <https://groups.google.com/d/msgid/elixir-lang-core/d8bd66d7-4328-4c2d-8d9b-19002a8d6bc9%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- Chris -- 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/CAGjNwxpQbs4awwSwfkOuTjY%3DNHaksMShO_%3DUxiyuvOzGvJNBgw%40mail.gmail.com.
