Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: webhope 12. 08. 2011, 15:55:28
-
Zdravím. Tak tohle je výzva pro mě i pro všechny logicky myslící lidi. Na programovacím jazyku ani tak nezáleží, ale já to píšu v php. Nejdříve abych vysvětlil okolnosti/kontext a kód který jsem použil, ale je to poměrně dlouhé, tak nevím jestli to vůbec někdo bude číst až do konce. Jádro problému (shrnuto tučným písmem dole) je až na konci (poslední dvě čáry)
Mám metodu, která načítá soubor do zásobníku po jednom řádku. Při každém novém řádku se přičte hodnot +1 do proměnné n.
$n++
Potom spouštím metodu, která má za úkol omezit zásobník na minimum. Je to dané podle určitých hledacích kritérií, která jsou definovány v poli, ležícím mimo funkci. K tomu je klíčové použít toleranci. Metoda přijímá argument $n a leží v cyklu načítání toho souboru. Navíc leží zanořena v dalším cyklu, který prochází několik slov, která hledám.
Dejme tomu, že máme načteno 71 řádků, a poslední řádky jsou tyto:
#69 - modrá polička
#70 - pěkné auto
#71 - růžové triko
(čísla jsou čísla řádků a to v zásobníku není; načítání řádků pak bude pokračovat)
Vysvětlím metodu na příkladu. Podle aktuálních argumentů a kritérií, metoda pracuje s podmínkami takto:
Jsem zrovna na řádku $n 70 a hledám první slovo (auto). Auto má nastavenu toleranci 0 řádků. Metoda vrátí řetězec
pěkné auto
Další příklad:
Jsem zrovna na řádku $n se rovná 70 a hledám větu, která začíná na "polička" a končí na "auto". Toto vyhledávací kriterium má toleranci 1. Vypočítám toleranci jako $tolerance=$n-1;
polička
pěkné auto
Snad je to až doposud jasné.
Takže to shrnu, stručně to vypadá asi takto:
while (!feof ($fd)){ // CYKLUS
$line = fgets($fd); // NAČÍTÁNÍ ŘÁDKŮ
$buffer .= $line; // UKLÁDÁNÍ DO ZÁSOBNÍKU
for ($i = 0; $i<$this->conf->multiline_search->items_count;$i++) // HLEDÁM SLOVA ZADANÁ V KONFIGURACI
$this->mySearchEngine($buffer, $index, $n); // TOTO JE MOJE METODA NA HLEDÁNÍ
}
Metoda pak používá různé statické proměnné, které uchovávají hodnoty proměnných po skončení metody pro další použití při dalším volání.
A teď se dostávám k jádru problému a to je správný výpočet okamžiku, kdy se má tolerance uplatnit. Jelikož pokud jsem prošel několik řádků a žádný výskyt jsem tam nenašel, nechci se k této staré části vracet.
Kdybych použil rovnou toleranci, která je nastavena pro daný hledaný výraz v konfiguráku, tak výsledek může být, že se prohledává část zásobníku která nemá být hledána.
Příklad:
- Jsem na řádku #70, tolerance je 0 (hledání na současném řádku), hledám slovo auto.
- našel jsem "auto" a vracím řetězec
- jdu na další řádek a provádím hledání pro další výraz ("triko") a mám toleranci 9. Tzn. omezím své hledání v zásobníku na #71-9, tedy řádky #62-71. Tím pádem nesmyslně načítám 8 řádků a hledání se zbytečně komplikuje. Potřebuju prohledat jen dva řádky. samozřejmě, že místo textu "triko" v reálu je text na dva řádky, atp.
Mám na to tento mechanismus:
$tolerance = $this->c->multiline->SearchLimit['before_strings'][$index]; // předběžná hodnota if ($last_tolerance < $tolerance){
if ( $allow_set_tolerance == true ){
$last_tolerance++; // přičíst pouze jednou / když spouštím cyklus poprvé
$allow_set_tolerance = false;
}
$tolerance=$last_tolerance;
if ($last_tolerance+1 == $tolerance) $tolerance = $this->c->multiline->SearchLimit['before_strings'][$index];
}
else if ($last_tolerance >= $tolerance) {$last_tolerance = $tolerance;
}
To co se děje v tomto kódu je postupné navyšování tolerance od 0 do 9. S každým novým řádkem se zvýší tolerance o jedna. Tím pádem se nemá prohledávat to co již bylo prohledáno. Budu pak prohledávat nejdříve 1 řádek navíc, pak 2 řádky, 3 řádky, atd. dokud nenajdu co hledám. Kdyby tolerance byla 0, tak se na hledání vykašlu hned po prvním řádku.
Předchozí algoritmus ještě vyžaduje napočítat kdy se smí připočítávání/navyšování tolerance povolit:
public function mySearchEngine(&$buffer, $index, $n, $sensitive = "i") {
static $last_tolerance;
static $allow_set_tolerance; // pokud tolerance byla nastavena, nepovolit v cyklu na jednom řádku další nastavování tolerance
static $old_n; // pamatuje jestli byl načten nový řádek
static $old_n_2; // pokus
static $n_arr; // pamatuje jestli byl načten nový řádek
$newline = ($old_n +1==$n) ? true : false; // zjišťuje zda byl načten nový řádek
if ($newline){ $old_n = $n; } // nastavit tuto hodnotu pouze pro nový řádek $n, tj. pro hlavní cyklus, ne pro ten druhý vnořený cyklus; jinak by se to přičítalo při procházení hledaných slov
Poznámky:
$old_n - ukládá staré $n, abych dokázal rozpoznat, kdy došlo k přechodu na nový řádek.
Jde o to, že pokud jsem právě přešel na nový řádek, který chci prohledat a tolerance je 0, nebudu nastavovat toleranci 9 ale 1. Výsledek ale není ideální. Protože výsledkem jsou tři řádky
#69 - modrá polička
#70 - pěkné auto
#71 - růžové triko
místo dvou:
#70 - pěkné auto
#71 - růžové triko
Pokud jsem ve výše uvedeném kódu někde udělal chybu (snad ne, ale je to stará verze), tak současný kód je takto, pomocí pole:
public function mySearchEngine(&$buffer, $$index, $n) {
static $last_tolerance;
static $allow_set_tolerance; // pokud tolerance byla nastavena, nepovolit v cyklu na jednom řádku další nastavování tolerance
static $n_arr; // pamatuje jestli byl načten nový řádek
$newline = ($n_arr[0]+1==$n) ? true : false; // zjišťuje zda byl načten nový řádek
$nextline = ($n_arr[1]+1==$n) ? true : false; // pomáhá vymezit rozsah řádků
if ($nextline){
$n_arr[1] = $n_arr[0]; // nastavit na ještě starší hodnotu $n. Když $n je 70, $n_arr[0] je 69 a $n_arr[1] mý být 68
}
$n_arr[0] = $n;
$n_arr[0] - staré $n (předchozí cyklus)
$n_arr[1] - staré $n (z předpředchozího cyklu )
Hledám řešení jak zjistit správný okamžik, kdy se má navyšování tolerance povolit. Je to nastavené na jeden cyklus později, a to funguje, ale potřebuju to opozdit o dva cykly a to nefunguje.
-
Oprava kódu:
Tam jak píšu: "Mám na to tento mechanismus:" a pod tím je kód, tak na prvním řádku za komentářem má být zalomení (podmínka if mi ujela za komentář). Kdyby tu byl admin, co to opraví?
-
Pokud jde jen o velikost zásobníku použijte slovník, načtená slova ukládejte do slovníku a do zásobníku jen odkazy do slovníku. V průběhu zpracování si ke každému slovu poznamenejte poslední řádek, na kterém se vyskytlo. Tím získáte hloubku prohledávání, když uděláte průnik intervalů pro hledaná slova.
-
Pokud jde jen o velikost zásobníku použijte slovník, načtená slova ukládejte do slovníku a do zásobníku jen odkazy do slovníku. V průběhu zpracování si ke každému slovu poznamenejte poslední řádek, na kterém se vyskytlo. Tím získáte hloubku prohledávání, když uděláte průnik intervalů pro hledaná slova.
Je to zajímavý nápad. Nicméně tohle řešení je už prakticky hotové jen vymyslet tu poslední matematickou definici pro upřesnění velikosti zásobníku. Zavádět slovník by znamenalo zase to celé předělávat a strávit min. týden navíc. Chtěl bych se posunout zas dále, takže pokud bych přišel na to jak vypočítat to opoždění $n o dva cykly, bzlo bz to supr.
-
Jo a do toho posledního kódu na konec ještě patří
if ($nextline) $allow_set_tolerance = true;
-
No tak, jsem tu podstatnou část zjednodušil:
static $allow_set_tolerance; // pokud tolerance byla nastavena, nepovolit v cyklu na jednom řádku další nastavování tolerance
static $old_n; // pamatuje jestli byl načten nový řádek
static $delay=-2; // zpoždění
static $debugger_stop;
$debugger_stop++;
$newline = ($old_n+1==$n) ? true : false;
if ($newline){
$delay++;
if ($delay==$n-2 ){ $allow_set_tolerance = true; }
}
$old_n = $n;
Problém je ale v tom, že ať nastavím
$delay=-2 a vzrovnám to podmínkou $n-2, tak výsledek je stále stejný. Zase je tam o jeden řádek navíc (ten přecházející). No já už nevím jak vytvořit zpoždění, aby se ta proměnná $allow_set_tolerance nastavila o dva cykly později.
-
Za prvé a poprvé -> PHP jede krásně na polích, takže je vhodné jich použít. Indexy se můžou použít opakovaně na několik polí a pomocí násobného pole (matice) se dá i zjistit relevance. Načítání dat se spáchá jen jednou, pak už se s nimi dá normálně dělat v paměti. Podobnou logiku pro fórum s texťákem jsem nedávno čistil a snese to v klidu MB takovýchto dat.
Za druhé - logika řešení praví cosi o tom, že máš funkci povědět (ona si to podle kódu nepamatuje), že je vhodný čas hrabat do tolerance - a o kolik. To tam nějak nevidím ( fce(params...,$tolerant=false) ).
Za třetí - použití pomocného pole to zjednoduší v tom pohledu, že pokud je z něj cosi pobráno, tak je to v pomocném poli zapsané a dá se podle toho domáknout, že už tam šťourat netřeba.
$frarr = array(); // výsledky
$fcarr = file($fd); // vytřískni soubor po řádcích
# $fcarr = explode('||',file_get_contents($fd)); // vytřískni ho podle jiného znaku- > tady "||"; s "\r\n" je to prakticky totéž jako o řádek výše
foreach ($fcarr as $i => $v) { // musí vracet jak index ($i), tak hodnotu ($v), jinak to často páchá zvěrstva
$frarr[$i] = (podmínka);
// podmínka by měla být extra funkce s návratovou hodnotou int či při neúspěchu false (něco jako substr_count()), případně pole začátku a konce kuchání s obdobným obsahem
}
$r = ""; // výsledný text
foreach ($frarr as $i => $v) {
if ($v) $r .= $fcarr[$i];
# if ($v[1]) $s = substr($fcarr[$i],0,$v[1]);
# if ($v[0]) $s = substr($s,$v[0]);
# if ($s) $r .= $s;
if (!$v) unset($frarr[$i]);
};
// počet všech řádek:
echo count($fcarr);
// počet použitých řádek:
echo count($frarr);
// text
echo $r;
-
Kalanis - díky za angažovanost. Hold jsem to udělal jinak a pro příště bych mohl zkusit tvoje řešení. Zdá se mi ale, že tvoje řešení nepracuje s víceřádkovým režimem anebo že by to bylo moc komplikované pro multiřádkový režim. Tzn. např. hledám odstavec, kterém předchází "Popis:</div><div>" a končí to na "</div>". Odstavec může být např. na čtyřech, šesti řádcích, ap. Tvoje řešení by našlo pouze např. Popis... leží na řádku #70, /div leží na řádku #75. Pak bych musel otevřít originální soubor, načíst z něj řádky 70-75 a pak použít preg_match(). Takže to taky není až tak jednoduché. Každopádně zatím zůstávám u svého řešení, i kdybych nenašel způsob jak opravit tu chybu opoždění o jeden řádek.
Zatím mě napadá upravit část kódu s podmínkami na porovnání $last_tolerance a $tolerance). Tam se nastavuje velikost tolerance. Zkusit upravit tu toleranci, což by snad mělo být v momentě kdy toleranci nastavuji podle konfiguráku. Jenže pak je tam to plynulé navyšování tolerance ... last_tolerance++ a jelikož je to statická proměnná uložená v paměti, nestačilo by dát tam např. last_tolerance=last_tolerance-1; protože to by se zase opakovalo v cyklu a výsledek by byl tolerance 0. Čili problém je najít ten správný okamžik.
-
To, že by našel jen počátek a konec, je pravda. Ale hned vzápětí se přece dá dodat logika, která označí k sebrání i ty zbylé řádky mezi, ne? (start:0, cíl:délka_řetězce, jednou for...) Proto tam ta zakomentovaná ripovací část.
A na co otevírat originální soubor, když už ho máš típnutý v paměti (v tom poli)? Já navíc do získaného textu nezasahuju, jen češu výsledky.
Navíc file() a file_get_contents() může dostat jeko cestu k souboru vzdálenou url.
Jo, cca 3 měsíce zpátky bych to dělal podobně, dneska ale holt už ne. Na ovoce pro ipv6 je prostě potřeba jiný kalibr.
-
Tzn. např. hledám odstavec, kterém předchází "Popis:</div><div>" a končí to na "</div>". Odstavec může být např. na čtyřech, šesti řádcích, ap.
Chápu to správně, že používáš regulární výrazy tam, kde bys měl použít DOM?
-
Tzn. např. hledám odstavec, kterém předchází "Popis:</div><div>" a končí to na "</div>". Odstavec může být např. na čtyřech, šesti řádcích, ap.
Chápu to správně, že používáš regulární výrazy tam, kde bys měl použít DOM?
to ne. je to php, to pracuje na strane serveru ne na strane klienta. to neni JS
-
webhope webhope: a? http://php.net/manual/en/book.dom.php
-
Přiznám se, že logiku Tvojeho kódu moc nechápu, a co jsem pochopil, je podivný (on i poopis zadání je dosti nepochopitelný).
-
Nicméně zcela určitě to Tvoje řešení není dobrý. IMHO správnej postup je takovej, projet pole, někam si ukládat dva poslední nalezený řádky s hledanejma termama, při každym nalezení termu zistit, jestli to nevyhovuje (např na řádku 71 jsem našel triko, kouknu, na term auto, ten jsem našel na řádce 70, tzn. mám dvojici vyhovující toleranci 1).
-
No a při nalezení dvojice buďto (pokud max povolená tolerance je známá předem) vypíšu, nebo uložím spolu s tolerancí a při nalezení další ji nahradím (má-li menší toleranci), přeskočím (větší), popř. přidám (stejnou).
-
Blbnu se dvěma výskytama, stačí jeden. Nevim, jak jsem na dva přišel...
-
Chápu to správně, že používáš regulární výrazy tam, kde bys měl použít DOM?
to ne. je to php, to pracuje na strane serveru ne na strane klienta. to neni JS
PHP také umí pracovat s DOM. A velmi dobře. Procházení stromu je jednodušší, než analyzovat soubor řádek po řádku.
Pokud potřebuješ porovnávat záznamy na více řádcích použij automat. Moorův nebo Mealyho, to je vcelku jedno. Ale na získávání tokenů z HTML nebo XML použij raději DOM.
-
Díky za odpovědi. Hledání pomocí polí si nechám na příště.
Ten XML modul, který obsahuje DOM se musí stáhnout samostatně? Používám Wamp server a nezdá se, že by to v tom bylo obsažené (je to ale starší verze Wampu).
-
Ten XML modul, který obsahuje DOM se musí stáhnout samostatně? Používám Wamp server a nezdá se, že by to v tom bylo obsažené (je to ale starší verze Wampu).
A to je tak těžké použít Google?
Buď použiješ modernější DOMdocument nebo starší SimpleXML, příp. XMLReader. K požadovanému účelu poslouží všechny, liší se způsobem ovládání a schopnostmi. Parser článků root.cz mám na 25 řádcích i s generováním výstupu.
-
No mě se ten můj script povedlo úspěšně opravit.
Tady je řešení:
Přidal jsem jednu proměnnou static do části, která rozhoduje o opravě tolerance.
/** VÝPOČET SPRÁVNÉ TOLERANCE */
$tolerance = $this->c->multiline->SearchLimit['before_strings'][$index]; // předběžná hodnota
/* Vysvětlení: Nemohu přidávat větší toleranci např. 9. když předchozí
řádek měl toleranci 0 nebo 1. Toleranci je možné zvýšit na novém
řádku o jedna, ale pokud zůstávám na tom samém řádku (v cyklu $i/$index),
pak neměnit toleranci. Tolerance se takto uplatňuje jen na hledání dopředu. */
if ($last_tolerance < $tolerance){ // HLAVNÍ PODMÍNKA část A)
if (!$tolerance_correction_set && $tolerance >= 1){
$last_tolerance--;
$tolerance_correction_set = true;
}
if ( $allow_set_tolerance == true ){
$last_tolerance++; // přičíst pouze jednou / když spouštím cyklus poprvé
$allow_set_tolerance = false; // Když začalo postupné navyšování tolerance, zmenšit toleranci o 1. Tím se vyvolá opoždění, a do hledání nebude zahrnutý ten, řádek, který jsem už jednou procházel.
}
$tolerance=$last_tolerance;
if ($last_tolerance+1 == $tolerance) $tolerance = $this->c->multiline->SearchLimit['before_strings'][$index];
}
else if ($last_tolerance >= $tolerance) { // HLAVNÍ PODMÍNKA část B)
$last_tolerance = $tolerance;
$tolerance_correction_set = false; // ZASTAVIT ODEČÍTÁNÍ
Jsem šťastný, že se mi to povedlo dotáhnout do konce. Vypadalo to fakt beznadějně. I když jste přišli s dejme tomu lepším řešením, tohle přeci jen bylo rychlejší na dokončení.
-
Kalanis:
Dneska jsem zkoušel ten tvůj kód:
# $fcarr = explode('||',file_get_contents($fd))
A lámal si hlavu proč to nejede.
Takhle je to správně:
# $fcarr = explode("||",file_get_contents($fd))
-
# $fcarr = explode('||',file_get_contents($fd))# $fcarr = explode("||",file_get_contents($fd))
Nějak jsem nepochpil rozdíl, chyba byla asi v něčem jiném.
-
Kit:
Sorry, ale do uvozovek jsem dal \n, takto:
Toto mi ve Windows nerozparsovalo řádky a hodilo to vše pod jeden index:
$temp_arr = explode('\n',file_get_contents($path));
A toto funguje správně:
$temp_arr = explode("\n",file_get_contents($path));
Jinak jsem ale zjistil, že tam je třeba dát trim na konec řádku, jinak to zanechává zalomení, ord. 13 na posledním řádku.
$this->options_count = count($temp_arr);
foreach ($temp_arr as $line): // odstranit zalomení ord 13 (při print_r() není vidět!)
$line = explode(",",$line);
$last = count($line)-1;
$line[$last] = trim($line[$last]);
$this->options[] = $line;
endforeach;