Laboration 4 – Enkel sökning

Fortsätt att använda Github som i de tidigare laborationerna. Deadline för bonus är 2017-09-29. Skriv ut ett labbkvitto för att få papperskopia på dina kursresultat.

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.

I labbtexten finns dessa nya turkosa rutor med extra viktiga påpkanden. Gå vidare till nästa uppgift först när ni har uppfyllt kraven i rutan. Fråga handledare om ni inte förstår det som står i rutan!

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:

Ditt ord: ajour
ajour finns
Ditt ord: banan
banan finns inte
Ditt ord: kvasi
kvasi finns
:
:

Körexemplet ovan avser att visa att funktionen linsok fungerar. Funktionen linsok måste alltså användas i koden som ger utskriften ovan. Funktionen linsok kan vara väldigt kort.

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!

Andra ordet i paret konstrueras ur det första enligt principen "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₁. 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):

Krav på funktionen linsokkup:

Ett anrop av funktionen ska ge alla ordpar av typen alpin/pinal som finns den ordlista som ges som parameter. Returnera en lista med paren eller låt funktionen skriva ut ordparen.
Funktionen linsokkup ska anropa funkionen linsok även om linsok är väldigt kort.

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 beskrivs i Pythonkramarens kapitel 7, algorimen finns också 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 4 är uppgift 2, fast med binärsökning istället för linjärsökning. Detta ska åstadkommas genom att anropet av funktionen linsok i uppgift 2 byts mot ett anrop av funktionen binsok.

Uppgift 5 – 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.

Uppgift 5 är uppgift 3, fast med binärsökning istället för linjärsökning. Detta ska åstadkommas genom att anropet av funktionen linsok i uppgift 3 byts mot ett anrop av funktionen binsok.

Att redovisa för grunduppgift:

Helst i en enda fil, programkod för
- Funktionerna linsok, binsok, linsokkup och binsokkup (andra namn är OK)
- Inläsning av ordlistan
Testprogrammet med binärsökning och utskrifter av jämförelseord (Uppgift 4).
Detaljförståelse av algoritmerna för linjärsökning och binärsökning.
Förbered svar!
Hur många jämförelser kan man maximalt vänta sig vid linjärsökning respektive binärsökning i en sorterad lista med n st element. Om n = 2511?
Förbered svar och förklaring!
Demonstration av linsokkup och binsokkup som båda hittar
alla "alpin–pinal"–orden.

Förbered redovisningen så att ni kan börja direkt när det är er tur.
Tag fram kvittensbladen innan handledaren kommer!

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.

Att redovisa för extrauppgift:

del 1: Demonstrera funktionen som söker efter "kuperade" ord där listsökfunktion (linjär resp binär) ges som parameter. Visa förstås anrop med linjärsökning och anrop med binärsökning.

del 2: För riffelblandning krävs att antalet kort går lätt att ändra så att man kan få svar på frågan om hur många gånger som krävs för andra jämna antal än 52.

Var beredda att redovisa när handledaren kommer. Tag fram kvittensbladen i förväg!

Frivillig extrauppgift som ej ger betygshöjning

För er som är extra intresserade:

Tidmätning: För att övertyga sig om att binärsökning verkligen går snabbare än linjärsökning: Tidmätningsuppgift