Найти минимальное и максимальное с рекурсией эффективно

Question

Есть ли способ рекурсивного поиска минимума и максимума в списке?Я написал это на python, но это очень плохо, так как каждый раз вызывал функцию с одним и тем же списком как для max, так и для min.

def f(l):
    if len(l)==1 : return [l[0],l[0]]
    return [max(l[0],f(l[1:])[0]),min(l[0],f(l[1:])[1])]

l=[1,3,9,-3,-30,10,100]
print(f(l))

output: [100, -30]

-

У вас есть идеи о том, как его улучшить?Возможно ли это сделать даже без передачи какой-либо другой переменной в функцию?

Answer 1

Есть способ сделать это (и рекурсия в python действительно очень медленная; смотрите другие ответы, если вы хотите надежную реализацию).Подумайте о своей рекурсивной формулировке слева направо: на каждом уровне рекурсии возьмите мин / макс текущего элемента в списке и результат, возвращаемый со следующего уровня рекурсии.Тогда (для python> = 2.5 мы можем использовать троичный оператор):

def find_min(ls, idx):
    return ls[idx] if idx == len(ls) - 1 else min(ls[idx], find_min(ls, idx+1))

find_max аналогично;Вы можете просто заменить min на max.Если вам нужно более простое определение, вы можете обернуть функцию, которая принимает только ls вокруг find_min/find_max, и заставить эту функцию вызывать find_min(ls, 0) или find_max(ls, 0).

Answer 2

Я не уверен, почему вы хотите использовать рекурсию для нахождения минимума и максимума, поскольку вы можете просто передать список min и max.

def f(l):
  return min(l), max(l)

Если вы пытаетесь это сделатьэто как упражнение в рекурсии, я не вижу способа решить его, не передавая мин и макс вниз рекурсивного вызова.

def f(l, min_=None, max_=None):
  if not l:
    return min_,max_
  min_ = l[0] if min_ is None else min(l[0], min_)
  max_ = l[0] if max_ is None else max(l[0], max_)
  return f(l[1:], min_, max_)

Answer 3

В Python рекурсивная реализация в любом случае будет намного медленнее, чем итеративная, из-за:

• издержек вызова
• создание объекта, в т.ч.частичное построение списка
• без использования некоторых эффективных конструкций Python, таких как for .. in loop

Вы не можете исключить первое, если вам определенно требуется выполнить рекурсивный алгоритм, но вы можетевырезать на объекте строительства.Построение списка особенно обременительно, так как все элементы копируются каждый раз.

• вместо создания нового списка каждую итерацию, передайте тот же список и текущий индекс в нем

  • и в своей функции вы создаете новый список не один раз, а дважды!

• Вы 'Кроме того, два рекурсивных вызова каждой итерации.Каждый из них также сделает два звонка и т.д., в результате чего общее количество звонков будет колоссальным 1+2+4+...+2**(N-1) = 2**N-1!Чтобы добавить оскорбление к травме, два вызова полностью избыточны, поскольку оба они дают одинаковый результат.

• , поскольку текущий элемент списка используется несколько раз, несколько микросекод также могут быть обрезаныкэшируя его в переменной вместо извлечения каждый раз.

def rminmax(l,i=0,cmin=float('inf'),cmax=float('-inf')):
    e=l[i]

    if e<cmin: cmin=e
    if e>cmax: cmax=e
    if i==len(l)-1:
        return (cmin,cmax)
    return rminmax(l,i+1,cmin,cmax)

Также обратите внимание, что из-за ограничения размера стека CPython вы не сможете обрабатывать списки длиннее числанемного ниже sys.getrecursionlimit() (немного ниже, потому что механизм интерактивного цикла также занимает некоторые кадры стека вызовов).Это ограничение может не применяться в других реализациях Python.

Вот несколько сравнений производительности на моей машине с примерами данных:

In [18]: l=[random.randint(0,900) for _ in range(900)]

In [29]: timeit rminmax(l)
1000 loops, best of 3: 395 µs per loop

# for comparison:

In [21]: timeit f(l)    #your function
# I couldn't wait for completion; definitely >20min for 3 runs

In [23]: timeit f(l)    #sjf's function
100 loops, best of 3: 2.59 ms per loop

Answer 4

Почему рекурсивно?

Это будет нормально работать и примерно в 10 раз быстрее, чем лучший рекурсивный алгоритм:

def minMax(array): return min(array),max(array)

Чтобы избежать повторного вызова каждого рекурсии, вы могли бы написать функцию следующим образом:

def minMax(array):
    first,*rest = array  # first,rest = array[0],array[1:]
    if not rest : return first,first
    subMin,subMax = minMax(rest)
    return min(first,subMin), max(first,subMax)

Если вы хотите избежать максимального предела рекурсии (т.е. в большом списке), вы можете использовать двоичный подход, разделяющий массив на левую и правую части.при этом используются только уровни рекурсии log (n) (а также уменьшаются некоторые накладные расходы на обработку):

def minMax(array):
    size = len(array)
    if size == 1 : return array[0],array[0]
    midPoint = size // 2
    leftMin,leftMax   = minMax(array[:midPoint])
    rightMin,rightMax = minMax(array[midPoint:])
    return min(leftMin,rightMin), max(leftMin,rightMin)

Если вы хотите уменьшить накладные расходы на создание массива и вызовы функций, вы можете передатьИндексируйте и избегайте min (), max () и len () (но тогда вы используете рекурсию как цикл for, который в значительной степени побеждает цель):

def minMax(array, index=None):
    index = (index or len(array)) - 1
    item = array[index]
    if index == 0 : return item,item
    subMin,subMax = minMax(array,index)
    if item < subMin: return item,subMax
    if item > subMax: return subMin,item
    return subMin,subMax

Вы можете объединить два предыдущих всократить накладные расходы и избежать предела рекурсии, но при этом производительность немного снизится:

def minMax(array, start=0, end=None):
    if end is None : end = len(array)-1
    if start >= end - 1:
        left,right = array[start],array[end]
        return (left,right) if left < right else (right,left)
    middle = (start + end) >> 1
    leftMin,leftMax   = minMax(array, start,middle)
    rightMin,rightMax = minMax(array, middle+1,end)
    return ( leftMin if leftMin < rightMin else rightMin ), \
           ( leftMax if leftMax > rightMax else rightMax )