Показать сообщение отдельно
  #20 (permalink)  
Старый 21.01.2013, 15:52
Аватар для kobezzza
Быдлокодер;)
Отправить личное сообщение для kobezzza Посмотреть профиль Найти все сообщения от kobezzza
 
Регистрация: 19.11.2010
Сообщений: 4,338

Сообщение от ksa Посмотреть сообщение
Я писал про "правильную" рекурсию.
Т.е. когда рекурсивный подход применяется как раз из-за невозможности применения циклов.
Я как не странно тоже.
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 раз быстрее рекурсивного (в зависимости от браузера).

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

Последний раз редактировалось kobezzza, 21.01.2013 в 15:59.
Ответить с цитированием