Oh, that was already explained: to have the O(...) annotation at a well structured place that can be used for post-processing; for example, to generate a table collecting those O(...) annotations, to be placed at a well known point, like the top of the collection's module.
This is not an addition to the language per se, because @doc can be used already in the form of @doc x: term This is an addition to the documentation of the collections that come with Elixir, and not only on the functions of those collections, because for example "sort" comes from "Enum" only and deserves to have its complexity documented for the different collections; in this case, documenting sort in a complexity section on the top of the collection document is perhaps the best place. Chris Keathley <c...@keathley.io> escreveu no dia sexta, 19/07/2019 à(s) 16:19: > > What's the difficulty of annotation like this, which can be complemented > if necessary with an additional explanation in the module or function > documentation? > > What's the difficulty in just using module docs and function docs? If > additional information would go in the module and function documentation > why not put everything there? I'm not saying that we shouldn't communicate > this information when its useful. But it hasn't been proven to me that we > need an addition to the language to accomplish that goal. > > On Fri, Jul 19, 2019 at 11:00 AM Mário Guimarães < > mario.luis.guimar...@gmail.com> wrote: > >> This proposal is to document the complexity for the collections that come >> with Elixir and the functions that manipulate them. There aren't many of >> these collections, they are the simplest collections that can exist from >> the user perspective, they are very distinct, and so, I think that the most >> simplified "O(...)" is enough to compare across them. For anyone >> creating new collections outside the standard library, they choose to >> document their collections as they wish. >> >> The case of average running times I believe will depend on the >> application domain, so it is better dealt by benchmarking the application >> for the typical inputs in its domain. >> >> The case of "O(min(n, W))" can be well complemented by explaining what >> "W" is in the function's documentation, in case such uncommon variables >> stay after simplification of the "O(...)". Again, I do not think that >> Elixir collections will need these. >> >> What's the difficulty of annotation like this, which can be complemented >> if necessary with an additional explanation in the module or function >> documentation? >> >> @doc time_complexity: "O(n) if n < 32, otherwise O(log32(n))" >> >> Mário >> >> sexta-feira, 19 de Julho de 2019 às 15:23:13 UTC+1, Chris Keathley >> escreveu: >>> >>> 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.lui...@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-l...@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/e6919fe4-9bb6-4894-93ce-8ac4f4255869%40googlegroups.com >> <https://groups.google.com/d/msgid/elixir-lang-core/e6919fe4-9bb6-4894-93ce-8ac4f4255869%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/CAGjNwxqnSm4sya_zwUWzxDTmF3HxgcAK%3D3abGsxFqvTE4NU%3Dpg%40mail.gmail.com > <https://groups.google.com/d/msgid/elixir-lang-core/CAGjNwxqnSm4sya_zwUWzxDTmF3HxgcAK%3D3abGsxFqvTE4NU%3Dpg%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > -- 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/CAF7CYk66Y9JN-rxr7mznstyz%3Db%2B_aSwW77pO1wROw8EGZ5Ypzw%40mail.gmail.com.
