Javascript-форум (https://javascript.ru/forum/)
-   Оффтопик (https://javascript.ru/forum/offtopic/)
-   -   Как рекурсию заменить максимально быстрым циклом (https://javascript.ru/forum/offtopic/34833-kak-rekursiyu-zamenit-maksimalno-bystrym-ciklom.html)

megaupload 21.01.2013 03:19

Как рекурсию заменить максимально быстрым циклом
 
function ololo(q) {

	if(q>5) return;

	alert(q);
	ololo(q+1);
}

ololo(1)

megaupload 21.01.2013 03:29

Вот это же не правильный вариант?

var stark = [];
stark.push(1);



while(stark.length){

	var value = stark[stark.length-1];

	if(value>5){
		stark.pop();
		break;
	}else{
		alert(value);
		stark.push(value+1);
	}

}

megaupload 21.01.2013 04:37

Как я понимаю все переменные и параметры которые использует функция нужно запихать в стек?

Deff 21.01.2013 06:02

function ololo(a,b) {
  for(var i=1; i<b+1; i++){alert(i);}
}

ololo(1,5);

megaupload 21.01.2013 06:12

Deff, спасибо; Вы гений; Ваш пример превосходит мой в разы; А теперь сделайте то же самое с этим:

alertHTML( document.body )


function alertHTML(context){

    alert(this.innerHTML);

    for ( var i = 0; context.childNodes.lenght; i++ ) {
        alertHTML(context.childNodes[i])
    }

}

Dmitriyff 21.01.2013 13:00

если вас порядок нод не волнует

самый быстрый так
alertHTML(document.body);

function alertHTML(context) {
  var nodes = context.childNodes,
        i = nodes.length;

  while (i--) alert(nodes[i]);
}

megaupload 21.01.2013 13:37

Dmitriyff,
Но ведь я создал эту тему для разбора способов развертывания рекурсии в циклы а не для какого-то конкретного решения проблемы; А Ваш вариант вообще, мягко говоря, не рекурсия;

Dmitriyff 21.01.2013 13:41

оу, сорри... не усмотрел =-))), сейчас придумаем

ksa 21.01.2013 13:59

Цитата:

Сообщение от megaupload
я создал эту тему для разбора способов развертывания рекурсии в циклы а не для какого-то конкретного решения проблемы

Рекурсия (правильная не как у тебя в первом случае :D ) циклом не опишется. Она для того и делается.
Потому как не известно не только число итераций, но и уровень вложения.

Возможно некие частные слочаи, где как раз возможно определить что-то конечное, и можно будет "развернуть" в циклы... Но "общего" решения не будет.

Dmitriyff 21.01.2013 14:18

как-то так

var f = function(nodes) {

	var	node, 
		stack = [];

	stack.push(nodes)

	while (stack.length) {

		node = stack.pop();

		if (node.childNodes.length) {

			var i = node.childNodes.length;

			while(i--) stack.push(node.childNodes[i]);
		} else {
			console.log(node);
		}
	}
}

Dmitriyff 21.01.2013 14:19

короче кури тему про графы и обход бинарных деревьев.

megaupload 21.01.2013 14:33

Спасибо конечно, но мне кажется это тут не при чем, и я просто создам стек с переменными;

Dmitriyff 21.01.2013 14:55

dom - это по сути бинарное дерево, код который я привел из разделов связанных с обходом бинарных деревьев. так что оно тут как раз при чем =-)

Цитата:

Сообщение от megaupload
и я просто создам стек с переменными;

эм... не уловил к чему это, собствено пример который я привел как раз со стеком =-)

kobezzza 21.01.2013 14:59

Цитата:

Сообщение от ksa (Сообщение 228520)
Рекурсия (правильная не как у тебя в первом случае :D ) циклом не опишется. Она для того и делается.
Потому как не известно не только число итераций, но и уровень вложения.

Возможно некие частные слочаи, где как раз возможно определить что-то конечное, и можно будет "развернуть" в циклы... Но "общего" решения не будет.

Любую рекурсию можно разложить в цикл. Общий принцип прост (хотя есть сложные рекурсии которые так просто не разложишь).

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

Как пример сложной рекурсии развёрнутой в цикл могу привести свою реализацию метода extend (как в jQuery, т.е. глубокое копирования произвольного количества аргументов произвольной глубины и структуры)

https://github.com/kobezzza/Collecti...re/obj.js#L151

ksa 21.01.2013 15:37

Цитата:

Сообщение от kobezzza
Любую рекурсию можно разложить в цикл. Общий принцип прост (хотя есть сложные рекурсии которые так просто не разложишь).

Это как понять? :D

Рекурсию для того и используют, что цикл тут не применим... Поскольку даже не понятно сколько штук их будет.

kobezzza 21.01.2013 15:39

Цитата:

Сообщение от ksa (Сообщение 228532)
Это как понять? :D

Ты написал что рекурсию нельзя описать с помощью цикла, я написал, что это не так и описал как это можно сделать и привёл пример кода сложной рекурсивной задачи, где все рекурсии выполняются через цикл:)

Цитата:

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

ksa 21.01.2013 15:46

kobezzza, напиши мне цикличный алгоритм подсчета количества файлов в папках.

Т.е. есть корень диска... Там есть как файлы, так и папки... В каждой папке могут быть как файлы так и папки.
Сделай это без рекурсии, только циклами.

Причем все, что у тебя есть в инструментарии - показать содержимое папки, в том числе и корневой.

ksa 21.01.2013 15:47

Цитата:

Сообщение от kobezzza
Ты написал что рекурсию нельзя описать с помощью цикла

Я писал про "правильную" рекурсию. :D
Т.е. когда рекурсивный подход применяется как раз из-за невозможности применения циклов.

ksa 21.01.2013 15:49

Цитата:

Сообщение от kobezzza
Мы создаём стек ручками, как массив и на каждый уровень вложенности пушим туда объект с текущем состоянием переменных, затем локальные переменные переопределяем и продолжаем алгоритм до тех пор пока рекурсия не закончится и тогда мы начинаем "всплытие", т.е. итеративно разворачиваем полученный массив и делаем на каждой итерации pop (т.е. срезаем крайне правый элемент).

Смысл сначала куда-то залезть рекурсивно... А потом работать с полученым цыклом? :blink:
При том утверждать, что де сделал все без рекурсии! :D

Цитата:

Сообщение от kobezzza
Мы создаём стек ручками ...

Это уже какой-то частный случай... А не общий подход к рекурси. :D
Или вся твоя "матчасть" к этому и сводится?

kobezzza 21.01.2013 15:52

Цитата:

Сообщение от ksa (Сообщение 228535)
Я писал про "правильную" рекурсию. :D
Т.е. когда рекурсивный подход применяется как раз из-за невозможности применения циклов.

Я как не странно тоже.
function extend(deep, target, var_args) {
	deep = deep || false;
	target = target || {};
	var aLength = arguments.length,
		
		aEl, key,
		src, copy,
		clone,
		copyIsArray,
		
		i = 1, j,
		
		stack = [],
		level,
		
		last, lastEl;
	
	// Внешний цикл по расширяющим аргументам
	while (++i < aLength) {
		if ((aEl = arguments[i])) {
			// Цикл для эмуляции рекурсии
			while (aEl) {
				level = [];
				
				// Цикл по свойствам объекта
				for (key in aEl) {
					src = target[key];
					copy = aEl[key];
					
					// Защита от бесконечного копирования
					if (target === copy) { continue; }
					
					// Рекурсивное копирование свойств
					// (рекурсия развёрнута)
					if (
						deep && copy
						&& ((copyIsArray = Array.isArray(copy)) || typeof copy === 'object')
					) {
						// Если копируемое свойство - массив
						if (copyIsArray) {
							copyIsArray = false;
							clone = src && Array.isArray(src) ? src : [];
						
						// Если копируемое свойство - объект
						} else {
							clone = src && typeof src === 'object' ? src : {};
						}
						
						// Запоминаем вложенность, чтобы в дальнейшем к ней вернуться
						level.push({
							target: target,
							clone: clone,
							
							aEl: aEl,
							copy: copy,
							
							key: key
						});
					} else {
						target[key] = copy;
					}
				}
				
				// Если на уровне имеются вложенности,
				// то добавляем новый уровень в стек и
				// проиводим сдвиг в крайне правый элемент нового уровня
				if ((last = level.length)) {
					stack.push(level);
					
					last = level[last - 1];
					// Ставим флаг, что элемент учавствует в обходе
					last['__COLLECTION_TMP__'] = true;
					
					// Устанавливаем новую точку отсчёта
					target = last.clone;
					aEl = last.copy;
					
				// На уровне нет вложенностей
				} else if ((last = stack.length)) {
					j = stack.length;
					while (j--) {
						lastEl = stack[j][stack[j].length - 1];
						
						// Если звено не имеет детей и уже было использовано,
						// то удаляем крайне правый элемент и сдвигаем позицию обхода
						if (lastEl['__COLLECTION_TMP__'] && !stack[j + 1]) {
							lastEl.target[lastEl.key] = target;
							target = lastEl.target;
							aEl = lastEl.aEl;
							stack[j].pop();
							
							// В звене не осталось элементов,
							// значит его можно удалить
							if (!stack[j].length) {
								stack.pop();
							}
						
						// Если первое условие не верно,
						// значит продолжать цикл нет смысла
						} else {
							break;
						}
					}
					
					// Устанавливаем новую позицию обхода
					if ((last = stack.length)) {
						last = stack[last - 1];
						lastEl = last[last.length - 1];
						lastEl['__COLLECTION_TMP__'] = true;
						
						target = lastEl.clone;
						aEl = lastEl.copy;
					}
				}
				
				// Операция закончена
				if (!stack.length && !level.length) {
					break;
				}
			}
		}
	}
	
	return target;
};

alert(JSON.stringify(extend(true, {}, {a: {b: 1}, c: {e: 2}}, {a: {b: {e: 2}}})));


Цитата:

Смысл сначала куда-то залезть рекурсивно... А потом работать с полученым цыклом?
Притом утверждать, что де сделал все без рекурсии!
Я писал, что мы руками создаём стек, и эмулируем рекурсию циклом, а смысл: нет проблемы переполнения стека и работает значительно шустрее, к примеру мой вариант extend от 2 до 8 раз быстрее рекурсивного (в зависимости от браузера).

Цитата:

Это уже какой-то частный случай... А не общий подход к рекурси.
Или вся твоя "матчасть" к этому и сводится?
Ты можешь бесконечно спорить на эту тему, но факт остаётся фактом. Любую рекурсию можно раскрыть так.

ksa 21.01.2013 15:57

kobezzza, еще раз повторюсь... Если задачка раскладывается на конечное число циклов и этого хватает для решения проблемы в общем виде - это не "рекурсивная задачка".
Если её кто-то решеет рекурсивно - это его проблема и ответственность. :D

kobezzza 21.01.2013 16:03

Цитата:

Т.е. есть корень диска... Там есть как файлы, так и папки... В каждой папке могут быть как файлы так и папки.
Сделай это без рекурсии, только циклами.
Сделано выше, вместо папок и файлов объекты, а всё остальное тоже самое.

Цитата:

Сообщение от ksa (Сообщение 228538)
kobezzza, еще раз повторюсь... Если задачка раскладывается на конечное число циклов и этого хватает для решения проблемы в общем виде - это не "рекурсивная задачка".
Если её кто-то решеет рекурсивно - это его проблема и ответственность. :D

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

http://ru.wikipedia.org/wiki/%D0%A0%...81%D0%B8%D1%8F
Цитата:

Любую рекурсивную функцию можно заменить циклом и стеком.

Gozar 21.01.2013 16:03

ksa,
Какой ты упрямый, прям как я :). Я часто пишу сначала на рекурсии, а затем переписываю на циклы, т.к.
Цитата:

Сообщение от kobezzza
работает значительно шустрее



Цитата:

Сообщение от ksa
напиши мне цикличный алгоритм подсчета количества файлов в папках.

Так и начинается любой холивар. Я не умею это делать, но утверждаю, что это невозможно. ;)

kobezzza 21.01.2013 16:08

Цитата:

Сообщение от Gozar (Сообщение 228540)
Так и начинается любой холивар. Я не умею это делать, но утверждаю, что это невозможно. ;)

Вот-вот:)

nerv_ 21.01.2013 16:10

Цитата:

Сообщение от Дзен-трансгуманист
megaupload,
Приятного аппетита.

+

kobezzza, если все "так просто", почему движок не делает это за нас?

kobezzza 21.01.2013 16:12

Цитата:

Сообщение от nerv_ (Сообщение 228543)
+

kobezzza, если все "так просто", почему движок не делает это за нас?

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

И ещё как мне кажется проблема в том, что такую оптимизацию легко делать в функциональных языках, т.к. функция никак не может влиять на внешний контекст, а JS как известно процедурный и внутри функции могут спокойно переопределяться внешние и глобальные переменные, одним словом вызов функции с одинаковыми параметрами не гарантирует одинаковый результат, поэтому JIT компилятору JS трудно сделать универсальную замену (от сюда кстати также растут проблемы с инлайнингом функции).

ksa 21.01.2013 16:23

Цитата:

Сообщение от kobezzza
Сделано выше, вместо папок и файлов объекты, а всё остальное тоже самое.

Вынужден согласиться... :D
Сам так же уже придумал как с папками разобраться в один цикл, но с 2-мя табличками...

Цитата:

Сообщение от Gozar
Какой ты упрямый, прям как я

Что есть - то есть. :D

Просто в моём случае все делается с базами данных и там я не получу никакого ускорения с другим подходом... Т.к. меня начнут тормозить операции с данными в таблицах. Поскольку одной оперативной памятью там не обойдешся...
От этого и "плясал".

Цитата:

Сообщение от Gozar
Я не умею это делать, но утверждаю, что это невозможно.

Наверно таки не "утверждал"... Более хотел разобраться. :D Поскольку интерес был устойчивым.
И естественно много приобрёл благодаря вам. :thanks: Поскольку просто с задачками "из опереативной памяти" дело имел мало...

megaupload 21.01.2013 16:35

Все идет по плану; Нубы вновь схлеснулись с отцами в поисках установления истины любую ли рекурсию можно заменить циклом?

Ответ конечно очевиден - любую, ибо вызов функций javascript это и есть цикл выполнения синтаксического дерева; Но нубы то этого не знают; Ееееекселент;

Цитата:

Сообщение от Дзен-трансгуманист
Приятного аппетита.

спасибо)

ksa,
ой кому-то припекло))

kobezzza,
красава) все верно описал)

megaupload 21.01.2013 16:41

Пасоны, напишИте регулярку для разворачивания рекурсии в цикл)

ksa 21.01.2013 16:53

Цитата:

Сообщение от megaupload
ой кому-то припекло))

В каком смысле? :blink:
Диспут или обсуждение какой-либо проблемы - обычное дело.

megaupload 21.01.2013 17:02

Да, но кому-то припекло)))


Часовой пояс GMT +3, время: 02:48.