Indledning

Søgning efter data gemt i forskellige datastrukturer er en vigtig del af stort set alle programmer.

Der findes mange forskellige algoritmer til brug ved søgning, og hver af dem har forskellige implementeringer og er afhængige af forskellige datastrukturer for at få arbejdet udført.

At kunne vælge en specifik algoritme til en given opgave er en nøglekompetence for udviklere og kan betyde forskellen mellem en hurtig, pålidelig og stabil applikation og en applikation, der smuldrer på grund af en simpel forespørgsel.

• Medlemskabsoperatører
• Linjær søgning
• Binær søgning
• Spring søgning
• Fibonacci søgning
• Eksponentiel søgning
• Interpolationssøgning

Membership Operators

Algoritmer udvikles og optimeres med tiden som følge af konstant udvikling og behovet for at finde de mest effektive løsninger på underliggende problemer inden for forskellige områder.

Et af de mest almindelige problemer inden for datalogi er at søge i en samling og afgøre, om et givet objekt er til stede i samlingen eller ej.

Næsten alle programmeringssprog har deres egen implementering af en grundlæggende søgealgoritme, som regel som en funktion, der returnerer en Boolean værdi på True eller False, når et objekt er fundet i en given samling af objekter.

I Python er den nemmeste måde at søge efter et objekt på at bruge medlemskabsoperatorer – de hedder sådan, fordi de giver os mulighed for at bestemme, om et givet objekt er et medlem i en samling.

Disse operatorer kan bruges med enhver iterabel datastruktur i Python, herunder strenge, lister og tupler.

• in – returnerer True, hvis det givne element er en del af strukturen.
• not in – Returnerer True, hvis det givne element ikke er en del af strukturen.

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

Membership-operatorer er tilstrækkelige, når vi blot skal finde ud af, om der findes en understreng inden for en given streng, eller bestemme, om to Strings, Lists eller Tuples skærer hinanden med hensyn til de objekter, de indeholder.

I de fleste tilfælde har vi brug for elementets position i sekvensen, ud over at bestemme, om det findes eller ej. Medlemskabsoperatorer opfylder ikke dette krav.

Der findes mange søgealgoritmer, der ikke er afhængige af indbyggede operatører, og som kan bruges til at søge efter værdier hurtigere og/eller mere effektivt. Desuden kan de give flere oplysninger, f.eks. elementets position i samlingen, i stedet for blot at kunne fastslå dets eksistens.

Linær søgning

Linær søgning er en af de enkleste søgealgoritmer og den letteste at forstå. Vi kan betragte den som en forstærket version af vores egen implementering af Pythons in-operator in.

Algoritmen består i at iterere over et array og returnere indekset for den første forekomst af et element, når det er fundet:

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

Så hvis vi bruger funktionen til at beregne:

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

Så hvis vi bruger funktionen til at beregne:

>>> print(LinearSearch(, 2))

Når vi udfører koden, bliver vi mødt med:

1

Det er indekset for den første forekomst af det element, vi søger efter – idet vi skal huske, at Python-indekser er 0-baserede.

Den lineære søges tidskompleksitet er O(n), hvilket betyder, at den tid, det tager at udføre, stiger med antallet af elementer i vores inputliste lys.

Linær søgning anvendes ikke ofte i praksis, fordi den samme effektivitet kan opnås ved at anvende indbyggede metoder eller eksisterende operatører, og den er ikke så hurtig eller effektiv som andre søgealgoritmer.

Linær søgning passer godt til, når vi skal finde den første forekomst af et element i en usorteret samling, fordi den i modsætning til de fleste andre søgealgoritmer ikke kræver, at en samling er sorteret, før søgningen begynder.

Binær søgning

Binær søgning følger en del og hersk-metode. Den er hurtigere end lineær søgning, men kræver, at arrayet er sorteret, før algoritmen udføres.

Hvis vi antager, at vi søger efter en værdi val i et sorteret array, sammenligner algoritmen val med værdien af det midterste element i arrayet, som vi kalder mid.

• Hvis mid er det element, vi leder efter (i bedste fald), returnerer vi dets indeks.
• Hvis ikke, identificerer vi, hvilken side af mid val med størst sandsynlighed befinder sig på, baseret på, om val er mindre eller større end mid, og kasserer den anden side af arrayet.
• Vi følger derefter rekursivt eller iterativt de samme trin, idet vi vælger en ny værdi for mid, sammenligner den med val og kasserer halvdelen af de mulige matches i hver iteration af algoritmen.

Den binære søgealgoritme kan skrives enten rekursivt eller iterativt. Rekursion er generelt langsommere i Python, fordi det kræver allokering af nye stack frames.

Da en god søgealgoritme skal være så hurtig og præcis som muligt, skal vi se på den iterative implementering af binær søgning:

Hvis vi bruger funktionen til at beregne:

>>> BinarySearch(, 20)

Vi får resultatet:

1

Hvilket er indekset for den værdi, vi søger efter.

Den handling, som algoritmen udfører som det næste i hver iteration, er en af flere muligheder:

• Sender indekset for det aktuelle element tilbage
• Søger gennem den venstre halvdel af arrayet
• Søger gennem den højre halvdel af arrayet

Vi kan kun vælge én mulighed pr. iteration, og vores pulje af mulige matches bliver delt med to i hver iteration. Dette gør tidskompleksiteten for binær søgning til O(log n).

En ulempe ved binær søgning er, at hvis der er flere forekomster af et element i arrayet, returnerer den ikke indekset for det første element, men derimod indekset for det element, der ligger tættest på midten:

>>> print(BinarySearch(, 4))

Det at køre dette stykke kode vil resultere i indekset for det midterste element:

1

Til sammenligning vil en lineær søgning på det samme array returnere:

0

Hvilket er indekset for det første element. Vi kan dog ikke kategorisk sige, at binær søgning ikke virker, hvis et array indeholder det samme element to gange – den kan fungere ligesom lineær søgning og returnere den første forekomst af elementet i nogle tilfælde.

Hvis vi f.eks. udfører binær søgning på arrayet og søger efter 4, ville vi få 3 som resultat.

Binær søgning er ret almindeligt anvendt i praksis, fordi den er effektiv og hurtig i forhold til lineær søgning. Den har dog nogle mangler, f.eks. at den er afhængig af //-operatoren. Der findes mange andre divide and conquer-søgealgoritmer, der er afledt af binær søgning, lad os undersøge nogle af dem næste gang.

Jump Search

Jump Search ligner binær søgning, idet den arbejder på et sorteret array og bruger en lignende divide and conquer-tilgang til at søge i det.

Den kan klassificeres som en forbedring af den lineære søgealgoritme, da den er afhængig af lineær søgning til at foretage den egentlige sammenligning, når der søges efter en værdi.

Givet et sorteret array søger vi i stedet for at søge gennem arrayelementerne trinvis i spring. Så i vores inputliste lys, hvis vi har en springstørrelse på jump, vil vores algoritme overveje elementer i rækkefølgen lys, lys, lys, lys, lys og så videre.

Med hvert spring gemmer vi den foregående værdi, vi har kigget på, og dens indeks. Når vi finder et sæt værdier, hvor lys<element<lys, udfører vi en lineær søgning med lys som det yderste venstre element og lys som det yderste højre element i vores søgemængde:

Da dette er en kompleks algoritme, skal vi se på den trinvise beregning af spring søgning med dette input:

>>> print(JumpSearch(, 5))

• Spring søgning ville først bestemme springstørrelsen ved at beregne math.sqrt(len(lys)). Da vi har 9 elementer, vil springstørrelsen være √9 = 3.
• Næst beregner vi værdien af variablen right, som er minimum af arrayets længde minus 1, eller værdien af left+jump, som i vores tilfælde ville være 0+3= 3. Da 3 er mindre end 8, bruger vi 3 som værdien af right.
• Nu kontrollerer vi, om vores søgeelement, 5, ligger mellem lys og lys. Da 5 ikke ligger mellem 1 og 4, går vi videre.
• Næste gang foretager vi beregningerne igen og kontrollerer, om vores søgeelement ligger mellem lys og lys, hvor 6 er 3+spring. Da 5 ligger mellem 4 og 7, foretager vi en lineær søgning på elementerne mellem lys og lys og returnerer indekset for vores element som:

4

Tidskompleksiteten af jump search er O(√n), hvor √n er springets størrelse, og n er listens længde, hvilket placerer jump search mellem de lineære søgealgoritmer og binære søgealgoritmer med hensyn til effektivitet.

Den vigtigste enkeltstående fordel ved jump search i forhold til binær søgning er, at den ikke er afhængig af divisionsoperatoren (/).

I de fleste CPU’er er det dyrt at bruge divisionsoperatoren sammenlignet med andre grundlæggende aritmetiske operationer (addition, subtraktion og multiplikation), fordi implementeringen af divisionsalgoritmen er iterativ.

Udgifterne er i sig selv meget små, men når antallet af elementer, der skal søges igennem, er meget stort, og antallet af divisionsoperationer, som vi skal udføre, stiger, kan omkostningerne stige gradvist. Derfor er jump search bedre end binær søgning, når der er et stort antal elementer i et system, hvor selv en lille stigning i hastigheden betyder noget.

For at gøre jump search hurtigere kan vi bruge binær søgning eller en anden intern jump search til at søge gennem blokkene i stedet for at stole på den meget langsommere lineære søgning.

Fibonacci search

Fibonacci search er en anden divide and conquer-algoritme, som har ligheder med både binær søgning og jump search. Den har fået sit navn, fordi den bruger Fibonacci-tallene til at beregne blokstørrelsen eller søgeområdet i hvert trin.

Fibonacci-tallene starter med nul og følger mønsteret 0, 1, 1, 1, 2, 2, 3, 3, 5, 8, 13, 21 … hvor hvert element er en addition af de to tal, der går umiddelbart forud for det.

Algoritmen arbejder med tre Fibonacci-taller ad gangen. Lad os kalde de tre tal fibM, fibM_minus_1 og fibM_minus_2, hvor fibM_minus_1 og fibM_minus_2 er de to tal umiddelbart før fibM i sekvensen:

fibM = fibM_minus_1 + fibM_minus_2

Vi initialiserer værdierne til 0,1 og 1 eller de tre første tal i Fibonacci-sekvensen for at undgå at få en indeksfejl i det tilfælde, hvor vores søgematrix lys indeholder et meget lille antal elementer.

Derpå vælger vi det mindste tal i Fibonacci-sekvensen, der er større end eller lig med antallet af elementer i vores søgematrix lys, som værdien fibM, og de to Fibonacci-tal umiddelbart før det som værdierne fibM_minus_1 og fibM_minus_2. Mens arrayet har elementer tilbage, og værdien af fibM er større end 1, skal vi:

• Sammenligne val med værdien af blokken i intervallet op til fibM_minus_2 og returnere indekset for elementet, hvis det passer.
• Hvis værdien er større end det element, vi i øjeblikket ser på, flytter vi værdierne for fibM, fibM_minus_1 og fibM_minus_2 to trin nedad i Fibonacci-sekvensen og nulstiller indekset til indekset for elementet.
• Hvis værdien er mindre end det element, vi i øjeblikket ser på, flytter vi værdierne for fibM, fibM_minus_1 og fibM_minus_2 et trin nedad i Fibonacci-sekvensen.

Lad os tage et kig på Python-implementeringen af denne algoritme:

Hvis vi bruger funktionen FibonacciSearch til at beregne:

>>> print(FibonacciSearch(, 6))

Lad os tage et kig på trin-for-trin-processen for denne søgning:

• Bestemmelse af det mindste Fibonacci-tal, der er større end eller lig med listens længde som fibM; i dette tilfælde er det mindste Fibonacci-tal, der opfylder vores krav, 13.
• Værdierne ville blive tildelt som:
  • fibM = 13
  • fibM_minus_1 = 8
  • fibM_minus_2 = 5
  • index = -1
• Næst kontrollerer vi elementet lys, hvor 4 er minimum af -1+5 . Da værdien af lys er 5, hvilket er mindre end den værdi, vi søger, flytter vi Fibonacci-tallene et trin nedad i sekvensen, hvilket giver værdierne:
  • fibM = 8
  • fibM_minus_1 = 5
  • fibM_minus_2 = 3
  • index = 4
• Næst kontrollerer vi elementet lys, hvor 7 er minimum af 4+3. Da værdien af lys er 8, hvilket er større end den værdi, vi søger, flytter vi Fibonacci-tallene to trin nedad i sekvensen.
  • fibM = 3
  • fibM_minus_1 = 2
  • fibM_minus_2 = 1
  • index = 4
• Nu kontrollerer vi elementet lys, hvor 5 er minimum af 4+1 . Værdien af lys er 6, hvilket er den værdi, vi søger efter!

Resultatet er som forventet:

5

Tidskompleksiteten for Fibonacci-søgning er O(log n), hvilket er det samme som binær søgning. Det betyder, at algoritmen er hurtigere end både lineær søgning og hoppesøgning i de fleste tilfælde.

Fibonacci-søgning kan bruges, når vi har et meget stort antal elementer at søge igennem, og vi ønsker at reducere den ineffektivitet, der er forbundet med at bruge en algoritme, der er afhængig af divisionsoperatoren.

En yderligere fordel ved at bruge Fibonacci-søgning er, at den kan rumme input-arrays, der er for store til at blive holdt i CPU-cache eller RAM, fordi den søger gennem elementer i stigende trinstørrelser og ikke i en fast størrelse.

Eksponentiel søgning

Eksponentiel søgning er en anden søgealgoritme, der kan implementeres ganske enkelt i Python, sammenlignet med spring søgning og Fibonacci søgning, som begge er en smule komplekse. Den er også kendt under navnene galopperende søgning, fordoblingssøgning og Struzik-søgning.

Exponentiel søgning er afhængig af binær søgning til at udføre den endelige sammenligning af værdier. Algoritmen fungerer ved at:

• Bestemme det område, hvor det element, vi leder efter, sandsynligvis befinder sig
• Anvende binær søgning for området for at finde det nøjagtige indeks for elementet

Python-implementeringen af den eksponentielle søgealgoritme er:

Det er Python-implementeringen af den eksponentielle søgealgoritme:

Hvis vi bruger funktionen til at finde værdien af:

>>> print(ExponentialSearch(,3))

Algoritmen fungerer ved at:

• Kontrollere, om det første element i listen passer til den værdi, vi søger efter – da lys er 1, og vi søger efter 3, indstiller vi indekset til 1 og går videre.
• Går gennem alle elementerne i listen, og mens elementet på indeksets position er mindre end eller lig med vores værdi, øger vi værdien af index eksponentielt i multipla af to:
  • index = 1, lys er 2, hvilket er mindre end 3, så indekset ganges med 2 og sættes til 2.
  • index = 2, lys er 3, hvilket er lig med 3, så indekset ganges med 2 og sættes til 4.
  • index = 4, lys er 5, hvilket er større end 3; løkken afbrydes på dette punkt.
• Derpå udføres en binær søgning ved at skære listen i skiver; arr. I Python betyder det, at underlisten vil indeholde alle elementer op til det 4. element, så vi kalder faktisk:

>>> BinarySearch(, 3)

som ville returnere:

2

Hvilket er indekset for det element, vi søger efter, både i den oprindelige liste og i den udskårne liste, som vi sender videre til den binære søgealgoritme.

Eksponentiel søgning kører på O(log i)-tid, hvor i er indekset for det element, vi søger efter. I værste tilfælde er tidskompleksiteten O(log n), når det sidste element er det element, vi søger efter (n er arrayets længde).

Exponentiel søgning fungerer bedre end binær søgning, når det element, vi søger efter, er tættere på begyndelsen af arrayet. I praksis bruger vi eksponentiel søgning, fordi det er en af de mest effektive søgealgoritmer til ubegrænsede eller uendelige arrays.

Interpolationssøgning

Interpolationssøgning er en anden divide and conquer-algoritme, der svarer til binær søgning. I modsætning til binær søgning begynder den ikke altid at søge i midten. Interpolationssøgning beregner den sandsynlige position for det element, vi søger efter, ved hjælp af formlen:

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

Hvor variablerne er:

• lys – vores input array
• val – det element, vi søger efter
• index – det sandsynlige indeks for det søgte element. Dette beregnes til at være en højere værdi, når val er tættere i værdi på elementet i slutningen af arrayet (lys), og lavere, når val er tættere i værdi på elementet i starten af arrayet (lys)
• low – arrayets startindeks
• high – arrayets sidste indeks

Algoritmen søger ved at beregne værdien af index:

• Hvis der findes et match (når lys == val), returneres indekset
• Hvis værdien af val er mindre end lys, genberegnes værdien for indekset ved hjælp af formlen for det venstre undermatrikel
• Hvis værdien af val er større end lys, genberegnes værdien for indekset ved hjælp af formlen for det højre underarray

Lad os gå videre og implementere interpolationssøgningen ved hjælp af Python:

Hvis vi bruger funktionen til at beregne:

>>> print(InterpolationSearch(, 6))

Vores startværdier ville være:

>>> print(InterpolationSearch(, 6))

Vores startværdier ville være:

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

Da lys er 6, hvilket er den værdi, vi søger efter, stopper vi udførelsen og returnerer resultatet:

5

Hvis vi har et stort antal elementer, og vores indeks ikke kan beregnes i én gentagelse, bliver vi ved med at genberegne værdierne for indeks efter at have justeret værdierne for high og low i vores formel.

Den tidskompleksitet for interpolationssøgning er O(log log n), når værdierne er ensartet fordelt. Hvis værdierne ikke er ensartet fordelt, er tidskompleksiteten i værste tilfælde O(n), hvilket er det samme som ved lineær søgning.

Interpolationssøgning fungerer bedst på ensartet distribuerede, sorterede arrays. Mens binær søgning starter i midten og altid deler sig i to, beregner interpolationssøgning elementets sandsynlige position og kontrollerer indekset, hvilket gør det mere sandsynligt at finde elementet i et mindre antal iterationer.

Hvorfor bruge Python til søgning?

Python er meget læsevenligt og effektivt sammenlignet med ældre programmeringssprog som Java, Fortran, C, C++ osv. En væsentlig fordel ved at bruge Python til implementering af søgealgoritmer er, at du ikke behøver at bekymre dig om casting eller eksplicit typning.

I Python vil de fleste af de søgealgoritmer, vi har diskuteret, fungere lige så godt, hvis vi søger efter en String. Husk, at vi skal foretage ændringer i koden for algoritmer, der bruger søgeelementet til numeriske beregninger, som f.eks. interpolationssøgningsalgoritmen.

Python er også et godt sted at starte, hvis du vil sammenligne ydelsen af forskellige søgealgoritmer for dit datasæt; det er nemmere og hurtigere at opbygge en prototype i Python, fordi du kan gøre mere med færre linjer kode.

For at sammenligne ydeevnen af vores implementerede søgealgoritmer i forhold til et datasæt kan vi bruge tidsbiblioteket i Python:

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

Konklusion

Der er mange mulige måder at søge efter et element i en samling på. I denne artikel har vi forsøgt at diskutere nogle få søgealgoritmer og deres implementeringer i Python.

Valg af algoritme er baseret på de data, du skal søge igennem; dit input array, som vi har kaldt lys i alle vores implementeringer.

• Hvis du vil søge i et usorteret array eller finde den første forekomst af en søgevariabel, er den bedste mulighed lineær søgning.
• Hvis du vil søge i et sorteret array, er der mange muligheder, hvoraf den enkleste og hurtigste metode er binær søgning.
• Hvis du har et sorteret array, som du vil søge igennem uden at bruge divisionsoperatoren, kan du bruge enten spring søgning eller Fibonacci søgning.
• Hvis du ved, at det element, du søger efter, sandsynligvis vil være tættere på starten af arrayet, kan du bruge eksponentiel søgning.
• Hvis dit sorterede array også er ensartet fordelt, vil den hurtigste og mest effektive søgealgoritme at bruge være interpolationssøgning.

Hvis du ikke er sikker på, hvilken algoritme du skal bruge med et sorteret array, skal du bare prøve hver af dem sammen med Pythons tidsbibliotek og vælge den, der klarer sig bedst med dit datasæt.