IDA - Institutionen för datavetenskap

Laboration 6 - Sökning, sortering och riktiga program

Syftet med denna laboration är att ni ska få en bättre förståelse för vilket arbete som krävs av processorn och hur ni kan minimera den tid era program arbetar med att gå igenom listor eller söka efter data. Slutligen ska ni skriva några riktiga program som ni faktiskt kan ha användning för senare i er utbildning.

Inlämningsuppgifter

Uppgift 6a - Tillbaka till Laboration 1

Det är dags att reflektera över vad ni har lärt er under kursens gång och se ifall det finns utrymme att förbättra era tidigare lösningar. I laboration 1 skrev ni två olika funktioner för att få summan av ett intervall och en annan funktion för att få produkten av ett intervall. Ni skrev även en funktion för att hitta det minsta talet som är delbart med samtliga tal från 1 till och med 13.

Er uppgift är att skriva om uppgift 1a och 1b så att ni kan lösa båda problemen med hjälp av en gemensam funktion och ett lambdauttryck per delproblem. Lambdauttrycket skall alltså skickas med som en parameter till funktionen

Uppgift 6b - Företagsdatabasen

En databas över personer som arbetar på ett företag definieras som en lista med tabeller. Skriv en funktion som söker i databasen. Första argumentet till funktionen är databasen som ska genomsökas, andra argumentet anger vilket fält matchningen ska ske emot och tredje argumentet anger vilket värde det fältet ska ha. Returvärdet ska vara en lista med de poster i databasen som matchar sökningen.

Körexempel:

>>> db = [
{'name': 'Jakob', 'position': 'assistant'},
{'name': 'Åke', 'position': 'assistant'},
{'name': 'Ola', 'position': 'examiner'},
{'name': 'Henrik', 'position': 'assistant'}
]
>>> dbsearch(db, 'position', 'examiner')
[{'position': 'examiner', 'name': 'Ola'}]
  

Uppgift 6c - Needles and haystacks

Skriv en funktion som tar reda på om en viss lista innehåller ett visst element. Du får inte använda dig av Pythons in-operator! (nyckelordet in används i flera sammanhang än som en operator, det är ok att ha med nyckelordet för att skapa en for-loop, men du får inte använda det för att kontrollera om ett viss element finns i listan).

Körexempel:

>>> haystack = 'Can you find the needle in this haystack?'.split()
>>> contains('find', haystack)
True
>>> contains('needle', haystack)
True
>>> contains('haystack', haystack)
False
  

Uppgift 6d - Linjärsökning

Linjärsökning är den simplaste formen av sökning ni kan tänka er. Det går helt enkelt ut på att ni börjar söka från början av listan och slutar när ni hittar elementet ni letar efter eller kommer till slutet av listan. Linjärsökning har fördelen att den även fungerar för osorterad data.

Skriv en funktion linear_search som söker igenom en lista (haystack) efter ett specifikt värde (needle). Funktionen ska dessutom ha möjlighet att ta ett tredje argument med en funktion för att specificera hur jämförelsen ska gå till.

Körexempel:

imdb = [
    {'title': 'The Rock', 'actress': 'Nicholas Cage', 'score': 11},          
    {'title': 'Raise your voice', 'actress': 'Hilary Duff', 'score': 10},    
    {'title': 'Black Hawk Down', 'actress': 'Eric Bana', 'score': 12},
    ...
]

linear_search(imdb, 10, lambda e: e['score'])
> {'title': 'Raise your voice', 'actress': 'Hilary Duff', 'score': 10}
  

Uppgift 6e - binärsökning

Binärsökning fungerar om mängden ni söker i är sorterad och på så sätt att ni hela tiden jämför det eftersökta elementet med elementet på mittenpositionen i sökmängden, därefter begränsar ni sökmängden beroende på utfallet av jämförelsen.

Skriv en funktion binary_search som söker igenom en lista (haystack) efter ett specifikt värde (needle). Funktionen ska dessutom ha möjlighet att ta ett tredje argument med en funktion för att specificera hur jämförelsen av två element i listan ska gå till.

Körexempel:

>>> people = [{'name': 'Pontus', 'age': 30},
              {'name': 'Sara', 'age': 20},
              {'name': 'Xavier', 'age': 19}]
# listan people är här sorterad på personernas namn      
>>> binary_search(people, 'Pontus', lambda e: e['name'])
{'name': 'Pontus', 'age': 30}

  

Uppgift 6f - Insertion sort

Ofta är det bra att kunna sortera data så att det går snabbare att söka igenom den. Skriv en funktion insertion_sort som tar en lista med element och en funktion för att specificera hur sorteringen ska gå till. Information om hur den fungerar hittar ni här.

Precis som i förra uppgiften ska funktionen ta emot dels listan som ska sorteras samt ha möjlighet att ta emot en funktion för att jämföra två element.

Körexempel:

>>> db = [
('j', 'g'), ('a', 'u'), ('k', 'l'), ('o', 'i'),
('b', 's'), ('@', '.'), ('p', 's'), ('o', 'e')
]
>>> insertion_sort(db, lambda e: e[0])
>>> db
[('@', '.'), ('a', 'u'), ('b', 's'), ('j', 'g'), ('k', 'l'), 
('o', 'e'), ('o', 'i'), ('p', 's')]
  

Uppgift 6g - Quicksort

Skriv en funktion quicksort som tar en lista med element och en funktion för att specificera hur sorteringen ska gå till. Information om hur algoritmen fungerar hittar ni på denna länk.

Körexempel:

>>> db = [
('j', 'g'), ('a', 'u'), ('k', 'l'), ('o', 'i'),
('b', 's'), ('@', '.'), ('p', 's'), ('o', 'e')
]
>>> quicksort(db, lambda e: e[0])
>>> db
[('@', '.'), ('a', 'u'), ('b', 's'), ('j', 'g'), ('k', 'l'),
('o', 'e'), ('o', 'i'), ('p', 's')]
  

Uppgift 6h - Copyright

I den här uppgiften ska ni lägga till copyright-information i källkodsfiler. Ni ska dessutom enkelt kunna byta ut copyright-informationen till en annan ifall ni vill publicera koden under olika licensvilkor.

Skriv ett program som kan användas på alla era källkodsfiler för att infoga copyright-information i filen. Informationen ska infogas mellan markörerna BEGIN COPYRIGHT och END COPYRIGHT. Ifall dessa markörer inte finns i filen ska filen inte förändras. Ifall markörerna förekommer på flera ställen i filen ska copyright-informationen infogas på varje plats i filen. Ifall det redan finns information mellan markörerna i filen ska den informationen ersättas. Markörerna ska vara kvar i den resulterande filen så att ni senare kan använda samma program för att byta till annan information. Programmet ska acceptera två kommandoradsparametrar. Den ena ska vara en fil som innehåller copyright-informationen och den andra ska vara den fil eller katalog där informationen ska infogas. Ifall det är en katalog ska samtliga filer i katalogen påverkas. Programmet ska även acceptera en flagga för att bara en viss filändelse ska behandlas och en flagga för att ändra filändelsen på resultatfilen.

Körexempel, där flagga c bestämmer att filer av typen .py skall ändras, flaggan u bestämmer att den nya filändelsen skall vara .c.py:

$ copyright.py [copyright-fil] [destination] -c py -u c.py 
  

Tips: Ni har tidigare lärt er om Regexp och sett att det går att nyttja i Python. Det är inte ett krav att lösa denna uppgift med hjälp av Regexp, men det är ett lämpligt problem att använda Regexp till. Delen man med fördel kan använda Regexp till är alltså att identifiera och byta ut delar av texten som matchar ett särskilt mönster.

Krav

Nedan följer de krav som finns på hur ni löser denna laboration som är utöver det som framgår i själva instruktionen:

• Alla lösningar skall ha huvudprogram som demonstrerar funktionaliteten hos varje del av laborationen