Labb 4 - Binärsökning

Som yrkesverksam kommer du ofta att hamna i situationer där du behöver hantera stora mängder data. Att kunna göra detta effektivt kan utgöra skillnaden mellan att kunna genomföra analysen över huvud taget. I den här labben får du träna på ett sätt att organisera data för att göra det effektivt sökbart genom sortering och att mäta tiden för en algoritm som söker i sorterade listor - binärsökning.

Fortsätt att använda Github som i de tidigare laborationerna. För bonusdatum, se kursöversikt i vänstermarginalen.

Mål

• Att kunna läsa en radindelad textfil till en lista av textsträngar
• Att kunna använda linjärsökning och binärsökning i små tillämpningar
• Att i detalj förstå algoritmerna för linjärsökning och binärsökning och kunna redogöra för skillnaden mellan dem och särskilt deras prestanda

Ordning och reda

Tänk på att inte blanda funktionsdefinitioner och annan programkod hur som helst i en programfil! Lägg eventuella import allra först, därefter funktionsdefinitioner och sist testkod med anrop av funktioner.

På den här labben ställs hårdare krav på struktur och organisation än på de tidigare labbarna. Följande 7 krav behöver vara uppfyllda:

1. Struktur: Koden ska vara indelad i funktioner. Det är ok att ha konstanter och ett anrop till main globalt. Resten av koden ska ligga i funktioner.
2. Funktionerna ska vara lagom stora. Lägg till exempel inte större delen av koden i en mainmetod och ha inte ett fåtal funktioner vars innehåll är one-liners som anropas en gång. 
3. Varje funktion ska vara dokumenterad med minst en välformulerad mening. Kommentarer ska förklara funktionens övergripande tanke. De ska inte vara en rad-för-rad-översättning från Python till ett mänskligt språk.
4. Använd lokala variabler för delresultat i en funktion. Undvik globala variabler. Globala konstanter är däremot ok.
5. Undvik onödig kodupprepning (Länkar till en externa sida.). Använd inte copy paste för en del av koden som borde ligga i en funktion istället. Stapla inte mängder med if-satser för något som borde ha en for-loop och copy paste:a inte upp samma kod med små variationer där du borde ha en funktion med variationerna som parametrar. Detta gäller även mellan filer.
6. Utskrifterna eller ska vara lätta att förstå. Användarna ska inte behöva se loggar från programmet eller tekniska felmeddelanden.
7. Dina namn på variabler och funktioner ska vara beskrivande och lättbegripliga. Använd inte f, x, y eller z som namn i den här labben.

Uppgift 1 – läs från fil till Pythonlista

Filen ordlista innehåller de flesta svenska ord som består av fem olika bokstäver. Titta på filen så ni får en uppfattning om hur den är uppbyggd. Den första ordfilen är latin1-kodad. Här finns en utf-8-kodad version: ordlistau. Spara en av ordfilerna på er labb4-katalog.

Skriv ett litet program som öppnar filen och läser in alla orden till en lista. Tips för hur man gör detta finns här: Inläsningstips.

För kontroll, skriv ut listans längd. Den ska vara 2511. Skriv också ut några av orden och några av ordlängderna. Satsen print(len(lis[0])) skriver ut längden av listans första ord om listan heter lis. Är längden 6 trots att alla orden innehåller 5 bokstäver? Det beror på att radslutstecknen som avslutar alla ordfilens rader också har lästs in och utgör del av orden. Komplettera i så fall programmet så att radsluttecknen tas bort. Tips för lösning finns här: radsluttips.

Uppgift 2 – linjärsökning i lista

Skriv en funktion som med hjälp av linjärsökning avgör om en lista innehåller ett visst element. Låt funktionen returnera True om elementet finns i listan och False annars. Låt funktionens huvud vara

def linsok(lista, elem):

Funktionskroppen kan innehålla en repetition över listan eller endast en tillämpning av en inbyggd operator. Skriv ett program som testar att funktionen fungerar genom att fråga efter ett ord och undersöka om det finns i den ordlista som lästs in i uppgift 1. För varje inläst ord anropas funktionen linsok. Dialogen kan se ut så här, använd "oändlig" repetition:

Uppgift 3 – linjärsökning efter "kuperade" ord

Skriv en funktion som med linjärsökning söker i en ordlista efter par av typen "alpin" och "pinal". Funktionen kan returnera en lista av funna ordpar eller skriva ut ordparen allteftersom de hittas. Välj själva!

Kuperingen vi söker innebär att de första bokstäverna i ordet förflyttas till slutet av ordet. Det kan göras med de 1-4 första bokstäverna och du behöver testa alla längder.

Ett konkret exempel med längden 2 är "alpin" ⇒ "al"+"pin" ⇒ "pin"+"al" ⇒ "pinal". Om första ordet är c₀c₁c₂c₃c₄ så ska det andra ordet vara c₂c₃c₄c₀c₁.

Ett konkret exempel med längden 1 är "agurk" ⇒ "a"+"gurk" ⇒ "gurk"+"a" ⇒ "gurka".

Strängar är immutable så en helt ny sträng måste konstrueras av två kopior av delsträngar till den första.

Funktionens huvud kan se ut så här (välj gärna namn själva):

def linsokkup(lista):

Binärsökning

Linjärsökningen i uppgift 3 går rätt långsamt. Datorn du använder kanske är så snabb att långsamheten inte märks vid sökning i den relativt korta ordlistan. Binärsökning är ändå mycket, mycket snabbare när man har sorterade data. Binärsökning finns här i Pythonkod i form av en funktion som kan användas direkt i labben: binärsökningsfunktion

Uppgift 4 – binärsökning i lista

Lös uppgift 2 med binärsökning istället för linjärsökning. Första delen ("skriv en funktion ...") är redan löst i och med att ni har fått binärsökningsfunktionen här ovanför! Den ska gå att använda direkt. Ni måste dock studera den så att ni förstår den fullständigt. Utgå från en kopia av programmet för Uppgift 2 och byt ut linjärsökningen mot binärsökning. Gör ett tillfälligt tillägg till binärsöknings-funktionen: print(li[mid]) direkt efter varje beräkning av mid. Tillägget finns redan i funktionen. Det är bara att ta bort kommentarstecknet #.

Hur många utskrifter kan man som mest vänta sig vid varje binärsökning då listans längd är 2511? Hur många blir det som minst? Prova några olika sökord. Uppfylls förväntningarna vid provkörningarna?

Uppgift 5 - rekursiv binärsökning

Försök först att lista ut hur man kan implementera binärsökning rekursivt genom att skriva en funktion som börjar såhär:

def br_search(v, target):
    """Returns True if the sorted list v contains target and False otherwise. 
    Undefined behaviour if v is not sorted"""
    pass # Remove this line when solving the task.

Ni får använda hjälpfunktioner.

Ett lösningsförslag till uppgiften finns här. Var beredd att svara på följande frågor vid redovisning:

• Kopieras listan som pekas ut av v vid ett anrop till br_search? Hur är det med anrop till helper?
• Peka ut basfall och rekursivt anrop i koden.

Uppgift 6 – binärsökning efter kuperade ord

Lös nu samma problem som i uppgift 3 ("alpin - pinal") men med binärsökning istället för linjärsökning. Utskriften i binärsökningsfunktionen ska inte användas här.

Extrauppgift för betygshöjning

Extrauppgiften består av två delar. Båda krävs för godkänd extrauppgift.

Del 1

Funktion som parameter: För att på ett elegant sätt minska den kodupprepning som förekommer i uppgiften kan sökfunktionen ges som parameter till funktioner som behöver anropa en sökfunktion.

• Byt ut funktionerna i uppgifterna 3 + 5 (sökning efter alpin-pinal-ord) mot en enda funktion som tar sökfunktionen som parameter.

Lite mer tips finns här: Funktion som parameter

Del 2

Riffelblandning av kortlekar: Visa med hjälp av ett testprogram att följande påstående är sant.

Om man upprepar en perfekt riffelblandning av en vanlig kortlek med 52 kort ett antal gånger så kommer man att återfå den ursprungliga ordningen mellan korten.

Hur många gånger behövs?

Riffelblandning går till så att man lyfter av exakt halva leken och "rifflar" ihop de två halvorna enligt blixtlåsprincipen, dvs man tar vartannat kort från ena respektive andra halvan. Om kortens index är 0, 1, 2,..., 51 så sätter en riffelblandning korten i ordningen 0, 26, 1, 27, 2, 28,... 25, 51.

En vanlig kortlek har 52 kort men skriv programmet så att det är lätt att ändra så att annan storlek på leken används. Jämt antal kort får förutsättas. Spelkorten kan representeras av talen 0,1, ... 51.