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.
