fejléc
Gyakori kérdések Belépés Új kérdés Véletlen kérdés
Keresés
Kezdőoldal » Számítástechnika » Programozás » Mi a leggyorsabb módja substri...

Mi a leggyorsabb módja substring -ek keresésének?

Figyelt kérdés

Van egy millió nagyságú adatom, mindegyik String.

A feladat az lenne hogy live search-t alkalmazzak ezekre.


Az egyszerűség kedvéért:

Például van rengeteg filmcímem (String, adat), és lenne egy kereső (input), ahova beírva szöveget, megjelennének azok a filmcímek valahol amik valamely substringje egyezik a keresőbe beírt szöveggel.


A kérdés az lenne, hogy milyen módon tudnám a leggyorsabb keresést elérni?

Tehát egyrészt hol tároljam ezeket a Stringeket (adatbázis (ha ez milyen fajta?), JSON, stb...), és milyen módszer(ek)kel keressek.


Prog nyelv: PHP, JS



A kérdésemre köszönöm a válaszokat előre is!



#javascript #adatbázis #php #adat #keresés #web #hatékonyság #string #live search
2020. ápr. 12. 14:30
 1/8 anonim ***** válasza:
75%

A kérdés, hogy pontosan hogyan kellene működnie a keresésnek. stringek elejétől keresel, a stringekben bárhol keresel, egybefüggő substringet ekresel, vagy esetleg szavanként keresel.


Egyébként bármelyik SQL adatbázis értelmes időn belül képes elvégezni egy ilyen keresést, de lévén, hogy mind elölről, mind hátulról wildcardos a keresésed, nem nagyon tud indexelést használni, szóval annyira gyors nem lesz.

2020. ápr. 12. 14:48
Hasznos számodra ez a válasz?
 2/8 A kérdező kommentje:

stringekben bárhol tudnék keresni, és igen emiatt nem lenne értelmes az index, esetleg csinálhatnám úgy hogy feltételezzük hogy string elején keresek és akkor index-el gyors, másodsorban pedig stringekben és akkor lassú.


De nincs erre valami jobb módszer?

Hogyan csinálja például egy IMDB, hogy pár másodperc alatt már van több találat?


Nincs valami adatstruktúra ami gyorsabbá teszi? Vagy adatbázis keresésnél (+indexek-nél) nem tudok jobbat akkor?

2020. ápr. 12. 15:33
 3/8 anonim ***** válasza:
83%
Az IMDB nem mezei string keresést használ. Valószínűnek tartom, hogy elsősorban kulcsszó alapú keresőt használ, tehát a beírt inputot kulcsszavakra bontja, és azok mentén keresi a legrelevánsabb találatokat, szótávolság, film értékelés/népszerűség, meg mittudomén mi alapján rendezve (erre vannak kész keresőmotorok, mint pl az Elasticsearch vagy az Algolia). A kulcsszó mentén való keresés gyorsíthat a lekérdezésen, cserébe méretes overhead-et képez a karbantartása. Dehát erről is szól az adatbázistervezés, megtalálni a sweet spotot a lekérdezés, karbantartás gyorsasága és a tárigény között.
2020. ápr. 12. 16:17
Hasznos számodra ez a válasz?
 4/8 A kérdező kommentje:

Értem.

Ha mondjuk úgy működne a kereső hogy az adatbázisban lenne külön szótábla (ezzel jócskán megnövelve az adatbázis méretét, de itt lehet indexet használni) , és a kereső a szóközzel elválasztott szavak alapján keresne először a szótáblából, majd pedig vennénk azokat a címeket ahol a szavak jelen lennének (a szótábla és a filmcímek között lenne kapcsolat), akkor meg lehetne gyorsítani a keresést a tárigény kárára?


Vagy felesleges ilyennel foglalkozni?

2020. ápr. 12. 17:22
 5/8 anonim ***** válasza:
63%
#4 Igen valószínű, hogy így gyorsabb lenne. Az első esetben egy full table scan kell a keresés elvégzéséhez, utóbbi esetben pedig index alapú keresés plusz egy join. Optimálisan a join csak azután hajtódik végre, hogy a kulcsszavas szűrést elvégezte, tehát a join költsége minimális lesz.
2020. ápr. 12. 17:29
Hasznos számodra ez a válasz?
 6/8 anonim ***** válasza:
63%
Ha már "leggyorsabb" akkor NoSQL, azaz nem SQL alapú adatbázisban. Bár ez a fogalom több különböző adatbázis kategóriát jelent.
2020. ápr. 12. 20:11
Hasznos számodra ez a válasz?
 7/8 anonim ***** válasza:
100%
Reguláris kifejezések. Erre találták ki.
2020. ápr. 12. 20:21
Hasznos számodra ez a válasz?
 8/8 anonim ***** válasza:
100%
#7 Igen, a reguláris kifejezésekkel gyorsan tudsz 1 stringet ellenőrizni. A marginális kérdés hogy milliós nagyságrendű adatban hogyan keresel hatékonyan. (Minden rekordra futtatni egy regexet nem feltétlenül a leggyorsabb megoldás)
2020. ápr. 12. 22:35
Hasznos számodra ez a válasz?

Kapcsolódó kérdések:

Számítástechnika főkategória kérdései »
Számítástechnika - Programozás kategória kérdései »



Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!