English web site
7. Algoritmer
7.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. Föreläsning 13 förbereder ytterligare denna laborationsomgång.
7.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): 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 7A - 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
7.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 7B - 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]
Sidansvarig: Peter Dalenius
Senast uppdaterad: 2012-12-11
