Introduktion

Söka efter data som lagras i olika datastrukturer är en viktig del av i stort sett alla program.

Det finns många olika algoritmer som kan användas vid sökning, och alla har olika implementeringar och förlitar sig på olika datastrukturer för att få jobbet gjort.

Att kunna välja en specifik algoritm för en viss uppgift är en nyckelkompetens för utvecklare och kan innebära skillnaden mellan en snabb, pålitlig och stabil applikation och en applikation som smulas sönder av en enkel förfrågan.

• Medlemskapsoperatörer
• Linjär sökning
• Binär sökning
• Språngsökning
• Fibonacci-sökning
• Exponentiell sökning
• Interpoleringssökning

Membership Operators

Algoritmer utvecklas och optimeras med tiden som ett resultat av ständig utveckling och behovet av att hitta de mest effektiva lösningarna för underliggande problem inom olika områden.

Ett av de vanligaste problemen inom datavetenskapens område är att söka i en samling och avgöra om ett visst objekt finns i samlingen eller inte.

Nästan alla programmeringsspråk har sin egen implementering av en grundläggande sökalgoritm, vanligen som en funktion som returnerar ett Boolean värde på True eller False när ett objekt hittas i en given samling objekt.

I Python är det enklaste sättet att söka efter ett objekt att använda medlemskapsoperatorer – de heter så eftersom de gör det möjligt att avgöra om ett givet objekt är en medlem i en samling.

Dessa operatörer kan användas med alla iterabla datastrukturer i Python, inklusive strängar, listor och tupler.

• in – Återger True om det givna elementet är en del av strukturen.
• not in – Returnerar True om det givna elementet inte är en del av strukturen.

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

Membership-operatorer räcker när allt vi behöver göra är att ta reda på om en delsträng existerar inom en given sträng, eller avgöra om två strängar, listor eller tupler skär varandra när det gäller de objekt de innehåller.

I de flesta fall behöver vi objektets position i sekvensen, förutom att bestämma om det finns eller inte; medlemskapsoperatorer uppfyller inte detta krav.

Det finns många sökalgoritmer som inte är beroende av inbyggda operatörer och som kan användas för att söka efter värden snabbare och/eller mer effektivt. Dessutom kan de ge mer information, till exempel elementets position i samlingen, i stället för att bara kunna fastställa dess existens.

Linjär sökning

Linjär sökning är en av de enklaste sökalgoritmerna, och den enklaste att förstå. Vi kan se den som en upptrappad version av vår egen implementering av Pythons in-operator in.

Algoritmen består av att iterera över en array och återge indexet för den första förekomsten av ett objekt när det hittats:

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

Så om vi använder funktionen för att beräkna:

>>> print(LinearSearch(, 2))

När vi utför koden får vi följande resultat:

1

Detta är indexet för den första förekomsten av det objekt vi söker efter – med tanke på att Python-index är 0-baserade.

Tidskomplexiteten för linjär sökning är O(n), vilket innebär att den tid det tar att utföra sökningen ökar med antalet objekt i vår inmatningslista lys.

Linjär sökning används inte ofta i praktiken, eftersom samma effektivitet kan uppnås genom att använda inbyggda metoder eller befintliga operatörer, och den är inte lika snabb eller effektiv som andra sökalgoritmer.

Linjär sökning passar bra när vi behöver hitta den första förekomsten av ett objekt i en osorterad samling eftersom den, till skillnad från de flesta andra sökalgoritmer, inte kräver att samlingen är sorterad innan sökningen påbörjas.

Binär sökning

Binär sökning följer en divide and conquer-metodik. Den är snabbare än linjär sökning men kräver att matrisen är sorterad innan algoritmen utförs.

Antag att vi söker efter ett värde val i en sorterad matris jämför algoritmen val med värdet på det mittersta elementet i matrisen, som vi kallar mid.

• Om mid är det element som vi letar efter (i bästa fall), returnerar vi dess index.
• Om inte, identifierar vi vilken sida av mid val som det är mest troligt att den befinner sig på baserat på om val är mindre eller större än mid, och kastar den andra sidan av arrayen.
• Vi följer sedan rekursivt eller iterativt samma steg och väljer ett nytt värde för mid, jämför det med val och kasserar hälften av de möjliga träffarna i varje iteration av algoritmen.

Den binära sökalgoritmen kan skrivas antingen rekursivt eller iterativt. Rekursion är generellt sett långsammare i Python eftersom det kräver allokering av nya stackramar.

Då en bra sökalgoritm bör vara så snabb och exakt som möjligt, låt oss betrakta den iterativa implementeringen av binär sökning:

Om vi använder funktionen för att räkna ut:

>>> BinarySearch(, 20)

Vi får resultatet:

1

som är indexet för det värde som vi söker efter.

Den åtgärd som algoritmen utför härnäst i varje iteration är en av flera möjligheter:

• Returnering av indexet för det aktuella elementet
• Sökning genom den vänstra halvan av arrayen
• Sökning genom den högra halvan av arrayen

Vi kan bara välja en möjlighet per iteration, och vår pool av möjliga träffar delas med två i varje iteration. Detta gör att tidskomplexiteten för binär sökning blir O(log n).

En nackdel med binär sökning är att om det finns flera förekomster av ett element i matrisen returneras inte indexet för det första elementet, utan snarare indexet för det element som ligger närmast mitten:

>>> print(BinarySearch(, 4))

Att köra den här koden ger index för det mittersta elementet:

1

En jämförelse: att utföra en linjär sökning på samma matris skulle ge:

0

vilket är index för det första elementet. Vi kan dock inte kategoriskt säga att binär sökning inte fungerar om en array innehåller samma element två gånger – den kan fungera precis som linjär sökning och återge den första förekomsten av elementet i vissa fall.

Om vi till exempel utför binär sökning på arrayen och söker efter 4 skulle vi få 3 som resultat.

Binär sökning är ganska vanligt förekommande i praktiken eftersom den är effektiv och snabb i jämförelse med linjär sökning. Det har dock vissa brister, till exempel att det är beroende av //-operatören. Det finns många andra divide and conquer-sökalgoritmer som härstammar från binär sökning, låt oss undersöka några av dem härnäst.

Jump Search

Jump Search liknar binär sökning i det avseendet att den arbetar med en sorterad matris och använder en liknande divide and conquer-strategi för att söka igenom den.

Den kan klassificeras som en förbättring av den linjära sökalgoritmen eftersom den är beroende av linjär sökning för att utföra den faktiska jämförelsen när den söker efter ett värde.

Givet en sorterad matris söker vi i stället för att söka igenom matrisens element stegvis i hopp. Så i vår ingångslista lys, om vi har en hoppstorlek på jump kommer vår algoritm att överväga element i ordningen lys, lys, lys, lys, lys och så vidare.

Med varje hopp lagrar vi det föregående värdet vi tittade på och dess index. När vi hittar en uppsättning värden där lys<element<lys, utför vi en linjär sökning med lys som det vänstra elementet och lys som det högra elementet i vår sökuppsättning:

Då det här är en komplex algoritm, låt oss betrakta den stegvisa beräkningen av hopp-sökning med den här indata:

>>> print(JumpSearch(, 5))

• Spring-sökning skulle först bestämma hoppstorleken genom att beräkna math.sqrt(len(lys)). Eftersom vi har 9 element skulle hoppstorleken vara √9 = 3.
• Nästan beräknar vi värdet av variabeln right, som är det minsta värdet av matrisens längd minus 1, eller värdet av left+jump, vilket i vårt fall skulle vara 0+3= 3. Eftersom 3 är mindre än 8 använder vi 3 som värde för right.
• Nu kontrollerar vi om vårt sökelement, 5, ligger mellan lys och lys. Eftersom 5 inte ligger mellan 1 och 4 går vi vidare.
• Nästan gör vi beräkningarna igen och kontrollerar om vårt sökelement ligger mellan lys och lys, där 6 är 3+hopp. Eftersom 5 ligger mellan 4 och 7 gör vi en linjär sökning på elementen mellan lys och lys och returnerar indexet för vårt element som:

4

Tidskomplexiteten för jump search är O(√n), där √n är hoppstorleken och n är listans längd, vilket placerar jump search mellan de linjära och binära sökalgoritmerna när det gäller effektivitet.

Den enskilt viktigaste fördelen med jump search jämfört med binär sökning är att den inte är beroende av divisionsoperatören (/).

I de flesta CPU:er är det kostsamt att använda divisionsoperatorn jämfört med andra grundläggande aritmetiska operationer (addition, subtraktion och multiplikation), eftersom implementeringen av divisionsalgoritmen är iterativ.

Kostnaden i sig själv är mycket liten, men när antalet element som ska genomsökas är mycket stort, och antalet divisionsoperationer som vi måste utföra ökar, kan kostnaden öka successivt. Därför är hoppsökning bättre än binär sökning när det finns ett stort antal element i ett system där även en liten ökning av hastigheten spelar roll.

För att göra hoppsökning snabbare kan vi använda binär sökning eller en annan intern hoppsökning för att söka igenom blocken, i stället för att förlita oss på den mycket långsammare linjära sökningen.

Fibonacci-sökning

Fibonacci-sökning är en annan sönderdelnings- och erövringsalgoritm som har likheter med både binär sökning och hoppsökning. Den har fått sitt namn eftersom den använder Fibonacci-tal för att beräkna blockstorleken eller sökområdet i varje steg.

Fibonacci-talen börjar med noll och följer mönstret 0, 1, 1, 1, 2, 3, 3, 5, 8, 13, 21… där varje element är tillägget av de två tal som omedelbart föregår det.

Algoritmen arbetar med tre Fibonacci-tal åt gången. Låt oss kalla de tre talen fibM, fibM_minus_1 och fibM_minus_2 där fibM_minus_1 och fibM_minus_2 är de två talen omedelbart före fibM i sekvensen:

fibM = fibM_minus_1 + fibM_minus_2

Vi initialiserar värdena till 0,1 och 1 eller de tre första talen i Fibonacci-sekvensen för att undvika att få ett indexfel i det fall där vår sökarray lys innehåller ett mycket litet antal element.

Därefter väljer vi det minsta talet i Fibonacci-sekvensen som är större än eller lika med antalet element i vår sökarray lys, som värdet fibM, och de två Fibonacci-talen omedelbart före det som värdena fibM_minus_1 och fibM_minus_2. Medan matrisen har element kvar och värdet av fibM är större än ett, gör vi:

• Varjämför val med värdet av blocket i intervallet upp till fibM_minus_2, och returnerar indexet för elementet om det stämmer.
• Om värdet är större än det element vi för närvarande tittar på flyttar vi värdena för fibM, fibM_minus_1 och fibM_minus_2 två steg nedåt i Fibonacci-sekvensen och återställer indexet till elementets index.
• Om värdet är mindre än det element vi för närvarande tittar på flyttar vi värdena för fibM, fibM_minus_1 och fibM_minus_2 ett steg nedåt i Fibonacci-sekvensen.

Låt oss ta en titt på Pythonimplementationen av denna algoritm:

Om vi använder funktionen FibonacciSearch för att beräkna:

>>> print(FibonacciSearch(, 6))

Låt oss ta en titt på den stegvisa processen för denna sökning:

• Bestäm det minsta Fibonacci-talet som är större än eller lika med längden på listan som fibM; i det här fallet är det minsta Fibonacci-talet som uppfyller våra krav 13.
• Värdena skulle tilldelas som:
  • fibM = 13
  • fibM_minus_1 = 8
  • fibM_minus_2 = 5
  • index = -1
• Nästan kontrollerar vi elementet lys där 4 är minimum av -1+5 . Eftersom värdet för lys är 5, vilket är mindre än det värde vi söker, flyttar vi Fibonacci-talen ett steg nedåt i sekvensen, vilket gör att värdena:
  • fibM = 8
  • fibM_minus_1 = 5
  • fibM_minus_2 = 3
  • index = 4
• Nästan kontrollerar vi elementet lys där 7 är minimum av 4+3. Eftersom värdet för lys är 8, vilket är större än det värde vi söker, flyttar vi Fibonacci-talen två steg nedåt i sekvensen.
  • fibM = 3
  • fibM_minus_1 = 2
  • fibM_minus_2 = 1
  • index = 4
• Nu kontrollerar vi elementet lys där 5 är minimum av 4+1 . Värdet för lys är 6, vilket är det värde vi söker efter!

Resultatet är som väntat:

5

Tidskomplexiteten för Fibonacci-sökning är O(log n); samma som för binär sökning. Detta innebär att algoritmen är snabbare än både linjär sökning och hopp-sökning i de flesta fall.

Fibonacci-sökning kan användas när vi har ett mycket stort antal element att söka igenom och vi vill minska den ineffektivitet som är förknippad med att använda en algoritm som förlitar sig på divisionsoperatorn.

En ytterligare fördel med att använda Fibonacci-sökning är att den kan hantera inmatningsmatriser som är för stora för att hållas i CPU-cache eller RAM, eftersom den söker igenom elementen i ökande stegstorlekar och inte i en fast storlek.

Exponentiell sökning

Exponentiell sökning är en annan sökalgoritm som kan implementeras ganska enkelt i Python, jämfört med hopp-sökning och Fibonacci-sökning som båda är lite komplexa. Den är också känd under namnen galopperande sökning, fördubblingssökning och Struzik-sökning.

Exponentiell sökning är beroende av binär sökning för att utföra den slutliga jämförelsen av värden. Algoritmen fungerar genom att:

• Bestämma intervallet där det element vi letar efter sannolikt finns
• Använda binär sökning för intervallet för att hitta det exakta indexet för elementet

Python-implementationen av den exponentiella sökalgoritmen är:

Om vi använder funktionen för att hitta värdet av:

>>> print(ExponentialSearch(,3))

Algoritmen fungerar på följande sätt:

• Kontrollera om det första elementet i listan matchar det värde vi söker efter – eftersom lys är 1 och vi söker efter 3, ställer vi in indexet på 1 och går vidare.
• Går igenom alla element i listan, och medan elementet på indexets position är mindre än eller lika med vårt värde, ökar vi exponentiellt värdet på index i multiplar av två:
  • index = 1, lys är 2, vilket är mindre än 3, så indexet multipliceras med 2 och sätts till 2.
  • index = 2, lysär 3, vilket är lika med 3, så indexet multipliceras med 2 och sätts till 4.
  • index = 4, lys är 5, vilket är större än 3. Slingan bryts vid denna punkt.
• Den utför sedan en binär sökning genom att skära listan; arr. I Python innebär detta att underlistan kommer att innehålla alla element upp till det fjärde elementet, så vi anropar egentligen:

>>> BinarySearch(, 3)

som skulle ge tillbaka:

2

Vilket är indexet för det element vi söker efter både i den ursprungliga listan och i den delade listan som vi skickar vidare till algoritmen för binär sökning.

Exponentiell sökning går på O(log i)-tid, där i är indexet för det element vi söker efter. I värsta fall är tidskomplexiteten O(log n), när det sista elementet är det element vi söker (n är längden på matrisen).

Exponentiell sökning fungerar bättre än binär sökning när det element vi söker är närmare början av matrisen. I praktiken använder vi exponentiell sökning eftersom det är en av de mest effektiva sökalgoritmerna för obegränsade eller oändliga matriser.

Interpolationssökning

Interpolationssökning är en annan divide and conquer-algoritm som liknar binär sökning. Till skillnad från binär sökning börjar den inte alltid söka i mitten. Interpolationssökning beräknar den sannolika positionen för det element vi söker med hjälp av formeln:

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

Där variablerna är:

• lys – vår inmatningsmatris
• val – elementet vi söker
• index – det sannolika indexet för det sökta elementet. Detta beräknas vara ett högre värde när val ligger närmare elementet i slutet av matrisen (lys) och lägre när val ligger närmare elementet i början av matrisen (lys)
• låg – startindexet för matrisen
• hög – det sista indexet för matrisen

Algoritmen söker genom att beräkna värdet av index:

• Om en matchning hittas (när lys == val) returneras indexet
• Om värdet av val är mindre än lys beräknas värdet för indexet på nytt med hjälp av formeln för den vänstra delmängden
• Om värdet av val är större än lys, så räknas värdet för indexet om med hjälp av formeln för det högra delfältet

Vi går vidare och implementerar interpolationssökningen med hjälp av Python:

Om vi använder funktionen för att beräkna:

>>> print(InterpolationSearch(, 6))

Våra utgångsvärden skulle vara:

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

Då lys är 6, vilket är det värde som vi söker efter, avbryter vi utförandet och returnerar resultatet:

5

Om vi har ett stort antal element och vårt index inte kan beräknas i en iteration fortsätter vi att räkna om värdena för index efter att ha justerat värdena för hög och låg i vår formel.

Tidskomplexiteten för interpolationssökning är O(log log n) när värdena är jämnt fördelade. Om värdena inte är jämnt fördelade är tidskomplexiteten i värsta fall O(n), samma som för linjär sökning.

Interpolationssökning fungerar bäst på jämnt fördelade, sorterade matriser. Medan binär sökning börjar i mitten och alltid delar i två, beräknar interpolationssökning elementets troliga position och kontrollerar indexet, vilket gör det mer sannolikt att hitta elementet i ett mindre antal iterationer.

Varför använda Python för sökning?

Python är mycket lättläst och effektivt jämfört med äldre programmeringsspråk som Java, Fortran, C, C++ osv. En viktig fördel med att använda Python för att implementera sökalgoritmer är att du inte behöver oroa dig för casting eller explicit typning.

I Python fungerar de flesta av de sökalgoritmer vi diskuterat lika bra om vi söker efter en sträng. Tänk på att vi måste göra ändringar i koden för algoritmer som använder sökelementet för numeriska beräkningar, som interpolationssökalgoritmen.

Python är också ett bra ställe att börja på om du vill jämföra prestandan hos olika sökalgoritmer för din datamängd; det är enklare och snabbare att bygga en prototyp i Python eftersom du kan göra mer med färre rader kod.

För att jämföra prestandan hos våra implementerade sökalgoritmer mot en datamängd kan vi använda tidsbiblioteket i Python:

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

Slutsats

Det finns många möjliga sätt att söka efter ett element i en samling. I den här artikeln försökte vi diskutera några sökalgoritmer och deras implementeringar i Python.

Välja vilken algoritm du ska använda baseras på de data du ska söka igenom; din inmatningsarray, som vi har kallat lys i alla våra implementeringar.

• Om du vill söka i en osorterad array eller hitta den första förekomsten av en sökvariabel är det bästa alternativet linjär sökning.
• Om du vill söka i en sorterad array finns det många alternativ varav den enklaste och snabbaste metoden är binär sökning.
• Om du har en sorterad matris som du vill söka igenom utan att använda divisionsoperatorn kan du använda antingen hopp-sökning eller Fibonacci-sökning.
• Om du vet att det element du söker efter troligen ligger närmare början av matrisen kan du använda exponentiell sökning.
• Om din sorterade array också är jämnt fördelad är den snabbaste och mest effektiva sökalgoritmen att använda interpolationssökning.

Om du inte är säker på vilken algoritm du ska använda med en sorterad array, kan du bara prova var och en av dem tillsammans med Pythons tidsbibliotek och välja den som presterar bäst med ditt dataset.