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的最小值（）爲自定義類（二進制搜索樹）

回答

相關問題