[Python-ideas] "Exposing" `__min__` and `__max__`
steve at pearwood.info
Tue Jun 19 23:19:19 EDT 2018
On Tue, Jun 19, 2018 at 12:33:15PM -0700, Michael Selik wrote:
> Do you mind sharing an example usage in a realistic context? There might be
> a good solution that doesn't require adding magic methods.
You have some sort of binary search tree that is iterated over in some
arbitrary order. Calling min(tree) iterates over the entire tree, even
if the tree knows how to find the minimum much more efficiently.
Iterating over the entire tree is O(N), where N = number of nodes.
More efficent min is typically O(D), where D = depth, which is typically
about log_2 N if the tree is balanced.
I know that for many purposes, we use dicts as they are more convenient
and easier to use than trees, but there are still plenty of realistic
use-cases for trees.
More information about the Python-ideas