рекурсия, как отдать путь до найденного массива во вне

predator · 17 Ноя 2010

grigori написал(а):
я вижу естественное решение маленьким конечным автоматом (или 2мя) в 1 проход

объясни подробнее, как конечный автомат или два в один проход обработают строку с бесконечным вложением вариантов?
лучше всего мелкий пример

fixxxer · 17 Ноя 2010

охоспади

какие евалы? какая рекурсия?

PHP:

<?php

function getNestedArrayElementByPath(array $data, array $path) {
    $ptr = &$data;
    foreach ($path as $element) {
        if (is_array($ptr) && isset($ptr[$element])) {
            $ptr = &$ptr[$element];
        } else {
            return false;
        }
    }
    return $ptr;
}

$data = array(
    'a' => array(
        'b' => array(
            'c' => array(
                'd' => array(
                    'e' => 'test'
                )
            )
        )
    )
);

$path = array('a', 'b', 'c', 'd', 'e');

var_dump(getNestedArrayElementByPath($data, $path));

AmdY · 17 Ноя 2010

fixxxer
ну вот, пришёл и всё испортил. у меня есть похожая функция, но вот откуда-то у меня сильная нелюбовь к ссылкам не знаю, срочно нужно поправить.

grigori · 17 Ноя 2010

predator написал(а):
объясни подробнее, как конечный автомат или два в один проход обработают строку с бесконечным вложением вариантов?
лучше всего мелкий пример

что именно объяснить - как автоматом парсить строку?
читаешь статью
как создавать вложенные структуры?
читаешь про массивы
тебе автомат написать?
а контрольную по вышке тебе не решить?

grigori · 17 Ноя 2010

>откуда-то у меня сильная нелюбовь к ссылкам
когда-то их юзали везде и не к месту,
"$ptr = &$ptr[$element];" с простым присваиванием будет работать точно так же, учитывая ссылочную природу переменных

predator · 18 Ноя 2010

всем спасибо за внимание и участие ))
вот что получилось:
1) Конечный автомат

PHP:

/**
 * Парсинг конструкций аля '{dog|cat} the {food {in|out} the air {some|more|hm}} i liked {car|bike|u-bann}'
 * на основе конечных машин (Finite State Machine)
 *
 * @category Project
 * @package Project_Articles
 * @license http://opensource.org/licenses/ MIT License
 */
class Project_Articles_Rewrite_FSM {

	private $_content=''; // Буфер данных
	private $_intLength=0; // Длина буфера
	private $_intPos=0; // Позиция курсора в буфере

	private $_line=0;
	private $_column=0;

	private $_error='';

	// Остальные символы имеют код 1
	private $_inState=array(
		'{'=>2, // начало вариантов
		'}'=>4, // конец варианта и выход из рекурсии
		'|'=>3, // конец варианта
		null=>4 // конец символов - аналогичен концу варианта, только в данном случае вариантом считается сам текст
	);

	private $_parserAutomat=array(
		/*
		-1 ошибка
		0 начало разбора - ожидаем символ или левую скобку
		1 получили символ, накапливаем их - ожидаем всё что угодно
		2 получили {. идём в рекурсию - после ожидаем символ или ещё одну левую скобку
		3 получили |. разбираемся с вариантом - ожидаем символ, любую скобку
		4 получили }. разбираемся с вариантом и выходим из рекурсии - ожидаем всё что угодно
		*/
		// состоян 0, 1, 2, 3, 4
		'1'=>array( 1, 1, 1, 1, 1 ), // символ
		'2'=>array( 2, 2, 2, 2, 2 ), // левая скобка
		'3'=>array(-1,3,-1,-1, 3 ), // палка
		'4'=>array(-1, 4,-1,4, 4 ), // правая скобка или конец строки
	);
	private $_state=0;

	public function setData( $_str='' ) {
		$this->_content=$_str;
		$this->_intLength=strlen( $_str );
		return $this;
	}

	public function getError() {
		return $this->_error;
	}

	private function updateStaying() {
		if ( $this->_content[$this->_intPos]=="\n" ) {
			$this->_line++;
			$this->_column=0;
		} else {
			$this->_column++;
		}
	}

	private function scan() {
		while ( $this->_intPos<$this->_intLength ) {
			$symbol=$this->_content[$this->_intPos];
			$this->updateStaying();
			$this->_intPos++;
			return $symbol;
		}
		return null;
	}

	public function parse() {
		$_arrVariation=array();
		$_arrVariants=array();
		$_strCurentVariant='';
		while( 1 ) {
			$symbol=$this->scan(); // получаем символ от сканера
			$instate=isSet( $this->_inState[$symbol] ) ?$this->_inState[$symbol]:1; // Устанавливаем код, подаваемого на вход автомата, символа
			$prev=$this->_state;
			$this->_state=$this->_parserAutomat[$instate][$this->_state];
			switch( $this->_state ) {
				case 1: // получили символ, накапливаем их - ожидаем всё что угодно
					$_strCurentVariant.=$symbol;
				break;
				case 2: // получили {. идём в рекурсию - после ожидаем символ или ещё одну левую скобку
					$_strCurentVariant.='%s';
					$_arrVariation[]=$this->parse();
				break;
				case 3: // получили |. разбираемся с вариантом - ожидаем символ, любую скобку
					if ( !empty( $_arrVariation ) ) {
						$_arrGenerated=$this->everyPossibleVariants( $_strCurentVariant, $_arrVariation );
						$_arrVariants=array_merge( $_arrVariants, $_arrGenerated );
						$_arrVariation=array();
					} else {
						$_arrVariants[]=$_strCurentVariant;
					}
					$_strCurentVariant='';
				break;
				case 4: // получили }. разбираемся с вариантом и выходим из рекурсии - ожидаем всё что угодно
					if ( !empty( $_arrVariation ) ) {
						$_arrGenerated=$this->everyPossibleVariants( $_strCurentVariant, $_arrVariation );
						$_arrVariants=array_merge( $_arrVariants, $_arrGenerated );
					} else {
						$_arrVariants[]=$_strCurentVariant;
					}
					return $_arrVariants;
				break;
				default: throw new Exception( Core_Errors::DEV.'|line: '.$this->_line.', col: '.$this->_column.' in "'.$this->_content.'"' ); break 2;
			}
		}
		return array();
	}

	private function everyPossibleVariants( $_str='', $_arr=array() ) {
		$f=new Core_Math_Combiner();
		$f->setData( $_arr );
		foreach($f as $e) {
			$arrRes[]=vsprintf( $_str, $e );
		}
		return $arrRes;
	}
}

1) Комбинаторика

PHP:

/**
 * Комбинирование массивов для получения всех возможных комбинаций
 * в порядке поступления массивов
 * т.е. напрмер array( array( dog, cat ), array( food, tooth ) ) преобразуются в 
 * dog food
 * dog tooth
 * cat food
 * cat tooth
 *
 * @category Core
 * @package Core_Math
 * @copyright Copyright (c) 2005-2010, Rodion Konnov
 * @license http://opensource.org/licenses/ MIT License
 */
class Core_Math_Combiner implements Iterator {
	protected $data=null; // масси массивов
	protected $limit=null; // количество возможных комбинаций (|arr1|*|arr2|...*|arrN|)
	protected $current=null;

	public function __construct() {
		$this->setData( func_get_args() );
	}

	public function setData( $_arr=array() ) {
		$this->data=array_reverse( $_arr );
		$this->init();
	}

	private function init() {
		$this->rewind();
		$this->limit=array_product(array_map('count', $this->data));
	}

	public function current() {
		/* this works like a baseX->baseY converter (e.g. dechex() )
		   the only difference is that each "position" has its own number of elements/"digits"
		*/
		// <-- add: test this->valid() -->
		$rv=array();
		$key=$this->current;
		foreach( $this->data as $e) {
			array_unshift( $rv, $e[$key % count($e)] );
			$key=(int)($key/count($e));
		}
		return $rv;
	}

	public function key() { return $this->current; }
	public function next() { ++$this->current; }
	public function rewind () { $this->current=0; }
	public function valid () { return $this->current < $this->limit; }
}

1) Использование

PHP:

$fsm=new Project_Articles_Rewrite_FSM();
$_arrVariants=$fsm->setData( '{dog|cat} the {food {in|out} the air {some|more|hm}|test} i liked {car|bike|u-bann}' )->parse();

тему можно закрывать, или давайте поговорим об этом )

predator · 19 Ноя 2010

ещё можно присовокупить защиту vsprintf от имеющихся в тексте знаков процента - %
для всего текста вначале их надо удвоить, а когда получили конец текста при разборе
после генерации конечных вариантов надо заменять взяд %% на %
как-то так

grigori · 20 Ноя 2010

сразу видно: будущий Герой Дебага

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

Вурдалак · 20 Ноя 2010

Надо избегать рекурсии. В данном случае она не нужна.

predator · 23 Ноя 2010

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

если у вас есть мысли по этому поводу
я буду рад их услышать

tz-lom · 23 Ноя 2010

predator
не любую рекурсию можно превратить в итерацию
пример превращения:

PHP:

function fact($n)
{
if($n>1)return $n*fact($n-1);
else return 1;
}

function nfact($n)
{
$res = 1;
while($n>1){$res*=$n--;}
return $res;
}

и пример невозможности:

PHP:

function fuuuuuuuu($n)
{
if($n>1)return $n*fuuuuuuuu($n); //stack will die here
else return 1;
}

флоппик · 23 Ноя 2010

Почему это второй пример нельзя вывернуть в итерацию?

PHP:

function fuu ($n)
{
  if ($n <= 1) return  1;
  $serult = 1;
  while (true)
  {
    $result = $result * $n;
  }
}

Просто сама рекурсия в твоем примере бесконечна и бессмысленна.

tz-lom · 23 Ноя 2010

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

флоппик · 23 Ноя 2010

«Плохо - хорошо» это не та категория, которой можно измерять алгоритмы. Рекурсия требует больше ресурсов на получение результата, чем линейный алгоритм, при этом выигрывая лишь в читаемости.

И не понимаю, причем тут математики.

tz-lom · 23 Ноя 2010

флоппик
на счёт ресурсов весьма спорный вопрос,в ручную контекст исполнения хранить накладнее чем вам это сделает интерпретатор
плюс код вроде

PHP:

function rec(...){ //bunch of code
rec();
//bunch of code }

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

флоппик · 23 Ноя 2010

tz-lom написал(а):
флоппик
на счёт ресурсов весьма спорный вопрос

Даю наводку - стек вызовов — не резиновый. И его ресурсная "стоимость" значительно выше, чем затраты на память.

Я помню, как мой препод в свое время (лет 12 назад) это наглядно показал на примере турбо паскаля - факториал 6 получить рекурсивно на паскале было нельзя - стека не хватало.

Во вторых, любой рекурсивный алгоритм можно развернуть в линейный.

В третьих, "неприглядно" - тоже не показатель. Интерпретатору безразлична "красота" кода.

tz-lom · 23 Ноя 2010

флоппик
факториал 6ти в TP7.0 это всего 5 вызовов внутри рекурсии и 1 вызов самой функции,я уверен что 7й TP это запросто сделает
ресурсная ёмкость стека НИЖЕ чем массивов,потому что его не надо аллоцировать

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

флоппик · 23 Ноя 2010

Причем тут обфусцированый код?

tz-lom · 23 Ноя 2010

флоппик
я к тому что "красота" и "неприглядно" можно вполне относить к критериям качества кода

Вурдалак · 23 Ноя 2010

tz-lom написал(а):
флоппик
факториал 6ти в TP7.0 это всего 5 вызовов внутри рекурсии и 1 вызов самой функции,я уверен что 7й TP это запросто сделает
ресурсная ёмкость стека НИЖЕ чем массивов,потому что его не надо аллоцировать

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

— бред сивой кобылы.

рекурсия, как отдать путь до найденного массива во вне

web designer

К.О.

Пью пиво

( ͡° ͜ʖ ͡°)

( ͡° ͜ʖ ͡°)

web designer

web designer

( ͡° ͜ʖ ͡°)

Продвинутый новичок

web designer

Продвинутый новичок

promotor fidei

Продвинутый новичок

promotor fidei

Продвинутый новичок

promotor fidei

Продвинутый новичок

promotor fidei

Продвинутый новичок

Продвинутый новичок