| Autor | Zpráva | ||
|---|---|---|---|
| xlifer Profil |
Jak postupovat resp. jakou logiku použít pro posílání dat do našeptávače?
Dejme tomu, že budeme mít dazabázi 20.000 záznamů. Při takovém množství určitě není vhodné s ohledem na zátěž posílat vždy dotaz SQL na vybrání shody dle vepsaného výrazu. Moc díky za vaše názory a tipy k tématu. |
||
| Chamurappi Profil |
#2 · Zasláno: 20. 9. 2010, 22:16:40 · Upravil/a: Chamurappi
Reaguji na xlifera:
Předgeneruj si v paměti strom všech (rozumných) možností uživatelského vstupu a ke každé ulož deset nejhledanějších slov. Budeš potřebovat docela hodně paměti, ale hrábnutí pro data bude prakticky bezzátěžové. (Přesně stejné zadání jsem měl na stole před pěti lety a ten můj našeptávač funguje dodnes.) |
||
| xlifer Profil |
#3 · Zasláno: 20. 9. 2010, 22:58:10
Rozumím a měl jsem vpodstatě takové řešení tak trochu v hlavě, ale chtěl jsem si to potvrdit a případně i zjistit zda není i další řešení.
Ale ten strom se bude asi muset nějak aktualizovat, takže na to asi automat úplně nepůjde, že? Jak to myslíš s tím, že bude potřeba hodně paměti??? |
||
| Chamurappi Profil |
#4 · Zasláno: 20. 9. 2010, 23:12:43
Reaguji na xlifera:
„ten strom se bude asi muset nějak aktualizovat“ Ano, jednou za čas si sáhneš do databáze pro všechna slova a aktuální počty a necháš strom přegenerovat — to bude jednorázový úkon, může se dít někdy v noci. „Jak to myslíš s tím, že bude potřeba hodně paměti???“ I když pro potřeby stromu ořežeš diakritiku, zůstane ti pořád 26 písmen. S každým dalším znakem poroste exponenciálně velikost a i když řadu větví můžeš včas prořezat při procesu generování, protože nikam nevedou, ten zbytek docela rychle naroste. Počítej minimálně s desítkami megabajtů, možná i stovkami (kdybys chtěl důkladné našeptávání i u delších slov a frází). |
||
| xlifer Profil |
#5 · Zasláno: 21. 9. 2010, 00:40:17 · Upravil/a: xlifer
Takže strom zhotovím nějak takto:
obsah databáze (4 záznamy): první záznam databáze druhý záznam databáze treří záznam databáze čtvrtý záznam databáze z toho vygenerovany strom bude (tučně): #C ctvrty #D druhy databaze #P prvni #T treti #Z zaznam Jdu na to dobře? |
||
| Tori Profil |
#6 · Zasláno: 21. 9. 2010, 01:14:18
Chamurappi:
„Předgeneruj si v paměti strom“ Můžu se jen zeptat, jakou paměť myslíte, když se dále mluví o řádově desítkách až stovkách MB? HEAP tabulky, velký soubor na serveru, či co? V dalších zdejších vlánkech o našeptávači jsem zatím nenašla vysvětlení, jak to vlastně funguje. Díky moc za případné objasnění. |
||
| Chamurappi Profil |
#7 · Zasláno: 21. 9. 2010, 13:26:15
Reaguji na xlifera:
„Jdu na to dobře?“ Nejsem si jist, že se chápeme. Kdybys měl po seřazení podle hledanosti tento seznam slov: • arafón • auto • ara • arsen • autobus • zvoneček • arabela … a kdybys chtěl našeptávat vždy nanejvýš tři slova, tak by strom vypadal nějak takhle: | +- A -+- slova: arafón, auto, ara | | | +- R -+- slova: arafón, ara, arsen | | | | | +- A -+- slova: arafón, arabela | | | | | | | +- F --- slova: arafón | | | | | | | +- B --- slova: arabela | | | | | +- S --- slova: arsen | | | +- U -+- slova: auto, autobus | | | +- T -+- slova: auto, autobus | | | +- O --- slova: autobus | +- Z -+- slova: zvoneček Reaguji na Tori: „HEAP tabulky, velký soubor na serveru, či co?“ Nedělám v PHP. Serverová aplikace v ASP.NET si žije svým životem, který není omezený životem HTTP požadavku a odpovědi. Nadeklaruji-li proměnnou jako static, zůstane v paměti (fyzické nebo virtuální, to je celkem fuk) naživu v použitelném stavu v podstatě natrvalo (dokud neumře celý proces). Kdykoliv si na ni mohu přímo sáhnout a nemusím řešit její uskladnění či načtení. Prostě tam jen tak … visí :-)
|
||
| xlifer Profil |
#8 · Zasláno: 21. 9. 2010, 14:12:05 · Upravil/a: xlifer
Reaguji na Chamurappi:
Teď když se dívám na ten příklad stromu, tak chápu na 100% :-) Díky moc. Akorát přemýšlím jak napsat aplikaci v php, která mi takový strom automaticky vytvoří, ale s tím si už nějak poradím... Kdyby to šlo vždy přímo na dotaz db, tak není nic jednoduššího než SELECT * FROM tabulka WHERE slovo LIKE "ara%" Ale nedovedu si představit, tak velkou zátěž na server při každém dotazu do db na stisk klávesy z vyhledávacího pole :-) |
||
| Joker Profil |
#9 · Zasláno: 21. 9. 2010, 15:04:35
xlifer:
„Akorát přemýšlím jak napsat aplikaci v php, která mi takový strom automaticky vytvoří“ Možný algoritmus: - SELECT všech slov v databázi, [kde počet hledání je větší než nějaký limit,] seřadit podle počtu hledání sestupně. - Pro každé vrácené slovo: - - Jako aktuální uzel nastav kořen stromu - - Pro každé písmeno slova: - - - Jako aktuální uzel nastav dané písmeno uvnitř aktuálního uzlu - - - Připoj slovo na konec seznamu slov pro aktuální uzel |
||
| xlifer Profil |
#10 · Zasláno: 21. 9. 2010, 19:23:25
Chamurappi:
A některé našeptávače zobrazují navržené dotazy až při minimálně třech znacích, ale algoritmus bude vlastně stejný akorát od 3 písmene a dále, resp. jako první znak budou 3znaky:-) |
||
| Alphard Profil |
#11 · Zasláno: 21. 9. 2010, 20:29:28
xlifer:
„Akorát přemýšlím jak napsat aplikaci v php, která mi takový strom automaticky vytvoří“ Vhodnost generování celého stromu záleží na počtu požadavků na vyhledávání. U menších aplikací bude zřejmě vhodnější lazy přístup. Výsledek se vygeneruje až ve chvíli, kdy je potřeba, a uloží se pro příště (s nějakou dobou expirace). Tori: „HEAP tabulky, velký soubor na serveru, či co?“ HEAP (u MySQL nově MEMORY) tabulky mají omezenou velikost. Opět záleží na rozsahuje dat, ale pro začátek bych asi zůstal u normální tabulky s vhodně nastavenými indexy. |
||
| Nox Profil |
#12 · Zasláno: 21. 9. 2010, 20:53:30 · Upravil/a: Nox
teoreticky by šlo (a možná bylo nejlepší?) memcached, ale pokud to má být na hosting, tak to asi nepůjde (pokud vím tak tam moc nebývá povolené bohužel)... šlo by mít třeba definovaný interface a udělat 2 objekty které by ho implementovaly, jeden DB, jeden memcached a podle dostupnosti by se vytvořil příslušný, díky stejnému interface by byla i stejná práce
|
||
| xlifer Profil |
#13 · Zasláno: 23. 9. 2010, 13:15:49 · Upravil/a: xlifer
A co prohledávat shody takto:
Pro všechny nejhledanější slova vytvořit array seznam a pak prohledat. Nevím jak moc to je efektivní, ale přijde mi to docela vhodé a funguje přesně na co je potřeba :-) $sl_a = Array(
"arafón",
"auto",
"ara",
"arsen",
"autobus",
"arabela",
);
function vyber($koren)
{
Global ${"sl_".SubStr($koren,0,1)};
foreach(${"sl_".SubStr($koren,0,1)} as $key => $slovo)
{
if (StrPos("~".$slovo, $koren)>0):
$s .= $slovo."<br>";
endif;
}
Return $s;
}
echo vyber("ara");Vypíše: arafón ara arabela Samozřejmě výstup $s se upraví pro parsování našeptávače. |
||
| Chamurappi Profil |
#14 · Zasláno: 23. 9. 2010, 15:09:22
Reaguji na xlifera:
„Nevím jak moc to je efektivní, ale přijde mi to docela vhodné“ Mně ani moc ne. Rozházet si slova do 26 polí podle prvního znaku mi připadá nesystémové a prohledávání pole má (předpokládám i v PHP) lineární časovou složitost. |
||
| xlifer Profil |
#15 · Zasláno: 23. 9. 2010, 15:32:36 · Upravil/a: xlifer
Netvrdím, že je to zcela cool řešení, ale otázkou je,
zda je to opravdu, tak moc časově náročné na zpracování... Možná jestli by někdo dokázal napsat lepší skriptík na řešení stromu, tak bych ocenil? |
||
| Chamurappi Profil |
#16 · Zasláno: 23. 9. 2010, 16:54:44
Reaguji na xlifera:
„otázkou je, zda je to opravdu, tak moc časově náročné na zpracování…“ Záleží na konkrétní situaci a na tom, jak moc je „tak moc“. Tomu „cool řešení“ se stromem se chceš vyhnout jen proto, že bys nad ním musel víc přemýšlet? :-) |
||
| xlifer Profil |
#17 · Zasláno: 23. 9. 2010, 17:06:55 · Upravil/a: xlifer
Chamurappi:
Nevím si rady jak nakódovat v php to sestavení stromu, který jsi mi dával jako příklad. Pochopil jsem princip, ale nedaří se mi. Možná kdyby jsi byl té dobroty a aspoň nějaké malé demo kódu php jak na to, tak bych ocenil? :-) Joker sice napsal postup, ale to je hodně obecně... |
||
|
Časová prodleva: 3 dny
|
|||
| smickar Profil |
#18 · Zasláno: 26. 9. 2010, 16:15:58
Nevyužije takový strom v ČR maximálně Seznam.cz ? Přijde mi, že všem ostatním stačí lazy přístup. Na Bazos.cz mám denně téměř 1 mil volání našeptávače a negeneruje to ani 1% zátěže serveru. Netuším kolik to zatěžuje, protože po vypnutí funkce na grafech zatížení není nic poznat. Čili odhadem i kdyby se toho volalo 10x tolik, což je deset milionů za den tak není na jednom sql serveru problém. Čili by mě opravdu zajímalo proč to řešit stromem? Osobně si myslím, že by ani Seznam s tím něměl mít výkonostní problém. Zajímalo by mě jestli ten strom spíš problém nevytvoří.
|
||
| xlifer Profil |
#19 · Zasláno: 26. 9. 2010, 16:43:18
smickar:
Zajimavý názor a docela by mě zajímala reakce zde ostatních? |
||
| xlifer Profil |
#20 · Zasláno: 26. 9. 2010, 16:45:13 · Upravil/a: xlifer
smickar:
Takže to řešíš dotazem přímo do databaze a vyhledáváš shody v db nejhledanějších slov, které si tam ukládaš nebo jakým způsobem výsledky pro našeptávač sestavuješ? |
||
| smickar Profil |
#21 · Zasláno: 26. 9. 2010, 17:38:31
xlifer: JJ tak nějak, data se jen jednou za čas (v noci) pročistí od blbostí, agregují a uloží do datbulky nad kterou se hleda klasicky přes select * from tabulka where slovo like '%abc%'.
|
||
| xlifer Profil |
#22 · Zasláno: 26. 9. 2010, 19:51:21
[#21] smickar
Tak jsi na to šel cestou, kterou jsem chtěl také relizovat a teď je otázkou, zda to opravdu není lepší cesta než převádět data do stromu a pak ze stromu vypisovat? Já jsem totiž podobného názoru, že se věci někdy řeší zbytečně složitě a pak funguje nejlépe obyč. řešení, ale není to moc přijatelné pro ostatní :-) |
||
| Chamurappi Profil |
#23 · Zasláno: 26. 9. 2010, 23:48:48
Reaguji na xlifera:
„docela by mě zajímala reakce zde ostatních“ Vycházel jsem z tvého zadání — nechtěl jsi posílat s každým požadavkem SQL dotaz. To, jestli je takové zadání vhodné pro tvoji situaci, jsem už neposuzoval. Reaguji na smickara: „Zajímalo by mě jestli ten strom spíš problém nevytvoří.“ Pokud má dost paměti, tak ne. Naprogramovat to není nijak zvlášť těžké, když už člověk ví, co chce. |
||
| smickar Profil |
#24 · Zasláno: 27. 9. 2010, 10:49:08
Chamurappi: Dá se pomocí stromu vyřešit i tohle %abc% nebo pouze abc%? (zkuste na Bazoši slova typu lpg, ohař, traktor apod ... .) Zvláště pro shopy mi přijde ta oboustranost nutná.
|
||
|
Časová prodleva: 8 dní
|
|||
| xlifer Profil |
#25 · Zasláno: 5. 10. 2010, 15:08:38
Tak jsem nakonec přešel taky na výběr přímo z db a příjde mi to daleko rychlejší než přes řešení stromu uloženého v array poli a dokonce funguje jak píše dobře i like %abc% což strom asi řešit umí, ale nekodážu si představit array pole ješte na tento způsob...
|
||
| Petr__ Profil * |
#26 · Zasláno: 5. 10. 2010, 16:40:54
xlifer:
Netuším jak velkou máte tu databázi, ze které chcete našeptávat, a co s ní dále provádite, takže uvedu jen takový námět. Já jsem pro to použil Autocomplete s tím, že data pro ten našeptávač linkuji v externím JS souboru jako pole (cca 20000 řádků, téměř 1 MB), který jsem si vygeneroval z databáze. Umí to hledat i v částech slov (obdoba "%abc%" u SQL dotazu) a i na mé staré šunce to běží svižně, bez prodlev. |
||
| Chamurappi Profil |
#27 · Zasláno: 5. 10. 2010, 16:47:44
Reaguji na smickara:
„Dá se pomocí stromu vyřešit i tohle %abc% nebo pouze abc%?“ Dá. Jen je to sestavení trošku komplikovanější. Reaguji na Petra_: Natáhnout všechna data do prohlížeče mi nepřipadá moc elegantní. Vlastně vůbec. |
||
| Petr__ Profil * |
#28 · Zasláno: 5. 10. 2010, 17:00:43
Chamurappi:
Já samozřejmě netuším, jestli xlifer v té databázi má potenciálně citlivá data (případně v jakém rozsahu) a zda je tedy vhodné je vůbec takto dát potenciálně všanc v jednom souboru ke stažení. S tím, že to není elegantní souhlasím, ale pokud chce xlifer "šetřit" s SQL dotazy, tak tímto se tomu zcela vyhne. Ale to už je jen takové teoretizování, nebylo uvedeno jak často je ta databáze aktualizovaná, jakou má strukturu, kolik návštěvníků ten našeptávač bude využívat... |
||
| xlifer Profil |
#29 · Zasláno: 6. 10. 2010, 00:33:13 · Upravil/a: xlifer
Ješte upřesním, že databáze pro našeptávač má vlastní tabulku index, která je využívána pouze pro našeptávač. Navíc v databázi mám uložené upravené texty bez diakritiky tedy pouze ascii. Takže hledané slovo z našeptávače ještě vždy před dotazem like %abc% upravím na malé písmena a bez diakritiky. V databázi je cca. 1.500 položek a jedná se o názvy max. do 128 znaků dlouhé. Nějaký automat vždy jednou za čas, když je potřeba, tak aktualizuje tuto databázi.
Jinak řešeni uvést seznam slov do javascriptu komplet, to není ideál a rozhodně nedoporučuji takto používat ani jsem to nikde tedy neviděl... |
||
| Petr__ Profil * |
#30 · Zasláno: 6. 10. 2010, 14:17:31
xlifer:
„Jinak řešeni uvést seznam slov do javascriptu komplet, to není ideál a rozhodně nedoporučuji takto používat ani jsem to nikde tedy neviděl...“ Já to používám na našeptávání názvů míst (GeoNames), stejně to mají použité i v demu k tomu pluginu jQuery Autocomplete. Že jste to ještě nikde neviděl není důvod to rozhodně nedoporučovat. Záleží na situaci. |
||
|
Téma pokračuje na další straně.
|
|||
0