Göm menyn

6. Algoritmer

6.1 Inledning

Syftet med denna laboration är att öva på att formulera och implementera algoritmer. Kapitel 13 i lärboken behandlar algoritmer, ger exempel på hur man kan tänka och visar hur ett flertal basalgoritmer ser ut och fungerar.
Kapitlet Algoritmer förbereder för denna laboration.

6.2 Mönstermatchning

Algoritmer för mönstermatchning är användbara vid flera olika tillfällen. Ett av de enklaste fallen är när man vid kommandoraden listar alla filer som börjar med py genom att skriva ls py* där * är ett mönster som matchar i princip vad som helst. I datorintroduktionen i kursen TDDC66 Datorsystem och programmering tittade vi också på reguljära uttryck som är en kraftfull och generell form av mönstermatchning.

För den här laborationsomgången ska vi formulera och implementera en algoritm för mönstermatchning i listor. Vi söker igenom listan och mönstret parallellt och försöker se om de matchar varandra. I det här fallet kommer vi inte att matcha tecken för tecken, utan vi matchar element i listan mot varandra i sin helhet. Mönstret ['apa', 'banan'] matchar listan ['apa', 'banan'] men inte listan ['apa', 'konservburk'].

I vår mönstermatchning kommer vi att ha två typer av specialmönster: '&' som matchar exakt ett element, vilket som helst, och '--' som matchar noll, ett eller flera element, vilka som helst. Detta innebär t.ex. att mönstret ['a', '&', 'c'] matchar listorna ['a', 'b', 'c'] och ['a', 'd', 'c'], men inte ['a', 'c'] eller ['a', 'b', 'd', 'c']. På samma sätt kommer mönstret ['a', '--', 'c'] matcha listorna ['a', 'b', 'c'], ['a', 'b', 'd', 'c'] och ['a', 'c'], men inte ['a', 'b', 'c', 'd'].

Vi vill ha en huvudfunktion match som tar en lista och ett mönster som indata, och som returnerar True om listan matchar mönstret och False om listan inte matchar mönstret.

Hur går vi då tillväga för att komma fram till en lämplig algoritm? Ett sätt är att börja med att skriva pseudokod och försöka täcka alla tänkbara fall. På så sätt kan man få en idé om hur ens program kommer fungera och samtidigt är det lätt att få en överskådlig blick vilket gör det lätt att identifiera eventuella missade fall. Låt oss göra detta för vår mönstermatchare.

Pseudokod Kommentar
1. Om mönstret är tomt, returnera True om listan är tom, annars False Vi måste börja med ett basfall. Ett tomt mönster matchar en tom lista, men inte en lista som innehåller något.
2. Om '--' är först i mönstret
2.1. Om resten av mönstret matchar listan, returnera True Mönstret '--' kan matcha noll tecken, så om resten av mönstret matchar resten av listan har vi en matchning.
2.2. Om listan är tom, returnera False Om resten av mönstret inte matchar i punkten ovan, men listan är tom, så innebär det att mönstret innehåller fler tecken än listan och vi har ingen matchning.
2.3. Sök igenom resten av listan med samma mönster Annars låter vi '--' äta upp första elementet i listan och söker vidare.
3. Om listan är tom, returnera False Eftersom '--' är det enda som kan matcha noll tecken, samt att vi i första fallet kontrollerade om både mönstret och listan är tomma samtidigt, så räcker det att här kontrollera om listan är om. I så fall innehåller mönstret för många element och vi har ingen matchning.
4. Om '&' är först i mönstret, jämför resten av listan med resten av mönstret Vi låter '&' äta upp första elementet och försöker matcha resten.
5. Om första elementet i listan matchar första elementet i mönstret, fortsätt matcha resten av listan mot resten av mönstret Vi har nu passerat specialtecknen och kan matcha vanliga element mot varandra. Dessa tar vi ett i taget och anropar oss själva rekursivt.
6. I alla andra fall, returnera False Hit kommer vi om inget annat matchar, t.ex. om första elementen inte matchar eller om mönstret har tagit slut innan listan.

Omskrivet till Python ser mönstermatcharen ut så här (se match.py):

def match(seq, pattern): """ Returns whether given sequence matches the given pattern """ if not pattern: return not seq elif pattern[0] == '--': if match(seq, pattern[1:]): return True elif not seq: return False else: return match(seq[1:], pattern) elif not seq: return False elif pattern[0] == '&': return match(seq[1:], pattern[1:]) elif seq[0] == pattern[0]: return match(seq[1:], pattern[1:]) else: return False

Uppgift 6A - Utökad mönstermatchning

I denna uppgift ska du göra två saker: utöka mönstermatchningsrutinen som vi visade ovan och skapa en ny funktion som använder mönstermatcharen för att göra en sökning i en enkel databas.

Databasen innehåller uppgifter om ett antal böcker och är lagrad som listor i listor. Strukturen framgår av följande exempel (se books.py):

db = [[['författare', ['john', 'zelle']], ['titel', ['python', 'programming', 'an', 'introduction', 'to', 'computer', 'science']], ['år', 2010]], [['författare', ['armen', 'asratian']], ['titel', ['diskret', 'matematik']], ['år', 2012]], [['författare', ['j', 'glenn', 'brookshear']], ['titel', ['computer', 'science', 'an', 'overview']], ['år', 2011]], [['författare', ['john', 'zelle']], ['titel', ['data', 'structures', 'and', 'algorithms', 'using', 'python', 'and', 'c++']], ['år', 2009]], [['författare', ['anders', 'haraldsson']], ['titel', ['programmering', 'i', 'lisp']], ['år', 1993]]]

Er uppgift är att skriva en funktion search som tar ett mönster och en enkel databas enligt ovanstående format. Funktionen ska söka igenom databasen (listan) och matcha mönstret mot varje huvudelement i listan. Returvärdet ska vara en lista med de element som matchar, alternativt en tom lista om inga böcker matchar.

För att kunna använda vår tidigare mönstermatchare måste ni dock först utöka denna så att den klarar av att matcha listor i listor. Som den fungerar nu kan den enbart matcha raka listor.

Målet är att det ska funka så här:

>>> search([['författare', ['&', 'zelle']], ['titel', ['--', 'python', '--']], ['år', '&']], db) [[['författare', ['john', 'zelle']], ['titel', ['python', 'programming', 'an', 'introduction', 'to', 'computer', 'science']], ['år', 2010]], [['författare', ['john', 'zelle']], ['titel', ['data', 'structures', 'and', 'algorithms', 'using', 'python', 'and', 'c++']], ['år', 2009]]] >>> search(['--', ['år', 2042], '--'], db) [] >>> search(['--', ['titel', ['&', '&']], '--'], db) [[['författare', ['armen', 'asratian']], ['titel', ['diskret', 'matematik']], ['år', 2012]]]

Första körexemplet korrigerat! 121204 //AML

Testning I den här labben ingår det inga givna tester. Istället är det er uppgift att skriva egna tester för de funktioner som ni har implementerat. Vilken metod ni väljer för att göra testerna (Pythons inbyggda unittest eller assert) är upp till er.

6.3 Sökning

I kapitel 13.3 i kursboken behandlas två standardalgoritmer för sortering: selectionsort och mergesort. En annan klassisk sorteringsalgoritm är quicksort. Den börjar med att välja ut ett så kallat pivotelement (uttalas "pivå" med betoning på sista stavelsen). Detta element placeras i mitten av listan och blir den punkt som man sorterar resten av listan runt. Efter att pivotelementet valts ut är nästa steg att grovsortera listan så att elementen som ska komma innan pivotelementet placeras till vänster och elementen som ska komma efter pivotelementet placeras till höger. Därefter anropas quicksort rekursivt, en gång för elementen till vänster och en gång för elementen till höger. Förr eller senare kommer quicksort anropas med en lista av ett element, och eftersom en lista med ett element per definition är sorterad så kan algoritmen avslutas i det läget. Så här kan det se ut:

Ursprungslista: [34, 93, 23, 14, 56, 26, 17, 59, 75] Steg 1: Partitionering Valt pivotelement: 34 Element till vänster (mindre): [23, 14, 26, 17] Element till höger (större): [93, 56, 59, 75] Steg 2: Rekursiv sortering av dellistor Valt pivotelement: 34 Element till vänster (mindre): [14, 17, 23, 26] Element till höger (större): [56, 59, 75, 93] Steg 3: Slå ihop resultatet Sorterad lista: [14, 17, 23, 26, 34, 56, 59, 75, 93]

Det finns många sätt att välja pivotelement. I vårt exempel ovan gjorde vi det enkelt för oss och valde det första elementet i listan. Om listan redan är sorterad ligger dock det minsta elementet först och det gör att vår uppdelning blir skev. Till vänster får vi inga element och till höger får vi resten av listan. Man önskar givetvis att det pivotelement man väljer ska ligga så nära mitten som möjligt. Ett sätt att förbättra chanserna är att ta det mittersta elementet av tre, t.ex. de tre första eller första, mittersta och sista i listan. I följande uppgift rekommenderas dock att du väljer det första elementet som pivot.

Om du har svårt att föreställa dig hur quicksort fungerar kan det underlätta om du klipper ut små papperslappar, skriver slumpmässiga tal på dem och försöker sortera dem för hand, så som quicksort skulle göra.

Uppgift 6B - Quicksort

Din uppgift är att skriva en funktion quicksort som kan sortera en lista med tal enligt metoden som beskrivits ovan.

>>> quicksort([45, 17, 39]) [17, 39, 45] >>> quicksort([26, 4, 18, 27, 6, 4, 12]) [4, 4, 6, 12, 18, 26, 27]

Testning I den här labben ingår det inga givna tester. Istället är det er uppgift att skriva egna tester för de funktioner som ni har implementerat. Vilken metod ni väljer för att göra testerna (Pythons inbyggda unittest eller assert) är upp till er.

Feedback För att ständigt förbättra undervisningen uppskattar vi om ni individuellt fyller i följande formulär. Notera att det är friviligt och inte påverkar betygen på något sätt.


Sidansvarig: Peter Dalenius
Senast uppdaterad: 2016-08-29