6 ms·

Developers in other languages know the performance characteristics of list.delete because there is only one implementation throughout 99% of their codebase. Go

• btilly 6y ago
  My experience is that developers in other languages have no idea of the performance characteristics of list.delete. It seems low-level and therefore obviously fast.
  • andi999 6y ago
    But isn't usually when using lists performance is dead anyway (due to cache misses).
    • pansa2 6y ago
      Linked-lists, maybe, but `list`s in Python are just resizable arrays.
      • kindall 6y ago
        resizable arrays of pointers to objects stored elsewhere, which is going to blow through your cache anyway, especially when you start accessing those objects' attributes. so it's more a memory management strategy than a performance optimization.
        • pansa2 6y ago
          But when removing an item it’s not necessary to visit every element, just re-arrange the pointers (and in CPython, modify the reference count of the item that was removed).
          • sokoloff 6y ago
            When removing an item by value (being the use case in this thread), you do need to visit the elements to check the value.
            • hiptobecubic 6y ago
              Yes but the problem there is not that your list is backed by a linked list or an array, it's that every single value is boxed and needs dereferencing. The difference between no hops and one hop totally trumps one hop vs two hops.
    • simiones 6y ago
      "List" is usually a generic term for any data structure that can hold many items, and that has an API for adding or removing items. This can be implemented using an array, a linked-list, a hasthable, or a more advanced data structure. Also, in languages with GCs, linked lists do not necessarily cause more cache misses than arrays, due to the way allocation works (this is especially true if you have a compacting GC, but bump-pointer allocation often makes it work even when you don't).
  • mdemare 6y ago
    "Fancy algorithms are slow when n is small, and n is usually small." Rob Pike, creator of Go.
    • saagarjha 6y ago
      Not at the scale of his employer.
      • hiptobecubic 6y ago
        You don't need to be Google scale. Google scale is just "medium large startup" scale replicated across a zillion regions. Gmail has an enormous amount of data behind it, but it's not like calling foo.sort() is going to be iterating over billions of accounts.
• deleted 6y ago
  [deleted]
• 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 ago
    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. [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 ago
      Redis's documentation is wonderful, I wish every system I use were documented even half as well.
  • mhh__ 6y ago
    Andrei 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 ago
• jholloway7 6y ago
  You can write a list data structure with performant 'delete' properties if you're willing to maintain a sort or a hash table. There would be people here bitching about memory usage if the stdlib did that natively. Here's a solution: don't use list.delete. You're using the wrong data structure if that's your solution to whatever collection you're maintaining.
  • jholloway7 6y ago
    Downvotes on comp sci 102. Nice.
    • mirekrusin 6y ago
      We have this saying in my country "if grandma had a mustache she'd be a grandpa".
      • omaranto 6y ago
        I like my country's version better: "if grandma had wheels she'd be a bicycle".
        • jholloway7 6y ago
          If your aunt had nuts she'd be your uncle
          • omaranto 6y ago
            That has the same basic idea as the mustache version, but is pithier. I still prefer the surrealism of the bicycle.
        • arp242 6y ago
          Which language/country is this? I will use this in English regardless. I like it.
          • 6y ago
• nunez 6y ago
  Yes! Perfect example: Datetimes. In Golang, if you want to convert a string to a datetime (or vice versa), you _need_ to look at the godoc for datetime because it uses very specific permutations of "Jan 2, 2006" that you _have_ to include in your code. This is much more confusing than how this would be done in Python (provide the format of the date using ISO8601 notation) or Ruby (provide the string, get a Datetime, done).