Re:Go is not an easy language
by arp242 on Monday February 22, 2021 @02:34AM
(#26221806)
Redis 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.
> 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
[2]: https://ruby-doc.org/core-3.0.0/Array.html#method-i-delete