Inleiding

Het zoeken naar gegevens die zijn opgeslagen in verschillende gegevensstructuren is een cruciaal onderdeel van vrijwel elke toepassing.

Er zijn veel verschillende algoritmen beschikbaar om te gebruiken bij het zoeken, en elk algoritme heeft verschillende implementaties en vertrouwt op verschillende gegevensstructuren om de klus te klaren.

Het kunnen kiezen van een specifiek algoritme voor een bepaalde taak is een belangrijke vaardigheid voor ontwikkelaars en kan het verschil betekenen tussen een snelle, betrouwbare en stabiele toepassing en een toepassing die afbrokkelt bij een eenvoudig verzoek.

• Lidmaat Operators
• Lineair zoeken
• Binair zoeken
• Sprong zoeken
• Fibonacci zoeken
• Exponentieel zoeken
• Interpolatie zoeken

Gebonden Operatoren

Algoritmen ontwikkelen zich en worden in de loop der tijd geoptimaliseerd als gevolg van voortdurende evolutie en de noodzaak om de meest efficiënte oplossingen te vinden voor onderliggende problemen in verschillende domeinen.

Een van de meest voorkomende problemen in het domein van de informatica is het doorzoeken van een verzameling en het bepalen of een bepaald object al dan niet in de verzameling aanwezig is.

Nagenoeg elke programmeertaal heeft zijn eigen implementatie van een elementair zoekalgoritme, gewoonlijk als een functie die een Boolean-waarde van True of False teruggeeft wanneer een voorwerp in een gegeven verzameling voorwerpen wordt gevonden.

In Python is de gemakkelijkste manier om naar een object te zoeken het gebruik van Membership Operators – zo genoemd omdat zij ons in staat stellen te bepalen of een gegeven object een lid is in een verzameling.

Deze operatoren kunnen worden gebruikt met elke iterable datastructuur in Python, met inbegrip van Strings, Lists, en Tuples.

• in – Geeft True terug als het gegeven element een deel is van de structuur.
• not in – Geeft True als het opgegeven element geen deel uitmaakt van de structuur.

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

Membership operators volstaan wanneer we alleen maar hoeven te kijken of een substring bestaat in een gegeven string, of bepalen of twee Strings, Lists, of Tuples elkaar snijden in termen van de objecten die ze bevatten.

In de meeste gevallen hebben we de positie van het item in de reeks nodig, naast de bepaling of het al dan niet bestaat; lidmaatschapsoperatoren voldoen niet aan deze eis.

Er zijn veel zoekalgoritmen die niet afhankelijk zijn van ingebouwde operatoren en die kunnen worden gebruikt om sneller en/of efficiënter naar waarden te zoeken. Bovendien kunnen zij meer informatie opleveren, zoals de positie van het element in de verzameling, in plaats van alleen het bestaan ervan te kunnen vaststellen.

Lineair zoeken

Lineair zoeken is een van de eenvoudigste zoekalgoritmen, en het eenvoudigst te begrijpen. We kunnen het zien als een opgevoerde versie van onze eigen implementatie van Python’s in operator.

Het algoritme bestaat uit het itereren over een matrix en het retourneren van de index van het eerste voorkomen van een item zodra het is gevonden:

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

Dus als we de functie gebruiken om te berekenen:

>>> print(LinearSearch(, 2))

Als we de code uitvoeren, worden we begroet met:

1

Dit is de index van het eerste voorkomen van het item dat we zoeken – in gedachten houdend dat Python indexen op 0 gebaseerd zijn.

De tijdcomplexiteit van lineair zoeken is O(n), wat betekent dat de tijd die nodig is om het uit te voeren toeneemt met het aantal items in onze invoerlijst lys.

Lineair zoeken wordt in de praktijk niet vaak gebruikt, omdat dezelfde efficiëntie kan worden bereikt met ingebouwde methoden of bestaande operatoren, en het is niet zo snel of efficiënt als andere zoekalgoritmen.

Lineair zoeken is goed geschikt voor het vinden van het eerste voorkomen van een item in een ongesorteerde verzameling, omdat het, in tegenstelling tot de meeste andere zoekalgoritmen, niet vereist dat een verzameling is gesorteerd voordat met zoeken wordt begonnen.

Binair zoeken

Binair zoeken volgt een verdeel-en-heers-methode. Het is sneller dan lineair zoeken, maar vereist dat de matrix gesorteerd is voordat het algoritme wordt uitgevoerd.

Aannemend dat we een waarde val in een gesorteerde matrix zoeken, vergelijkt het algoritme val met de waarde van het middelste element van de matrix, dat we mid zullen noemen.

• Als mid het element is dat we zoeken (in het beste geval), geven we de index ervan terug.
• Zo niet, dan bepalen we aan welke kant van mid val waarschijnlijker is op grond van het feit of val kleiner of groter is dan mid, en gooien we de andere kant van de array weg.
• We volgen dan recursief of iteratief dezelfde stappen, waarbij we een nieuwe waarde kiezen voor mid, deze vergelijken met val en de helft van de mogelijke overeenkomsten in elke iteratie van het algoritme weggooien.

Het binaire zoekalgoritme kan zowel recursief als iteratief worden geschreven. Recursief is over het algemeen langzamer in Python, omdat het de toewijzing van nieuwe stack frames vereist.

Omdat een goed zoekalgoritme zo snel en nauwkeurig mogelijk moet zijn, laten we de iteratieve implementatie van binair zoeken eens bekijken:

Als we de functie gebruiken om te berekenen:

>>> BinarySearch(, 20)

We krijgen het resultaat:

1

Wat de index is van de waarde waarnaar we zoeken.

De actie die het algoritme vervolgens in elke iteratie uitvoert, is een van de volgende mogelijkheden:

• Het teruggeven van de index van het huidige element
• Het doorzoeken van de linker helft van de matrix
• Het doorzoeken van de rechter helft van de matrix

We kunnen maar één mogelijkheid per iteratie kiezen, en onze pool van mogelijke overeenkomsten wordt in elke iteratie door twee gedeeld. Dit maakt de tijdcomplexiteit van binair zoeken O(log n).

Een nadeel van binair zoeken is dat als een element in de matrix meerdere malen voorkomt, niet de index van het eerste element wordt gegeven, maar die van het element dat het dichtst bij het midden ligt:

>>> print(BinarySearch(, 4))

Het uitvoeren van dit stukje code zal resulteren in de index van het middelste element:

1

Voor vergelijking het uitvoeren van een lineaire zoekactie op dezelfde array zou opleveren:

0

Dat is de index van het eerste element. We kunnen echter niet categorisch zeggen dat binair zoeken niet werkt als een array tweemaal hetzelfde element bevat – het kan net als lineair zoeken werken en in sommige gevallen het eerste voorkomen van het element opleveren.

Als we bijvoorbeeld binair zoeken op de array en naar 4 zoeken, zouden we 3 als resultaat krijgen.

Binair zoeken wordt in de praktijk vrij vaak gebruikt omdat het efficiënt en snel is in vergelijking met lineair zoeken. Het heeft echter enkele tekortkomingen, zoals de afhankelijkheid van de operator //. Er zijn veel andere verdeel-en-heers-zoekalgoritmen die van binair zoeken zijn afgeleid. Laten we er nu een paar bekijken.

Jump Search

Jump Search lijkt op binair zoeken omdat het op een gesorteerde matrix werkt, en een vergelijkbare verdeel-en-heers-aanpak gebruikt om die matrix te doorzoeken.

Het kan worden geclassificeerd als een verbetering van het lineaire zoekalgoritme, omdat het afhankelijk is van lineair zoeken om de feitelijke vergelijking uit te voeren bij het zoeken naar een waarde.

Gegeven aan een gesorteerde matrix, in plaats van incrementeel door de matrixelementen te zoeken, zoeken we in sprongen. Dus in onze invoerlijst lys, als we een spronggrootte van sprong hebben, zal ons algoritme elementen overwegen in de volgorde lys, lys, lys, lys enzovoort.

Met elke sprong slaan we de vorige waarde op die we hebben bekeken en de index ervan. Wanneer we een reeks waarden vinden waarbij lys<element<lys, voeren we een lineaire zoekactie uit met lys als het meest linkse element en lys als het meest rechtse element in onze zoekverzameling:

Omdat dit een complex algoritme is, laten we de stapsgewijze berekening van het zoeken met sprongen met deze invoer eens bekijken:

>>> print(JumpSearch(, 5))

• Het zoeken met sprongen zou eerst de grootte van de sprong bepalen door math.sqrt(len(lys)) te berekenen. Aangezien we 9 elementen hebben, zou de spronggrootte √9 = 3 zijn.
• Volgende berekenen we de waarde van de variabele right, die het minimum is van de lengte van de matrix min 1, of de waarde van left+jump, die in ons geval 0+3= 3 zou zijn. Aangezien 3 kleiner is dan 8 gebruiken we 3 als de waarde van right.
• Nu controleren we of ons zoekelement, 5, tussen lys en lys ligt. Aangezien 5 niet tussen 1 en 4 ligt, gaan we verder.
• Volgende, we doen de berekeningen opnieuw en controleren of ons zoekelement tussen lys en lys ligt, waarbij 6 3+sprong is. Aangezien 5 tussen 4 en 7 ligt, doen we een lineaire zoekactie op de elementen tussen lys en lys en geven de index van ons element terug als:

4

De tijdcomplexiteit van de sprong-zoekactie is O(√n), waarbij √n de spronggrootte is, en n de lengte van de lijst, waardoor de sprong-zoekactie qua efficiëntie tussen de lineaire zoek- en de binaire zoekalgoritmen in komt te staan.

Het belangrijkste voordeel van sprongsgewijs zoeken in vergelijking met binair zoeken is dat het niet afhankelijk is van de delingsoperator (/).

In de meeste CPU’s is het gebruik van de delingsoperator duur in vergelijking met andere rekenkundige bewerkingen (optellen, aftrekken en vermenigvuldigen), omdat de uitvoering van het delingsalgoritme iteratief is.

De kosten op zichzelf zijn zeer gering, maar wanneer het aantal elementen dat moet worden doorzocht zeer groot is, en het aantal delingsoperaties dat moet worden uitgevoerd toeneemt, kunnen de kosten in stijgende lijn oplopen. Daarom is sprongzoeken beter dan binair zoeken als er een groot aantal elementen in een systeem is waar zelfs een kleine toename in snelheid van belang is.

Om sprongzoeken sneller te maken, zouden we binair zoeken of een ander intern sprongzoeken kunnen gebruiken om de blokken te doorzoeken, in plaats van te vertrouwen op het veel langzamere lineaire zoeken.

Fibonacci zoeken

Fibonacci zoeken is een ander verdeel-en-heersalgoritme dat overeenkomsten vertoont met zowel binair zoeken als sprongzoeken. Het dankt zijn naam aan het gebruik van Fibonacci getallen om de blokgrootte of het zoekbereik in elke stap te berekenen.

Fibonacci getallen beginnen met nul en volgen het patroon 0, 1, 1, 2, 3, 5, 8, 13, 21… waarbij elk element de optelling is van de twee getallen die er onmiddellijk aan voorafgaan.

Het algoritme werkt met drie Fibonacci getallen per keer. Laten we de drie getallen fibM, fibM_minus_1, en fibM_minus_2 noemen, waarbij fibM_minus_1 en fibM_minus_2 de twee getallen zijn die onmiddellijk voor fibM in de reeks staan:

fibM = fibM_minus_1 + fibM_minus_2

We initialiseren de waarden op 0,1, en 1, of de eerste drie getallen in de Fibonacci reeks om een indexfout te voorkomen in het geval dat onze zoek-array lys een zeer klein aantal items bevat.

Dan kiezen we het kleinste getal van de Fibonacci reeks dat groter of gelijk is aan het aantal elementen in onze zoek-array lys, als de waarde fibM, en de twee Fibonacci getallen direct daarvoor als de waarden fibM_minus_1 en fibM_minus_2. Zolang de array nog elementen bevat en de waarde van fibM groter is dan één, vergelijken we:

• val met de waarde van het blok in het bereik tot fibM_minus_2, en geven de index van het element terug als het overeenkomt.
• Als de waarde groter is dan het element waar we nu naar kijken, verplaatsen we de waarden van fibM, fibM_minus_1 en fibM_minus_2 twee stappen omlaag in de Fibonacci reeks, en zetten de index terug op de index van het element.
• Als de waarde kleiner is dan het element waar we nu naar kijken, verplaatsen we de waarden van fibM, fibM_minus_1 en fibM_minus_2 één stap omlaag in de Fibonacci reeks.

Laten we eens kijken naar de Python-implementatie van dit algoritme:

Als we de FibonacciSearch-functie gebruiken om te berekenen:

>>> print(FibonacciSearch(, 6))

Laten we eens kijken naar het stapsgewijze proces van deze zoekactie:

• Het bepalen van het kleinste Fibonacci getal groter of gelijk aan de lengte van de lijst als fibM; in dit geval is het kleinste Fibonacci getal dat aan onze eisen voldoet, 13.
• De waarden zouden worden toegekend als:
  • fibM = 13
  • fibM_minus_1 = 8
  • fibM_minus_2 = 5
  • index = -1
• Daarna controleren we het element lys waarbij 4 het minimum is van -1+5 . Omdat de waarde van lys 5 is, wat kleiner is dan de waarde die we zoeken, schuiven we de Fibonacci getallen een stap naar beneden in de reeks, waardoor de waarden:
  • fibM = 8
  • fibM_minus_1 = 5
  • fibM_minus_2 = 3
  • index = 4
• Volgende controleren we het element lys waarbij 7 het minimum is van 4+3. Omdat de waarde van lys 8 is, wat groter is dan de waarde die we zoeken, verplaatsen we de Fibonacci getallen twee stappen naar beneden in de reeks.
  • fibM = 3
  • fibM_minus_1 = 2
  • fibM_minus_2 = 1
  • index = 4
• Nu controleren we het element lys waarbij 5 het minimum is van 4+1 . De waarde van lys is 6, en dat is de waarde die we zoeken!

Het resultaat is, zoals verwacht:

5

De tijdcomplexiteit voor Fibonacci zoeken is O(log n); hetzelfde als binair zoeken. Dit betekent dat het algoritme in de meeste gevallen sneller is dan lineair zoeken en zoeken met sprongen.

Fibonacci zoeken kan worden gebruikt wanneer we een zeer groot aantal elementen moeten doorzoeken, en we de inefficiëntie willen verminderen die gepaard gaat met het gebruik van een algoritme dat op de delingsoperator berust.

Een bijkomend voordeel van het gebruik van Fibonacci search is dat het geschikt is voor input arrays die te groot zijn om in CPU cache of RAM te worden bewaard, omdat het door elementen zoekt in toenemende stapgroottes, en niet in een vaste grootte.

Exponentieel zoeken

Exponentieel zoeken is een ander zoekalgoritme dat vrij eenvoudig in Python kan worden geïmplementeerd, vergeleken met jump search en Fibonacci search, die beide een beetje complex zijn. Het is ook bekend onder de namen galopperen zoeken, verdubbelen zoeken en Struzik zoeken.

Exponentieel zoeken is afhankelijk van binair zoeken om de uiteindelijke vergelijking van waarden uit te voeren. Het algoritme werkt door:

• Het bereik te bepalen waar het element dat we zoeken zich waarschijnlijk bevindt
• Het bereik binair te doorzoeken om de exacte index van het item te vinden

De Python-implementatie van het exponentiële zoekalgoritme is:

Als we de functie gebruiken om de waarde te vinden van:

>>> print(ExponentialSearch(,3))

Het algoritme werkt door:

• Kijken of het eerste element in de lijst overeenkomt met de waarde die we zoeken – aangezien lys 1 is en we zoeken naar 3, stellen we de index in op 1 en gaan we verder.
• Doorlopen van alle elementen in de lijst, en zolang het item op de index’th positie kleiner of gelijk is aan onze waarde, verhogen we de waarde van index exponentieel in veelvouden van twee:
  • index = 1, lys is 2, wat kleiner is dan 3, dus de index wordt met 2 vermenigvuldigd en op 2 gezet.
  • index = 2, lys is 3, wat gelijk is aan 3, dus de index wordt met 2 vermenigvuldigd en op 4 gezet.
  • index = 4, lys is 5, wat groter is dan 3; de lus wordt op dit punt afgebroken.
• Het voert dan een binaire zoekactie uit door de lijst te slicen; arr. In Python betekent dit dat de deellijst alle elementen tot en met het 4e element zal bevatten, dus roepen we eigenlijk:

>>> BinarySearch(, 3)

op, wat als resultaat zou geven:

2

Wat de index is van het element waarnaar we zoeken in zowel de oorspronkelijke lijst, als de gesneden lijst die we doorgeven aan het binaire zoekalgoritme.

Exponentieel zoeken verloopt in O(log i) tijd, waarbij i de index is van het element dat we zoeken. In het slechtste geval is de tijdcomplexiteit O(log n), wanneer het laatste element het element is dat we zoeken (n is de lengte van de matrix).

Exponentieel zoeken werkt beter dan binair zoeken wanneer het element dat we zoeken dichter bij het begin van de matrix ligt. In de praktijk gebruiken we exponentieel zoeken omdat het een van de meest efficiënte zoekalgoritmen is voor onbegrensde of oneindige matrices.

Interpolatie zoeken

Interpolatie zoeken is een ander verdeel-en-heers algoritme, vergelijkbaar met binair zoeken. In tegenstelling tot binair zoeken, begint het zoeken niet altijd in het midden. Interpolatie zoeken berekent de waarschijnlijke positie van het element dat we zoeken met de formule:

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

Waarbij de variabelen zijn:

• lys – onze invoer-array
• val – het element dat we zoeken
• index – de waarschijnlijke index van het zoek-element. Dit wordt berekend als een hogere waarde wanneer val dichter bij het element aan het eind van de array ligt (lys), en een lagere waarde wanneer val dichter bij het element aan het begin van de array ligt (lys)
• low – de beginindex van de array
• high – de laatste index van de array

Het algoritme zoekt door het berekenen van de waarde van index:

• Als een overeenkomst wordt gevonden (als lys == val), wordt de index teruggegeven
• Als de waarde van val lager is dan lys, wordt de waarde voor de index opnieuw berekend met behulp van de formule voor de linker subarray
• Als de waarde van val hoger is dan lys, wordt de waarde voor de index herberekend met de formule voor de rechter sub-array

Laten we verder gaan en de Interpolatie zoekopdracht implementeren met Python:

Als we de functie gebruiken om te berekenen:

>>> print(InterpolationSearch(, 6))

Onze beginwaarden zouden zijn:

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

Omdat lys 6 is, en dat is de waarde die we zoeken, stoppen we met de uitvoering en geven we het resultaat terug:

5

Als we een groot aantal elementen hebben, en onze index niet in één iteratie kan worden berekend, blijven we de waarden voor index herberekenen na aanpassing van de waarden van hoog en laag in onze formule.

De tijdcomplexiteit van interpolatie-zoeken is O(log log n) als de waarden uniform verdeeld zijn. Als de waarden niet uniform verdeeld zijn, is de tijdcomplexiteit in het slechtste geval O(n), hetzelfde als bij lineair zoeken.

Interpolatie zoeken werkt het beste op uniform verdeelde, gesorteerde arrays. Terwijl binair zoeken in het midden begint en altijd in tweeën deelt, berekent interpolatie zoeken de waarschijnlijke positie van het element en controleert de index, waardoor het waarschijnlijker is dat het element in een kleiner aantal iteraties wordt gevonden.

Waarom Python gebruiken om te zoeken?

Python is zeer leesbaar en efficiënt in vergelijking met oudere programmeertalen zoals Java, Fortran, C, C++ enz. Een belangrijk voordeel van het gebruik van Python voor het implementeren van zoekalgoritmen is dat je je geen zorgen hoeft te maken over casting of expliciet typen.

In Python zullen de meeste zoekalgoritmen die we hebben besproken net zo goed werken als we zoeken naar een String. Houd er rekening mee dat we wel wijzigingen moeten aanbrengen in de code voor algoritmen die het zoekelement gebruiken voor numerieke berekeningen, zoals het interpolatie-zoekalgoritme.

Python is ook een goede plek om te beginnen als je de prestaties van verschillende zoekalgoritmen voor je dataset wilt vergelijken; het bouwen van een prototype in Python is eenvoudiger en sneller omdat je meer kunt doen met minder regels code.

Om de prestaties van onze geïmplementeerde zoekalgoritmen te vergelijken met een dataset, kunnen we de tijdbibliotheek in Python gebruiken:

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

Conclusie

Er zijn veel mogelijke manieren om naar een element binnen een verzameling te zoeken. In dit artikel hebben we geprobeerd een paar zoekalgoritmen en hun implementaties in Python te bespreken.

Het kiezen van welk algoritme je moet gebruiken is gebaseerd op de gegevens die je moet doorzoeken; je input array, die we in al onze implementaties lys hebben genoemd.

• Als u door een ongesorteerde array wilt zoeken of het eerste voorkomen van een zoekvariabele wilt vinden, is lineair zoeken de beste optie.
• Als u door een gesorteerde array wilt zoeken, zijn er vele opties waarvan de eenvoudigste en snelste methode binair zoeken is.
• Als u een gesorteerde matrix hebt die u wilt doorzoeken zonder de delingsoperator te gebruiken, kunt u gebruik maken van sprongzoeken of Fibonacci zoeken.
• Als u weet dat het element dat u zoekt waarschijnlijk dichter bij het begin van de matrix ligt, kunt u exponentieel zoeken gebruiken.
• Als uw gesorteerde array ook uniform verdeeld is, is interpolatie zoeken het snelste en efficiëntste zoekalgoritme.

Als u niet zeker weet welk algoritme u met een gesorteerde array moet gebruiken, probeert u ze gewoon allemaal uit met de Python-tijdbibliotheek en kiest u het algoritme dat het best presteert met uw dataset.