[Python-ideas] "Exposing" `__min__` and `__max__`

Steven D'Aprano 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 mailing list