Преобразование рекурсивного алгоритма «разделяй и властвуй» в итерационную версию - PullRequest
Новая
       37

Преобразование рекурсивного алгоритма «разделяй и властвуй» в итерационную версию

0 голосов
/ 18 января 2019

Я хотел бы преобразовать рекурсивный алгоритм в массиве в итеративную функцию. Он не является хвостовым рекурсивным алгоритмом и имеет два рекурсивных вызова, за которыми следует некоторая операция. Алгоритм представляет собой алгоритм «разделяй и властвуй», где на каждом шаге массив разбивается на два подмассива, и некоторая функция f применяется к двум предыдущим результатам. На практике f сложен, поэтому итерационный алгоритм должен использовать функцию f, для минимального рабочего примера я использовал простое дополнение.

Ниже приведен минимальный рабочий пример рекурсивной программы на python. 

import numpy as np

def f(left,right):
    #In practice some complicated function of left and right
    value=left+right
    return value

def recursive(w,i,j):
    if i==j:
        #termination condition when the subarray has size 1
        return w[i]
    else:
        k=(j-i)//2+i
        #split the array into two subarrays between indices i,k and k+1,j
        left=recursive(w,i,k)
        right=recursive(w,k+1,j)

        return f(left,right)

a=np.random.rand(10)
print(recursive(a,0,a.shape[0]-1))

Теперь, если я хочу написать это итеративно, я понимаю, что мне нужен стек для хранения промежуточных результатов, и что на каждом шаге мне нужно применять f к двум элементам в верхней части стека. Я просто не уверен, как построить порядок, в котором я помещаю элементы в стек без рекурсии. Вот попытка найти решение, которое, безусловно, не оптимально, поскольку, похоже, должен быть способ удалить первый цикл и использовать только один стек: 

def iterative(w):
    stack=[]
    stack2=[]
    stack3=[]
    i=0
    j=w.shape[0]-1
    stack.append((i,j))
    while (i,j)!=(w.shape[0]-1,w.shape[0]-1):
        (i,j)=stack.pop()
        stack2.append((i,j))
        if i==j:
            pass
        else:
            k=int(np.floor((j-i)/2)+i)
            stack.append((k+1,j))
            stack.append((i,k))
    while len(stack2)>0:
        (i,j)=stack2.pop()
        if i==j:
            stack3.append(w[i])
        else:
            right=stack3.pop()
            left=stack3.pop()
            stack3.append(f(left,right))
    return stack3.pop()

Редактировать: реальная проблема, которая меня интересует, состоит в том, чтобы ввести массив тензоров разных размеров, и операция f решает линейную программу с участием этих тензоров и выводит новый тензор. Я не могу просто перебрать исходный массив, так как в этом случае размер выходных данных f растет в геометрической прогрессии. Вот почему я использую подход «разделяй и властвуй», который уменьшает этот размер. Рекурсивная программа работает нормально, но значительно замедляется при большом размере, возможно, из-за фреймов, которые Python открывает и отслеживает.

1 Ответ

0 голосов
/ 18 января 2019

Ниже я преобразовал программу, чтобы использовать продолжение (then) и батут (run / recur). Он развивает линейный итеративный процесс и не будет переполнять стек. Если вы не столкнулись с проблемой переполнения стека, это мало поможет вашей конкретной проблеме, но может научить вас, как сгладить вычисления ветвления.

Этот процесс преобразования нормальной функции в стиль передачи продолжения может быть механическим. Если вы немного прищурите глаза, вы увидите, что в программе есть почти такие же элементы, как у вас. Встроенные комментарии показывают код рядом друг с другом - 

import numpy as np

def identity (x):
  return x

def recur (*values):
  return (recur, values)

def run (f):
  acc = f ()
  while type (acc) is tuple and acc [0] is recur:
    acc = f (*acc [1])
  return acc

def myfunc (a):
  # def recursive(w,i,j)
  def loop (w = a, i = 0, j = len(a)-1, then = identity):
    if i == j:                # same
      return then (w[i])      # wrap in `then`
    else:                     # same
      k = (j - i) // 2 + i    # same
      return recur \          # left=recursive(w,i,k)
        ( w
        , i
        , k
        , lambda left:
          recur               # right=recursive(w,k+1,j)
            ( w
            , k + 1
            , j
            , lambda right:
                then          # wrap in `then`
                  (f (left, right)) # same
            )
        )
  return run (loop)

def f (a, b):
    return a + b              # same

a = np.random.rand(10)        # same
print(a, myfunc(a))           # recursive(a, 0, a.shape[0]-1)

# [0.5732646  0.88264091 0.37519826 0.3530782  0.83281033 0.50063843 0.59621896 0.50165139 0.05551734 0.53719382]

# 5.208212213881435
...