4 ms·
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
by 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 agoBut isn't usually when using lists performance is dead anyway (due to cache misses).
- pansa2 6y agoLinked-lists, maybe, but `list`s in Python are just resizable arrays.
- kindall 6y agoresizable 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 agoBut 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 agoWhen 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 agoYes 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 agoNot at the scale of his employer.
- hiptobecubic 6y agoYou 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.