4 ms·

Python is famously built around hash tables. So much so that several versions ago they made an improvement to the hash table implementation, and the entire lang

Python is famously built around hash tables. So much so that several versions ago they made an improvement to the hash table implementation, and the entire language became several percent faster. However, I'm surprised to see no data structures at all with O(log(N)) complexity. Surely there are some use cases for which that's desirable?

krautsauer 1mo ago
One reason you don't see a data structure with O(log(n)) operations in this list is that priority queues/heaps are not a built-in type. Weirdly, there isn't a type for them at all, just a bunch of functions (good luck if you use them wrong). https://docs.python.org/3/library/heapq.html https://docs.python.org/3/library/heapq.html
- zahlman 1mo ago
  There isn't a type for them for the same kind of reasons that `join` is a method on the joining string. That is, it lets you reuse that code for multiple sequence types, including ones that don't exist yet. This is just something that happens with ad-hoc polymorphism, but it's also good to keep class interfaces small and implement other functionality in terms of them. Herb Sutter would approve. Making the functions into methods wouldn't make them easier to use, it would just make the abstraction feel more familiar to those from a Java tradition rather than a C++ one.
  - krautsauer 1mo ago
    Easier I don't know, but safer for sure. With the current implementation you can accidentally use first heapify_max and then heappop (forgetting the _max), accidentally append something through the normal list append method, change the priority of something unknowing that that breaks the invariant, or run into problems with "Tuple comparison breaks for (priority, task) pairs if the priorities are equal and the tasks do not have a default comparison order". These headaches could have been mostly removed if these were in a class. And the option to use a custom sequence type could have surely been preserved.
- Retr0id 1mo ago
  It's not exposed for general use (yet?) but cpython does internally contain an implementation of the HAMT data structure: https://github.com/python/cpython/blob/main/Python/hamt.c https://github.com/python/cpython/blob/main/Python/hamt.c Set/Delete/Lookup are all O(log(n)) See also: https://github.com/MagicStack/immutables https://github.com/MagicStack/immutables (for something you can actually use) p.s. I think the reason heapq isn't a type is that it's ancient code that's hung around from the early days of python.

krautsauer 1mo ago

One reason you don't see a data structure with O(log(n)) operations in this list is that priority queues/heaps are not a built-in type. Weirdly, there isn't a type for them at all, just a bunch of functions (good luck if you use them wrong). https://docs.python.org/3/library/heapq.html https://docs.python.org/3/library/heapq.html

zahlman 1mo ago
There isn't a type for them for the same kind of reasons that `join` is a method on the joining string. That is, it lets you reuse that code for multiple sequence types, including ones that don't exist yet. This is just something that happens with ad-hoc polymorphism, but it's also good to keep class interfaces small and implement other functionality in terms of them. Herb Sutter would approve. Making the functions into methods wouldn't make them easier to use, it would just make the abstraction feel more familiar to those from a Java tradition rather than a C++ one.
- krautsauer 1mo ago
  Easier I don't know, but safer for sure. With the current implementation you can accidentally use first heapify_max and then heappop (forgetting the _max), accidentally append something through the normal list append method, change the priority of something unknowing that that breaks the invariant, or run into problems with "Tuple comparison breaks for (priority, task) pairs if the priorities are equal and the tasks do not have a default comparison order". These headaches could have been mostly removed if these were in a class. And the option to use a custom sequence type could have surely been preserved.
Retr0id 1mo ago
It's not exposed for general use (yet?) but cpython does internally contain an implementation of the HAMT data structure: https://github.com/python/cpython/blob/main/Python/hamt.c https://github.com/python/cpython/blob/main/Python/hamt.c Set/Delete/Lookup are all O(log(n)) See also: https://github.com/MagicStack/immutables https://github.com/MagicStack/immutables (for something you can actually use) p.s. I think the reason heapq isn't a type is that it's ancient code that's hung around from the early days of python.