2 ms·
Haskell documentation uses the Big O notation everywhere which I really love. I wish Go and many other languages did the same. An example would be https://hack
by johnisgood 6y ago
Haskell documentation uses the Big O notation everywhere which I really love. I wish Go and many other languages did the same.
An example would be https://hackage.haskell.org/package/containers-0.4.0.0/docs/Data-Map.html https://hackage.haskell.org/package/containers-0.4.0.0/docs/....
size :: Map k a -> IntSource
O(1). The number of elements in the map.
member :: Ord k => k -> Map k a -> BoolSource
O(log n). Is the key a member of the map? See also notMember.
lookup :: Ord k => k -> Map k a -> Maybe aSource
O(log n). Lookup the value at a key in the map.
And so forth...
- arp242 6y agoRedis does the same; e.g. [1]: > Time complexity: O(N) where N is the number of elements to traverse to get to the element at index. This makes asking for the first or the last element of the list O(1). I agree this is something more documentations should do when possible; it doesn't even have to be big-O notation as far as I'm concerned, just a "this will iterate over all keys" will be fine. Ruby's delete() doesn't mention any of this, although you can easily see the (C) implementation in the documentation[2]. In principle at least, this doesn't have to be O(n) if the underlying implementation would be a hash for example, which of course has its own downsides but something like PHP may actually do this with their arrays as they're kind of a mixed data structure? Not sure. [1]: from https://redis.io/commands/lindex https://redis.io/commands/lindex [2]: https://ruby-doc.org/core-3.0.0/Array.html#method-i-delete https://ruby-doc.org/core-3.0.0/Array.html#method-i-delete
- Groxx 6y agoRedis's documentation is wonderful, I wish every system I use were documented even half as well.
- mhh__ 6y agoAndrei Alexandrescu has a scheme to encode these in the D typesystem on his website. It didn't get merged into the standard library in the end but you can happily do it in your own code
- johannes1234321 6y agoIn the C++ standard the complexity of algorithms is a requirement for a compliant implementation. Many text books skip it, but better documentation references it. Taking the "delete element from list" example from this thread https://en.cppreference.com/w/cpp/container/list/remove https://en.cppreference.com/w/cpp/container/list/remove states that there is a linear search.