Как конвертировать синхронную и асинхронную рекурсивную функцию в итерацию в JavaScript

Ответ 1

Чтобы мы могли преобразовать процедуру с функцией, вызывающей другую функцию (независимо от того, является ли она той же самой функцией, иначе называемой "рекурсивной" ), нам нужно разделить ее на процедуру, которая возникает до такого вызова и любых процедур, следующих за вызовом. Если после исходящего вызова нет процедур, а исходящий вызов относится к одной и той же функции, мы можем описать его как "хвост рекурсивный", который может сделать преобразование в итеративном намного проще, просто нажимая параметры вызова в стек (Пример). Фактически, преобразование хвостовой рекурсии в процесс итеративного стека помогло мне преодолеть пределы глубины рекурсии браузеров в более чем одном реальном экземпляре.

Преобразование в хвостовую рекурсию

Чтобы преобразовать рекурсию в хвостовую рекурсию, мы должны рассмотреть, как обрабатывается информация, полученная от рекурсивного вызова, и можем ли мы преобразовать этот процесс для использования параметров в самой рекурсии. Поскольку в вашем конкретном примере единственное, что происходит с результатом внешнего вызова, - это установка локальной переменной, output и output - это объект, который в JavaScript передается по ссылке, мы находимся в положении сделать это преобразование. Итак, вот простой рефактор, который позволит нам использовать сжатый стек (я пропустил хвостовой рекурсивный код в реализацию стека, оставил в качестве упражнения для читателя):

var references = {}
var object = {
  a: {
    b: {
      c: {
        d: {
          e: 10,
          f: 11,
          g: 12
        }
      }
    }
  }
}
object.a.b.c.d.x = object
object.a.b.c.d.y = object.a.b

var id = 1

//var x = circularReferences(object, references)
//console.log(x)

//function circularReferences(object, references) {
// => add parameters, 'output' and 'key'
var stack = [[object, references, null, null]];

while (stack.length){
  [_object, _references, _callerOutput, _key] = stack.pop()

  var output = {}
  
  if (_object.__circularid__){
    _callerOutput[_key] = '[Circular]'
    
    // Log our example
    console.log('OUTPUT VALUE: ' + JSON.stringify(_callerOutput))
    
    // Exit
    continue;
  }
  
  Object.defineProperty(_object, '__circularid__', { value: id++ })
  
  for (var key in _object) {
    var value = _object[key]
    
    if (value && typeof value == 'object') {
      console.log(value)
      
      //var is = circularReferences(value, references)
      // if (is) output[key] = '[Circular]'
      stack.push([value, _references, output, key])
        
    } else {
      output[key] = value
    }
  }
}

Ответ 2

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

Когда функция в Javascript выполняется, она подталкивает адрес возврата, параметры функции и локальные переменные в стек. Практически невозможно получить большую экономию на них с естественно-рекурсивной проблемой неопределенной глубины, заставляя ее зацикливаться. Предыдущий ответ (чье имя я не могу напечатать или даже скопировать-вставить хорошо, так как он в RTL-обращении) обсудил хвостовую рекурсию, и если вы можете поместиться в шаблон, вы можете получить небольшую экономию, не нажимая обратный адрес в стек, но Возможно, механизмы Javascript могут позаботиться об этом для вас.

Одна разница и дополнительная загрузка производительности по сравнению с другими языками, например PHP, будут заключаться в том, что Javascript также создает закрытие для каждого вызова функции. Это может быть тривиальная или значительная стоимость ресурсов в очень глубоких, очень широких наборах данных, тип, который может фактически вызвать проблему, когда можно подумать, что нерекурсия решит эту проблему. Существует средство для вызова функции без закрытия, однако, используя конструктор Function. Мы уклоняемся от них, потому что eval-is-evil и они делают дополнительный шаг для компиляции, но после его создания это может уменьшить любые дополнительные накладные расходы при закрытии в глубокой рекурсии. Эффективность компиляции в реальном времени должна быть более чем компенсирована уменьшением накладных расходов при глубоких вызовах рекурсии.

Другие перетаскивания производительности могут создавать объект-аргумент и контекст выполнения (this). Теперь у нас есть функции стрелок, которые просто наследуют экземпляры внешней области. Таким образом, фактическая рекурсивная часть должна быть функцией стрелки. Если ему нужен this, пропустите его внешним замыканием Function или передайте его как параметр.

Здесь общее отображение:

const outerFunction=new Function(
    'arg1,arg2,arg3',
    `
        // Initialize and create items that simply must be transferred by closure
        ...
        const recursiveFunction=(param1,param2,param3)=>{
            ...
            const value=recursiveFunction(newParam1,newParam2,newParam3)
            ...
        }
        return recursiveFunction(firstParam1,firstParam2,firstParam3)
    `
)

В общую схему, оптимизируйте внутренний цикл как можно больше. Не создавайте и рекомбинируйте объекты и массивы, если оригиналы могут быть переданы в качестве ссылок. В рекурсивной части не выполняйте никаких операций по удалению или посторонней обработке. Программистам Javascript не уделяют много внимания утечкам памяти, так как язык традиционно представляет собой короткие фрагменты, которые вытираются при обновлении страницы, поэтому научитесь выявлять случаи, когда предметы, которые больше не нужны, не могут быть собраны в мусор, и, если на то пошло, уменьшите элементы, которые нужно собрать мусором, если проблема - это скорость, а не память. Помните, что все примитивы неизменяемы, и старые значения будут подчиняться GC'd при назначении новых значений. Подумайте об использовании типизированных массивов, где разумно, чтобы это предотвратить.

Даже если это не решит проблемы OP, я надеюсь, что этот подход может быть полезен другим, кто находит этот вопрос в Google.

Ответ 3

Позвольте просто определить простую функцию вместе с нашими параметрами.

function syncLoop(iterations, process, exit){
    // Body of the function
}

Просто поговорить о параметрах очень быстро,

iterations = the number of iterations to carry out
process    = the code/function we're running for every iteration
exit       = an optional callback to carry out once the loop has completed

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

function syncLoop(iterations, process, exit){
    var index = 0,
        done = false;
    // Body of function
}

Теперь мы можем отслеживать, где мы находимся, и если мы закончили или нет (оба важны в циклах!). Сделанный логический процесс будет нашим способом проверить, хотим ли мы снова запускаться при вызове.

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

function syncLoop(iterations, process, exit){
    var index = 0,
        done = false;
    var loop = {
        // Loop structure
    };
    return loop;
}

Я вернусь к этому через некоторое время. Итак, у нас есть наш цикл. Что важно иметь в цикле? Ну, нам нужен способ доступа к индексу, перемещение в цикле и способ убить цикл - так что давайте реализовать эти методы.

function syncLoop(iterations, process, exit){
    var index = 0,
        done = false,
        shouldExit = false;
    var loop = {
        next:function(){
            if(done){
                if(shouldExit && exit){
                    return exit(); // Exit if we're done
                }
            }
            // If we're not finished
            if(index < iterations){
                index++; // Increment our index
                process(loop); // Run our process, pass in the loop
            // Otherwise we're done
            } else {
                done = true; // Make sure we say we're done
                if(exit) exit(); // Call the callback on exit
            }
        },
        iteration:function(){
            return index - 1; // Return the loop number we're on
        },
        break:function(end){
            done = true; // End the loop
            shouldExit = end; // Passing end as true means we still call the exit callback
        }
    };
    return loop;
}

Хорошо, немного поговорим об этом;

loop.next() является нашим контроллером цикла. Наш процесс должен называть loop.next(), когда он хочет завершить итерацию и перейти к следующему. В принципе, все loop.next() это снова вызывает наш желаемый процесс, если мы не закончим, и в этом случае он вызывает окончательный обратный вызов.

Функция loop.iteration() просто возвращает индекс, в котором мы находимся. Первая инициализация означает, что мы всегда будем на один индекс впереди текущей итерации, поэтому возвращаем индекс - 1.

loop.break() просто указывает циклу завершить текущую итерацию. Вы можете передать необязательное значение, чтобы сообщить о завершении цикла, как обычно, и вызвать обратный вызов exit(), если это необходимо. Это полезно для циклов, которые необходимо очистить после себя.

Правильно, у нас здесь большая часть тела. Поэтому просто отпустите его, вызвав loop.next() непосредственно перед тем, как мы вернем наш цикл.

function syncLoop(iterations, process, exit){
    var index = 0,
        done = false,
        shouldExit = false;
    var loop = {
        next:function(){
            if(done){
                if(shouldExit && exit){
                    return exit(); // Exit if we're done
                }
            }
            // If we're not finished
            if(index < iterations){
                index++; // Increment our index
                process(loop); // Run our process, pass in the loop
            // Otherwise we're done
            } else {
                done = true; // Make sure we say we're done
                if(exit) exit(); // Call the callback on exit
            }
        },
        iteration:function(){
            return index - 1; // Return the loop number we're on
        },
        break:function(end){
            done = true; // End the loop
            shouldExit = end; // Passing end as true means we still call the exit callback
        }
    };
    loop.next();
    return loop;
}

И все готово! Все, что имеет значение сейчас, - это реализовать наш цикл и запустить его, поэтому рассмотрим пример:

syncLoop(5, function(loop){
    setTimeout(function(){
        var i = loop.iteration();
        console.log(i);
        loop.next();
    }, 5000);
}, function(){
    console.log('done');
});

Вышеприведенный код просто выводит текущую итерацию с интервалом 5 секунд между каждой печатью, а затем записывается после завершения. Идите дальше и попробуйте его в консоли браузера. Пусть также проверьте, что наш loop.break() работает так, как ожидалось.

var myLoop = syncLoop(5, function(loop){
    setTimeout(function(){
        var i = loop.iteration();
        console.log(i);
        loop.next();
    }, 5000);
}, function(){
    console.log('done');
});

setTimeout(myLoop.break, 10000);

В этом сценарии мы должны увидеть только первые две итерации, напечатанные до окончания цикла. Поскольку мы не передаем логическое значение myLoop.break(), оно не выполняется. Мы могли бы изменить это, используя следующее:

setTimeout(function(){
    myLoop.break(true);
}, 10000);

Важно отметить, что вы не можете убить цикл (чисто), пока в середине выполнения, он будет ждать завершения текущей итерации (что на самом деле имеет большой смысл). Он просто остановит разрыв для начала следующей итерации, которая проверяется в loop.next().

Ответ 4

Существует общий способ перевода рекурсивной функции вместо явного стека: Имитировать способ обработки рекурсивных вызовов компилятором. Сохраните все локальное состояние в стеке, измените значения аргументов на то, что было бы передано на рекурсивный вызов, и перейдите в начало функции. Затем, когда функция возвращает, а не просто возвращает, проверьте стек. Если непустое, поп-состояние и прыжок в место, где будет возвращен рекурсивный вызов. Поскольку javascript не разрешает переходы (goto), тогда необходимо сделать алгебру кода, чтобы преобразовать их в циклы.

Начните с рекурсивного кода, который будет немного легче иметь, чем ваш оригинал. Это просто классическая рекурсивная DFS с "посещенными" метками для объектов (узлы графа), которые мы уже искали, и "текущие" метки для объектов на пути от верхнего (корневого) объекта к текущему. Мы обнаружим все циклы, если для каждой ссылки на объект (край графа) мы проверяем, помечен ли пункт назначения "текущий".

Текущие метки удаляются по пути. Посещенные метки остаются после поиска графика.

function get_back_refs(obj, back_refs) {
  if (obj && typeof obj == 'object' && !('__visited__' in obj)) {
    mark(obj, '__visited__')
    mark(obj, '__current__')
    var iter = getKeyIterator(obj)
    while (iter.hasNext()) {
      var key = iter.next()
      if ('__current__' in obj[key]) {
        back_refs.push([obj, obj[key]])
      } else {
        get_back_refs(obj[key], back_refs)
      }
    }
    unmark(obj, '__current__')
  }
}

var object = {
  a: {
    b: {
      c: {
        d: {
          e: 10,
          f: 11,
          g: 12
        }
      }
    }
  }
}
object.a.b.c.d.x = object
object.a.b.c.d.y = object.a.b

var id = 0

function mark(obj, name) {
  Object.defineProperty(obj, name, { value: ++id, configurable: true })
}

function unmark(obj, name) {
  delete obj[name]
}

function getKeyIterator(obj) {
  return {
    obj: obj,
    keys: Object.keys(obj).filter(k => obj[k] && typeof obj[k] == 'object'),
    i: 0,
    hasNext: function() { return this.i < this.keys.length },
    next: function() { return this.keys[this.i++] }
  }
}

var back_refs = []
get_back_refs(object, back_refs)
for (var i = 0; i < back_refs.length; ++i) {
  var pair = back_refs[i]
  console.log(pair[0].__visited__ + ', ' + pair[1].__visited__)
}