Introducere

Cercetarea datelor stocate în diferite structuri de date este o parte crucială a aproape fiecărei aplicații.

Există mulți algoritmi diferiți disponibili pentru a fi utilizați la căutare și fiecare dintre ei are implementări diferite și se bazează pe structuri de date diferite pentru a face treaba.

Abilitatea de a alege un algoritm specific pentru o anumită sarcină este o abilitate cheie pentru dezvoltatori și poate face diferența între o aplicație rapidă, fiabilă și stabilă și o aplicație care se prăbușește de la o simplă solicitare.

• Operatori de membru
• Cercetare liniară
• Cercetare binară
• Cercetare prin salt
• Cercetare Fibonacci
• Cercetare exponențială
• Cercetare prin interpolare

.

Operatori de apartenență

Algoritmii se dezvoltă și se optimizează în timp ca urmare a evoluției constante și a necesității de a găsi cele mai eficiente soluții pentru problemele de bază din diferite domenii.

Una dintre cele mai frecvente probleme din domeniul informaticii este căutarea într-o colecție și determinarea dacă un anumit obiect este prezent sau nu în colecție.

Chiar fiecare limbaj de programare are propria implementare a unui algoritm de căutare de bază, de obicei sub forma unei funcții care returnează o valoare Boolean de True sau False atunci când se găsește un obiect într-o anumită colecție de obiecte.

În Python, cel mai simplu mod de a căuta un obiect este de a folosi Operatorii de apartenență – numiți astfel deoarece ne permit să determinăm dacă un anumit obiect este membru într-o colecție.

Aceste operatori pot fi folosiți cu orice structură de date iterabilă în Python, inclusiv Strings, Lists și Tuples.

• in – Returnează True dacă elementul dat face parte din structură.
• not in – Returnează True dacă elementul dat nu face parte din structură.

>>> 'apple' in True>>> 't' in 'stackabuse'True>>> 'q' in 'stackabuse'False>>> 'q' not in 'stackabuse'True

Operatorii de apartenență sunt suficienți atunci când tot ce trebuie să facem este să aflăm dacă există o subșir în cadrul unui șir de caractere dat sau să determinăm dacă două Strings, Lists sau Tuples se intersectează în ceea ce privește obiectele pe care le dețin.

În cele mai multe cazuri avem nevoie de poziția elementului în secvență, pe lângă faptul că trebuie să determinăm dacă acesta există sau nu; operatorii de apartenență nu îndeplinesc această cerință.

Există mulți algoritmi de căutare care nu depind de operatorii încorporați și care pot fi utilizați pentru a căuta valori mai rapid și/sau mai eficient. În plus, aceștia pot produce mai multe informații, cum ar fi poziția elementului în colecție, în loc de a putea determina doar existența acestuia.

Cercetare liniară

Cercetarea liniară este unul dintre cei mai simpli algoritmi de căutare și cel mai ușor de înțeles. Ne putem gândi la el ca la o versiune accelerată a propriei noastre implementări a operatorului in din Python.

Algoritmul constă în iterarea peste un array și returnarea indicelui primei apariții a unui element odată ce acesta este găsit:

def LinearSearch(lys, element): for i in range (len(lys)): if lys == element: return i return -1

Așa că dacă folosim funcția pentru a calcula:

>>> print(LinearSearch(, 2))

În urma executării codului, suntem întâmpinați cu:

1

Acesta este indexul primei apariții a elementului pe care îl căutăm – ținând cont de faptul că indexurile Python sunt bazate pe 0.

Complexitatea în timp a căutării liniare este O(n), ceea ce înseamnă că timpul de execuție crește odată cu numărul de elemente din lista noastră de intrare lys.

Cercetarea liniară nu este adesea utilizată în practică, deoarece aceeași eficiență poate fi obținută prin utilizarea metodelor încorporate sau a operatorilor existenți, și nu este la fel de rapidă sau eficientă ca alți algoritmi de căutare.

Cercetarea liniară se potrivește bine atunci când trebuie să găsim prima apariție a unui element într-o colecție nesortată, deoarece, spre deosebire de majoritatea celorlalți algoritmi de căutare, nu necesită ca o colecție să fie sortată înainte de a începe căutarea.

Cercetare binară

Cercetarea binară urmează o metodologie de împărțire și cucerire. Este mai rapidă decât căutarea liniară, dar necesită ca array-ul să fie sortat înainte ca algoritmul să fie executat.

Să presupunem că căutăm o valoare val într-un array sortat, algoritmul compară val cu valoarea elementului din mijloc al array-ului, pe care îl vom numi mid.

• Dacă mid este elementul pe care îl căutăm (cel mai bun caz), returnăm indicele acestuia.
• Dacă nu, identificăm pe care parte a lui mid val este mai probabil să se afle, pe baza faptului că val este mai mică sau mai mare decât mid, și eliminăm cealaltă parte a tabloului.
• Apoi urmăm recursiv sau iterativ aceiași pași, alegând o nouă valoare pentru mid, comparând-o cu val și eliminând jumătate din posibilele potriviri în fiecare iterație a algoritmului.

Agoritmul de căutare binară poate fi scris fie recursiv, fie iterativ. Recursivitatea este, în general, mai lentă în Python, deoarece necesită alocarea de noi cadre de stivă.

Din moment ce un algoritm de căutare bun ar trebui să fie cât mai rapid și mai precis posibil, să luăm în considerare implementarea iterativă a căutării binare:

Dacă folosim funcția pentru a calcula:

>>> BinarySearch(, 20)

Obținem rezultatul:

1

Care este indicele valorii pe care o căutăm.

Acțiunea pe care algoritmul o execută în continuare în fiecare iterație este una dintre mai multe posibilități:

• Întoarcerea indicelui elementului curent
• Cercetarea prin jumătatea stângă a tabloului
• Cercetarea prin jumătatea dreaptă a tabloului

Noi putem alege doar o singură posibilitate pe iterație, iar grupul nostru de potriviri posibile se împarte la două în fiecare iterație. Acest lucru face ca complexitatea în timp a căutării binare să fie O(log n).

Un dezavantaj al căutării binare este că, în cazul în care există mai multe apariții ale unui element în matrice, aceasta nu returnează indexul primului element, ci mai degrabă indexul elementului cel mai apropiat de mijloc:

>>> print(BinarySearch(, 4))

Executarea acestei bucăți de cod va avea ca rezultat indicele elementului din mijloc:

1

Pentru comparație, efectuarea unei căutări liniare pe același array ar returna:

0

Ceea ce reprezintă indicele primului element. Cu toate acestea, nu putem spune în mod categoric că căutarea binară nu funcționează dacă un array conține același element de două ori – poate funcționa la fel ca și căutarea liniară și returnează prima apariție a elementului în unele cazuri.

Dacă efectuăm căutarea binară pe array-ul , de exemplu, și căutăm 4, am obține 3 ca rezultat.

Cercetarea binară este destul de frecvent utilizată în practică deoarece este eficientă și rapidă în comparație cu căutarea liniară. Cu toate acestea, are unele neajunsuri, cum ar fi dependența sa de operatorul //. Există mulți alți algoritmi de căutare de tip “divide și cucerește” care derivă din căutarea binară, să examinăm în continuare câțiva dintre aceștia.

Jump Search

Jump Search este similar cu căutarea binară prin faptul că lucrează pe o matrice sortată și utilizează o abordare similară de tip “divide și cucerește” pentru a căuta în ea.

Poate fi clasificat ca o îmbunătățire a algoritmului de căutare liniară, deoarece depinde de căutarea liniară pentru a efectua comparația efectivă atunci când caută o valoare.

Dat fiind un tablou sortat, în loc să căutăm prin elementele tabloului în mod incremental, căutăm în salturi. Astfel, în lista noastră de intrare lys, dacă avem o dimensiune a salturilor de salt, algoritmul nostru va lua în considerare elementele în ordinea lys, lys, lys, lys, lys și așa mai departe.

Cu fiecare salt, stocăm valoarea anterioară pe care am căutat-o și indicele acesteia. Când găsim un set de valori în care lys<element<lys, efectuăm o căutare liniară cu lys ca fiind elementul cel mai din stânga și lys ca fiind elementul cel mai din dreapta din setul nostru de căutare:

Din moment ce acesta este un algoritm complex, să luăm în considerare calculul pas cu pas al căutării prin salt cu această intrare:

>>> print(JumpSearch(, 5))

• Cercetarea prin salt ar determina mai întâi mărimea săriturii prin calculul math.sqrt(len(lys)). Având în vedere că avem 9 elemente, dimensiunea saltului ar fi √9 = 3.
• În continuare, calculăm valoarea variabilei right, care este minimul lungimii matricei minus 1, sau valoarea lui left+jump, care în cazul nostru ar fi 0+3=3. Deoarece 3 este mai mic decât 8, folosim 3 ca valoare a right.
• Acum verificăm dacă elementul nostru de căutare, 5, se află între lys și lys. Deoarece 5 nu este între 1 și 4, trecem mai departe.
• În continuare, facem din nou calculele și verificăm dacă elementul nostru de căutare este între lys și lys, unde 6 este 3+salt. Deoarece 5 este între 4 și 7, efectuăm o căutare liniară pe elementele cuprinse între lys și lys și returnăm indicele elementului nostru ca fiind:

4

Complexitatea în timp a căutării prin salt este O(√n), unde √n este dimensiunea săriturii, iar n este lungimea listei, plasând căutarea prin salt între algoritmii de căutare liniară și căutare binară în ceea ce privește eficiența.

Cel mai important avantaj al căutării prin salt în comparație cu căutarea binară este că nu se bazează pe operatorul de împărțire (/).

În cele mai multe unități centrale de procesare, utilizarea operatorului de împărțire este costisitoare în comparație cu alte operații aritmetice de bază (adunare, scădere și înmulțire), deoarece implementarea algoritmului de împărțire este iterativă.

Costul în sine este foarte mic, dar atunci când numărul de elemente de căutat este foarte mare, iar numărul de operații de împărțire pe care trebuie să le efectuăm crește, costul se poate aduna în mod incremental. Prin urmare, căutarea prin salt este mai bună decât căutarea binară atunci când există un număr mare de elemente într-un sistem în care chiar și o creștere mică a vitezei contează.

Pentru a face căutarea prin salt mai rapidă, am putea folosi căutarea binară sau o altă căutare internă prin salt pentru a căuta prin blocuri, în loc să ne bazăm pe căutarea liniară, mult mai lentă.

Cercetarea Fibonacci

Cercetarea Fibonacci este un alt algoritm de împărțire și cucerire care are asemănări atât cu căutarea binară, cât și cu căutarea prin salt. Își primește numele deoarece folosește numerele Fibonacci pentru a calcula dimensiunea blocului sau intervalul de căutare în fiecare pas.

Numerele Fibonacci încep cu zero și urmează modelul 0, 1, 1, 1, 2, 3, 3, 5, 8, 13, 21… unde fiecare element este suma celor două numere care îl precedă imediat.

Algoritmul lucrează cu trei numere Fibonacci la un moment dat. Să numim cele trei numere fibM, fibM_minus_1 și fibM_minus_2, unde fibM_minus_1 și fibM_minus_2 sunt cele două numere imediat înainte de fibM în secvență:

fibM = fibM_minus_1 + fibM_minus_2

Inițializăm valorile la 0,1 și 1 sau la primele trei numere din secvența Fibonacci pentru a evita obținerea unei erori de indexare în cazul în care matricea noastră de căutare lys conține un număr foarte mic de elemente.

Apoi alegem cel mai mic număr din secvența Fibonacci care este mai mare sau egal cu numărul de elemente din tabloul nostru de căutare lys, ca valoare fibM, și cele două numere Fibonacci imediat înainte de acesta ca valori fibM_minus_1 și fibM_minus_2. În timp ce matricea are elemente rămase și valoarea lui fibM este mai mare decât unu, noi:

• Comparăm val cu valoarea blocului din intervalul de până la fibM_minus_2 și returnăm indicele elementului dacă acesta se potrivește.
• Dacă valoarea este mai mare decât elementul la care ne uităm în prezent, mutăm valorile lui fibM, fibM_minus_1 și fibM_minus_2 cu două trepte în jos în secvența Fibonacci și resetăm indicele la indicele elementului.
• Dacă valoarea este mai mică decât elementul la care ne uităm în prezent, mutăm valorile lui fibM, fibM_minus_1 și fibM_minus_2 cu o treaptă în jos în secvența Fibonacci.

Să aruncăm o privire la implementarea Python a acestui algoritm:

Dacă folosim funcția FibonacciSearch pentru a calcula:

>>> print(FibonacciSearch(, 6))

Să aruncăm o privire la procesul pas cu pas al acestei căutări:

• Determinarea celui mai mic număr Fibonacci mai mare sau egal cu lungimea listei ca fibM; în acest caz, cel mai mic număr Fibonacci care îndeplinește cerințele noastre este 13.
• Valorile ar fi atribuite ca:
  • fibM = 13
  • fibM_minus_1 = 8
  • fibM_minus_2 = 5
  • index = -1
• În continuare, verificăm elementul lys unde 4 este minimul lui -1+5 . Deoarece valoarea lui lys este 5, care este mai mică decât valoarea pe care o căutăm, mutăm numerele Fibonacci cu o treaptă mai jos în secvență, realizând valorile:
  • fibM = 8
  • fibM_minus_1 = 5
  • fibM_minus_2 = 3
  • index = 4
• În continuare, verificăm elementul lys unde 7 este minimul lui 4+3. Deoarece valoarea lui lys este 8, care este mai mare decât valoarea pe care o căutăm, mutăm numerele Fibonacci cu două trepte mai jos în secvență.
  • fibM = 3
  • fibM_minus_1 = 2
  • fibM_minus_2 = 1
  • index = 4
• Acum verificăm elementul lys unde 5 este minimul lui 4+1 . Valoarea lui lys este 6, care este valoarea pe care o căutăm!

Rezultatul, așa cum era de așteptat, este:

5

Complexitatea de timp pentru căutarea Fibonacci este O(log n); la fel ca pentru căutarea binară. Acest lucru înseamnă că algoritmul este mai rapid atât decât căutarea liniară, cât și căutarea prin salt în majoritatea cazurilor.

Cercetarea Fibonacci poate fi utilizată atunci când avem un număr foarte mare de elemente de căutat și dorim să reducem ineficiența asociată cu utilizarea unui algoritm care se bazează pe operatorul de împărțire.

Un avantaj suplimentar al utilizării căutării Fibonacci este acela că poate acomoda array-uri de intrare care sunt prea mari pentru a fi păstrate în memoria cache a procesorului sau în memoria RAM, deoarece caută prin elemente în trepte de mărime crescătoare, și nu într-o dimensiune fixă.

Cercetare exponențială

Cercetarea exponențială este un alt algoritm de căutare care poate fi implementat destul de simplu în Python, în comparație cu căutarea prin salt și căutarea Fibonacci, care sunt amândouă un pic mai complexe. Este cunoscut și sub numele de căutare galopantă, căutare dublă și căutare Struzik.

Cercetarea exponențială depinde de căutarea binară pentru a efectua comparația finală a valorilor. Algoritmul funcționează prin:

• Determinarea intervalului în care este probabil să se afle elementul pe care îl căutăm
• Utilizarea căutării binare pentru interval pentru a găsi indicele exact al elementului

Implementarea Python a algoritmului de căutare exponențială este:

Dacă folosim funcția pentru a găsi valoarea lui:

>>> print(ExponentialSearch(,3))

Algoritmul funcționează prin:

• Verificarea dacă primul element din listă se potrivește cu valoarea pe care o căutăm – din moment ce lys este 1 și căutăm 3, setăm indexul la 1 și mergem mai departe.
• Cercetarea tuturor elementelor din listă și, în timp ce elementul de pe poziția indexului este mai mic sau egal cu valoarea noastră, creșterea exponențială a valorii lui index în multipli de doi:
  • index = 1, lys este 2, care este mai mic decât 3, astfel încât indicele este înmulțit cu 2 și setat la 2.
  • index = 2, lyseste 3, care este egal cu 3, astfel încât indicele este înmulțit cu 2 și setat la 4.
  • index = 4, lys este 5, ceea ce este mai mare decât 3; bucla este întreruptă în acest punct.
• Se efectuează apoi o căutare binară prin felierea listei; arr. În Python, acest lucru înseamnă că sublista va conține toate elementele până la al 4-lea element, așa că, de fapt, apelăm:

>>> BinarySearch(, 3)

care ar returna:

2

Care este indicele elementului pe care îl căutăm atât în lista originală, cât și în lista feliată pe care o transmitem algoritmului de căutare binară.

Cercetarea exponențială se execută în timp O(log i), unde i este indicele elementului pe care îl căutăm. În cel mai rău caz, complexitatea în timp este O(log n), atunci când ultimul element este elementul pe care îl căutăm (n fiind lungimea tabloului).

Cercetarea exponențială funcționează mai bine decât căutarea binară atunci când elementul pe care îl căutăm este mai aproape de începutul tabloului. În practică, folosim căutarea exponențială deoarece este unul dintre cei mai eficienți algoritmi de căutare pentru array-uri nemărginite sau infinite.

Cercetare prin interpolare

Cercetarea prin interpolare este un alt algoritm de împărțire și cucerire, similar cu căutarea binară. Spre deosebire de căutarea binară, acesta nu începe întotdeauna căutarea de la mijloc. Căutarea prin interpolare calculează poziția probabilă a elementului pe care îl căutăm folosind formula:

index = low + )*(high-low) / (lys-lys)]

În care variabilele sunt:

• lys – matricea noastră de intrare
• val – elementul pe care îl căutăm
• index – indicele probabil al elementului căutat. Acesta este calculat ca fiind o valoare mai mare atunci când val este mai aproape ca valoare de elementul de la sfârșitul tabloului (lys) și mai mică atunci când val este mai aproape ca valoare de elementul de la începutul tabloului (lys)
• low – indicele de început al tabloului
• high – ultimul indice al tabloului

Algoritmul caută prin calcularea valorii lui index:

• Dacă se găsește o potrivire (când lys == val), se returnează indexul
• Dacă valoarea lui val este mai mică decât lys, valoarea indexului este recalculată folosind formula pentru subregiul din stânga
• Dacă valoarea lui val este mai mare decât lys, valoarea indicelui este recalculată folosind formula pentru sub-reagregatul din dreapta

Să continuăm și să implementăm căutarea prin interpolare folosind Python:

Dacă folosim funcția pentru a calcula:

>>> print(InterpolationSearch(, 6))

Valorile noastre inițiale ar fi:

• val = 6,
• low = 0,
• high = 7,
• lys = 1,
• lys = 8,
• index = 0 + = 5

Din moment ce lys este 6, care este valoarea pe care o căutăm, ne oprim din execuție și returnăm rezultatul:

5

Dacă avem un număr mare de elemente, iar indexul nostru nu poate fi calculat într-o singură iterație, continuăm să recalculăm valorile pentru index după ce ajustăm valorile de high și low din formula noastră.

Complexitatea în timp a căutării prin interpolare este O(log log n) atunci când valorile sunt distribuite uniform. Dacă valorile nu sunt distribuite uniform, complexitatea timpului în cel mai rău caz este O(n), la fel ca în cazul căutării liniare.

Cercetarea prin interpolare funcționează cel mai bine pe array-uri sortate și distribuite uniform. În timp ce căutarea binară începe de la mijloc și întotdeauna se împarte în două, căutarea prin interpolare calculează poziția probabilă a elementului și verifică indicele, ceea ce face mai probabilă găsirea elementului într-un număr mai mic de iterații.

De ce să folosiți Python pentru căutare?

Python este foarte ușor de citit și eficient în comparație cu limbajele de programare mai vechi precum Java, Fortran, C, C++ etc. Un avantaj cheie al utilizării Python pentru implementarea algoritmilor de căutare este că nu trebuie să vă faceți griji cu privire la casting sau la tastarea explicită.

În Python, majoritatea algoritmilor de căutare pe care i-am discutat vor funcționa la fel de bine dacă căutăm un String. Rețineți că trebuie să facem modificări la cod pentru algoritmii care folosesc elementul de căutare pentru calcule numerice, cum ar fi algoritmul de căutare prin interpolare.

Python este, de asemenea, un loc bun pentru a începe dacă doriți să comparați performanța diferiților algoritmi de căutare pentru setul dvs. de date; construirea unui prototip în Python este mai ușoară și mai rapidă, deoarece puteți face mai multe cu mai puține linii de cod.

Pentru a compara performanța algoritmilor noștri de căutare implementați față de un set de date, putem folosi biblioteca de timp din Python:

import timestart = time.time()# call the function hereend = time.time()print(start-end)

Concluzie

Există multe moduri posibile de a căuta un element într-o colecție. În acest articol, am încercat să discutăm câțiva algoritmi de căutare și implementările lor în Python.

Alegerea algoritmului de utilizat se bazează pe datele prin care trebuie să căutați; array-ul de intrare, pe care l-am numit lys în toate implementările noastre.

• Dacă doriți să căutați într-un tablou nesortat sau să găsiți prima apariție a unei variabile de căutare, cea mai bună opțiune este căutarea liniară.
• Dacă doriți să căutați într-un tablou sortat, există multe opțiuni dintre care cea mai simplă și mai rapidă metodă este căutarea binară.
• Dacă aveți un tablou sortat prin care doriți să căutați fără a utiliza operatorul de împărțire, puteți utiliza fie căutarea prin salt, fie căutarea Fibonacci.
• Dacă știți că elementul pe care îl căutați este probabil să fie mai aproape de începutul tabloului, puteți utiliza căutarea exponențială.
• Dacă array-ul dvs. sortat este, de asemenea, uniform distribuit, cel mai rapid și eficient algoritm de căutare de utilizat ar fi căutarea prin interpolare.

Dacă nu sunteți sigur ce algoritm să utilizați cu un array sortat, încercați fiecare dintre ei împreună cu biblioteca de timp Python și alegeți-l pe cel care se comportă cel mai bine cu setul dvs. de date.

.