Datu struktūras – Algoritmu meklēšana / Searching Algorithms

Iepriekšējā videoklipā jūs izpētījāt kārtošanu (sorting) un iepazināties ar vairākām ieguves metodēm, kuras var izmantot datu kopai. Tomēr ko darīt, ja šajos datos ir jāmeklē konkrēts elements? Šajā videoklipā jūs iepazīsieties ar dažām dažādām meklēšanas pieejām, piemēram, lineāro un bināro. Jūs arī atklāsit darbības, kas saistītas ar abu šo pieeju ieviešanu, un izpētīsiet to piedāvātās priekšrocības.

Datorzinātnē meklēšana ir būtiska darbība. Ja tiek nodrošināta datu kolekcija, var būt nepieciešams identificēt konkrētus elementus šajos datos. Tomēr precīzs elementa apraksts atstāj vietu zināmai interpretācijai. Jau no paša sākuma jūs varētu apsvērt šo jautājumu.

Vai, ņemot vērā hash tabulu, ir atslēgas-vērtības pāris, kas atbilst šai atslēgai?

Šis ir vienkāršs līdzīgs salīdzinājums, kas radīs vai nu unikālas atslēgas neesamību, vai unikālas atslēgas atgriešanu. Daži apsvērumi, veicot meklēšanu, var ietvert lielākā vai mazākā skaitļa atrašanu šajā masīvā vai vidējā skaitļa atgriešanu no šīs skaitļu kolekcijas. Tomēr, ja vērtība neeksistē? Kas būtu jāatdod? Nulles vērtības atgriešana var traucēt lietojumprogrammas spēju darboties pēc tam. Veicot meklēšanu, jums jāapsver, kādi aizsardzības pasākumi ir jāievieš, ja netiek atgriezta vērtība. Jums arī jāapsver, vai meklēšanā ir jāatgriež vērtības pirmais gadījums vai pēdējais.

Vienkāršākā meklēšana, ko varat ieviest, ir lineārā meklēšana.

Ja jums ir elementu masīvs, lineārā meklēšana sākas indeksa sākumā un veic meklēšanu masīvā, līdz tiek atrasts atbilstošs elements vai vairs nav pārbaudāmo elementu. Šajā pieejā labākā gadījuma scenārijs būtu O(1) no viena un sliktākais O(n), jo katrs elements būtu jāpārbauda, lai varētu teikt, ka mērķa elementa nav.

Saistībā ar datu struktūrām ir pierādīts, ka dažām ir raksturīgas šķirošanas tendences, piemēram, heap vai binārs koks. Varat arī izmantot jebkuru datu struktūru un lietot tai kārtošanas algoritmu pirms meklēšanas pieejas izmantošanas. Izmantojot bināro meklēšanu, katrā iterācijā būs meklēšanas vieta.

Ekrānā ir datu saraksts. Binārā meklēšana vispirms pārbaudīs pusceļa punktu un nosaka, vai elements ir lielāks vai mazāks par mērķa elementu. Ja vidējais elements ir mazāks, tad saraksta kreisā puse tiek izmesta un labā puse kļūst par fokusu. Tagad tikai saraksta labajā pusē tiek pieprasīta vidējā vērtība. Atkal, ja tas ir mazāks par mērķa elementu, tas atkal tiek atmests un tiks pārbaudīta šī filtrētā saraksta labā puse. Tādā veidā algoritms katrā iterācijā samazina meklēšanas vietu uz pusi.

Šī pieeja ir ātrāka nekā lineārā meklēšana, taču pirms meklēšanas sākšanas dati ir jāsakārto. Var šķist, ka šāda prasība nav saprātīga, taču, ja jūsu dati tiek lasīti biežāk nekā tiek atjaunināti, tad šāds risinājums varētu būt atbilstošs risinājums. Atkal, tāpat kā iepriekš aprakstītajā lineārajā meklēšanā, vislabākais iespējamais šīs pieejas rezultāts ir tāds, ka elements tiek atrasts pirmajā piegājienā O(1). Tomēr sliktākais scenārijs nav tik optimistisks. Pēc pirmās meklēšanas saraksts tiek samazināts uz pusi n/2. Ja šī iterācija nav veiksmīga, to atkal samazina uz pusi n/4. Pēc tam pēc trešās dalīšanas atkal tiek uz pusēm n/8 utt. Tāpēc var teikt, ka pēc j iterācijām tas ir n/2^K jeb, citiem vārdiem sakot, O(log(n)). Tas ir daudz efektīvāk nekā lineāra pieeja. Tomēr ir vērts paturēt prātā, ka jebkurš laika pieaugums ir jākompensē ar laiku, kas nepieciešams saraksta kārtošanai. Ja saraksts tiek regulāri atjaunināts, tas var kļūt par dārgu procesu.

Šajā rakstā jūs izpētījāt binārās un lineārās meklēšanas funkcijas, darbības, kas veiktas, lai pabeigtu šo meklēšanu, un to darbību. Jūs arī uzzinājāt, kā Big-O pielietojumu var izmantot, lai novērtētu abu efektivitāti. Jūs pat esat uzzinājis, kā, veicot dažus gudrus pielāgojumus standarta pieejai, ir iespējams nopietni uzlabot veiktspēju. Jaun nākošajos rakstos centīšos izpētīt kā strādāt ar algoritmiem.