Python的最小值（）为自定义类（二进制搜索树）

我正在实现一个二进制搜索树并创建了一个最小的方法。我想知道我是如何（或是否）能做到兼容，所以，我能够做到：Python的最小值（）为自定义类（二进制搜索树）

min(my_tree)

而不是

my_tree.minimum()

我在想，如果它使用迭代，这将是O（N）时间而不是O（lgN）。

来源

2016-05-12 lorenzocastillo

这是不可能的 - 'min（）'是一个函数，不能重载自定义类。内部实现不能利用BST内部结构，因此它的复杂性不会低于O（n）。 –

你知道内置的[**'bisect' **]（https://docs.python.org/2/library/bisect.html）吗？ –

@Rogalski'min'的[**'key' **]（https://docs.python.org/2/library/functions.html#min）参数允许聪明的技巧。 –

在CPython中执行min可以在这里找到here。相关的代码在下面重复。

static PyObject * 
min_max(PyObject *args, PyObject *kwds, int op) 
{ 
    /* omitted code */ 
    it = PyObject_GetIter(v); 
    /* omitted code */ 

    maxitem = NULL; /* the result */ 
    maxval = NULL; /* the value associated with the result */ 
    while ((item = PyIter_Next(it))) { 
     /* get the value from the key function */ 
     if (keyfunc != NULL) { 
      val = PyObject_CallFunctionObjArgs(keyfunc, item, NULL); 
      if (val == NULL) 
       goto Fail_it_item; 
     } 
     /* no key function; the value is the item */ 
     else { 
      val = item; 
      Py_INCREF(val); 
     } 

     /* maximum value and item are unset; set them */ 
     if (maxval == NULL) { 
      maxitem = item; 
      maxval = val; 
     } 
    /* more omitted code */ 
    } 
} 

static PyObject * 
builtin_min(PyObject *self, PyObject *args, PyObject *kwds) 
{ 
    return min_max(args, kwds, Py_LT); 
}

从这一点可以看出，使用min将是为O（n）不管是什么;它通过迭代器中的每个成员。你无法覆盖这种行为，我不认为你目前的使用tree.minimum()是不自然的。

来源

2016-05-12 13:41:59

我在想可能会实现一个min_iter，max_iter等，或者其他东西，但是当Python通常有更干净的东西时，这似乎很复杂。 – lorenzocastillo

您可以写自己的函数调用min并用它来掩盖一个事实，即它是不是真的有可能：

min_ = min 
def min(*args, **kwargs): 
    if isinstance(args[0], MyTree): 
     return args[0].minimum() 
    else: 
     return min_(*args, **kwargs)

不这样做，虽然。

来源

2016-05-12 13:58:15 L3viathan

Python的最小值（）为自定义类（二进制搜索树）

回答

相关问题