Autor Zpráva
Psychopat
Profil
Dobrý den,

Chtěl bych poprosit někoho znalého rekurzivních funkcí, jestli by mohl buď přepsat rekurzi na cyklus, nebo funkci vylepšit tak aby byla rychlejší.

Je to funkce na porovnání dvou textů a vyhledání rozdílu v nich.
function diff($old, $new){
	$maxlen = 0;
	// Go through each old line.
	foreach($old as $oindex => $ovalue){
		// Get the new lines that match the old line
		$nkeys = array_keys($new, $ovalue);
		// Go through each new line number
		foreach($nkeys as $nindex){
			if(isset($matrix[$oindex - 1][$nindex - 1])) {
				$matrix[$oindex][$nindex] = $matrix[$oindex - 1][$nindex - 1] + 1;
			} else {
				$matrix[$oindex][$nindex] = 1;
			}
			if($matrix[$oindex][$nindex] > $maxlen){
				$maxlen = $matrix[$oindex][$nindex];
				$omax = $oindex + 1 - $maxlen;
				$nmax = $nindex + 1 - $maxlen;
			}
		}
	}
	if($maxlen == 0) return array(array('d'=>$old, 'i'=>$new));

	return array_merge(
		diff(array_slice($old, 0, $omax), array_slice($new, 0, $nmax)),
		array_slice($new, $nmax, $maxlen),
		diff(array_slice($old, $omax + $maxlen), array_slice($new, $nmax + $maxlen))
	);
}
TomášK
Profil
Psychopat:
Předpokládám, že WMS_diff má být diff, což je ta rekurze. Bylo by vhodné pár slovy popsat, jak to funguje, ušetří to luštění. Každopádně dotaz je trochu podivný - máte pomalý algoritmus v pomalém jazyce a řešíte rekurzivní volání.
* Změnou algoritmu jde ušetřit složitost, teď je něco jako O(n^2 log(n)), určitě to jde O(n log(n)). Navíc výsledky uvedeného algoritmu nebudou vždy totéž, jako vrací klasický diff - ty texty na sebe lze lépe napasovat (měřeno počtem operací smazání/přidání/nahrazení řádku) než to dělá tento algoritmus.
* Změnou jazyka to jde zrychlit mnohonásobně (tipuju 10x-100x).
* Změna rekurze na cyklus ušetří nejvýš procenta a myslím, že ani to ne.

Pokud potřebujete rychlý diff, pak bych se poohlédnul po nějaké existující implementaci - třeba unixovém diffu. Pokud chcete rychlý vlastní diff, pak bych použil jiný jazyk, pokud nelze, tak jiný algoritmus. Po vyčerpání předchozího bych začal profilovat kód, kolik co trvá, ve chvíli, kdy bude rekurze nejpomalejší část, tak už máte vyhráno.
Psychopat
Profil
TomášK:
WMS_diff -> kód jsem opravil, již je tak jak má být.

Jinak to není z mé hlavy:
http://paulbutler.org/archives/a-simple-diff-algorithm-in-php/

Jak jsem nyní hledal kde jsem to vzal, našel jsem i novejší verzi algoritmu, ale v pythonu.
http://paulbutler.org/archives/simplediff-in-python/

Autor píše, že stará verze vytváří pole o velikosti druhé mocniny vstupu, kdežto nová verze si vystačí s polem o stejné velikosti jako vstup. Takže to vypadá že bude stačit přeložit novou verzi do PHP.

Kód potřebuji v PHP do webové aplikace.
Když bude kód tak rychlý, jak jen to dovolí daný jazyk, budu spokojen.
Ten požadavek na přepis do cyklu není nutný, jen bych líp pochopil jak to funguje.
Kód na vstupu očekává dva texty explodované do pole, a na výstupu je podobné následujícímu:
Array
(
    [0] => Array
        (
            [d] => Array
                (
                )
            [i] => Array
                (
                )
        )
    [2] => bezezmeny
    [3] => Array
        (
            [d] => Array
                (
                    [0] => odstraneno
                )

            [i] => Array
                (
                    [0] => pridano
                )

        )
    [4] => bezezmeny
)


Vzhledem k té novejší variantě by mělo stačit přeložit python do PHP.
TomášK
Profil
Psychopat:
Algoritmus vyměňuje rychlost za jednoduchost, i autor ho označuje jako simple. Najde nejdelší společný podřetězec, vyřadí ho a pak se rekurzivně zavolá na zbývající části. Tento postup nemusí dávat optimální výsledky, ale zřejmě celkem dobré ano. Najít nejdelší společný podřetězec lze v lineárním čase a prostoru pomocí suffix trie nebo lépe suffixového pole, ale netuším, jestli existuje implementace v php a jak moc velký musí být vstup, aby se to vyplatilo konstruovat. Efektivní algoritmy pro diff na internetu určitě budou, jen ne v php, např. tu v javě, implementace GNU diff v C. Otázka, jestli se to vyplatí implementovat - pokud to chcete používat na porovnání stořádkových textů, pak spíš ne, pokud stostránkových, pak ano.
Urychlit by to mohl i preprocessing, kdy by se řádky převedly na znaky v nějaké dostatečně velké abecedě, výše uvedený postup pokaždé porovnává celé řádky.

Vaše odpověď

Mohlo by se hodit


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: