IDA - Institutionen för datavetenskap

ADT

Vad är Abstrakta Datatyper (ADT)?

Hittills har ni bara arbetat med väldigt vanligt förekommande datatyper som strängar och tal men det är inte alltid tal och strängar räcker för att beskriva ett problem på ett bra sätt. Abstrakta datatyper (ADT) är ett sätt att beskriva sådana data som annars inte kan beskrivas med de datatyper som redan finns i språket. Ett spelkort har till exempel två attribut som krävs för att representera kortet (färg/suit och valör/value). När man hanterar ett sådant spelkort kan man låta en sammansatt datatyp såsom lista, dictionary eller en tupel representera kortet. Utan funktioner som tydligt förmedlar att man hanterar ett spelkort och inte vilken lista eller tupel som helst kan det dock bli svårt att komma ihåg hur man representerade kort när man står i begrepp att skapa nya vid ett senare tillfälle. För andra programmerare kan det dessutom bli svårt att läsa ens program. Därför är det viktigt att skapa en uppsättning funktioner som låter en manipulera och visa spelkort.

Vanligen definierar man en abstrakt datatyp genom funktioner för att skapa, modifiera, extrahera data ur och visa datatypen. Finns dessa fyra funktioner är det möjligt att arbeta med er datatyp och utöka den allt eftersom ert program kräver det. Det är också bra att ha funktioner som kan verifiera att datan i er nya datatyp är korrekt, men det är inget krav för att kunna arbeta med datatypen. Som övning inför den här laborationen ska ni skapa två datatyper: spelkort (card) och kortlek (deck). Nedan anges körexempel på hur datatyperna hanteras.

Körexempel:

three_of_spades = create_card(3, 2)
print(get_value(three_of_spades))
3
print(get_suit(three_of_spades))
2
display_card(three_of_spades)
3 of Spades
card = create_card(13, 2)
display_card(card)
13 of Spades

Eftersom ett spelkort är oföränderligt i verkligheten skapar ni inte funktioner för att modifiera det. När ni däremot ska skapa funktioner för att modellera en hel kortlek kommer ni behöva funktioner för att skapa en lek eftersom en kortlek inte alltid behöver innehålla alla spelkort och ordningen på spelkorten kan spela roll beroende på sammanhang. Nedan visas exempel på funktioner för att skapa och extrahera data ur en kortlek. Behövs det fler för att modellera en kortlek? Implementera funktionerna i körexemplet och tänk på huruvida fler funktioner skulle kunna vara användbara när ni implementera algoritmerna i inlämningsuppgifterna.

Körexempel:

deck = create_deck()
print(deck)
['deck', [(1, 1),(2, 1), ...]]
print(pick_card(deck))
(1, 1)
three_of_spades = create_card(3, 2)
deck = insert_card(three_of_spades, deck)
print(deck)
['deck', [(3, 2),(1, 1),(2, 1), ...]]

Tips och tankar runt ADT

Nedan följer lite tips på hur man kan tänka runt och veta om man gör rätt när man programmerar med ADT som verktyg. Läs gärna igenom laborationsinstruktionen för ADT-labben innan du läser delen nedan. Alternativt kan du läsa detta nu och titta på det igen när du läst igenom laborationsinstruktionen.

I de laborationer som kräver en abstrakt datatyp är det viktigt att ha förståelse för vad det faktiskt innebär. Annars kan det resultera i mycket arbete som senare behöver justeras. En rekommendation är att alltid börja med att skriva dina ADT-funktioner för att sedan diskutera dem med en assistent.

Det kan underlätta att lösa ADT-laborationerna genom att föreställa dig att du har två olika roller under arbetet, ADT-programmerare samt problemlösare. Det är starkt rekommenderat att du använder dig av två filer, en för ADT och en för själva laborationen för att underlätta för dig själv:

ADT-programmeraren

Som ADT-programmerare bestämmer du hur din datatyp ska representeras och vilka ADT-funktioner som är lämpliga att implementera. Här är det bra att reflektera över vilka problem som ska kunna lösas av din ADT. Tänk på att din ADT representerar en datatyp som kommer användas som en del av problemlösningen senare. Det innebär att din ADT inte behöver lösa hela problemet i exempelvis en laboration. Läs avsnittet "När blir en ADT-funktion för specifik" innan du påbörjar implementationen.

Du kanske vill representera en klass på ett av Universitetets program för att kunna sätta betyg på studenter? Kanske skulle följande ADT-funktioner vara lämpliga då:

#Skapar en skolklass m.h.a. en lista av namn
def create_class(list_of_names):
    class_list = []
    for name in list_of_names:
        class_list.append([name, 0])
    return class_list

#Hämta en student m.h.a. klasslistan och studentens namn
def get_student(class_list, name):
    for student in class_list:
        if name in student:
            return student

#Ändra ett betyg m.h.a. en klasslista, en student och ett nytt betyg
def change_grade(class_list, student, grade):
    idx = class_list.index(student)
    student[1] = grade
    class_list[idx] = student

Problemlösar-programmeraren

Problemlösaren tar hjälp av ADT-funktioner för att lösa uppgifter. I denna roll får du aldrig (och ska inte behöva) veta exakt hur den abstrakta datatypen är implementerad "bakom kulisserna". Föreställ dig att den enda information du har i denna roll är en lista av ADT-funktioner du kan använda, samt vad dessa returnerar och tar in för argument.

Tänk dig listor i Python som en ADT. Datatypen lista har tillhörande funktionalitet för att kunna manipulera datatypen:

• Konstruktorer: my_list = []
• Selektorer: my_list[0]
• Iteratorer: for element in my_list:
• Modifikatorer: my_list.pop()

Användaren av funktionerna behöver inte se hur datatypens modifikatorer fungerar. Vi vet vad resultatet blir när vi använder exempelvis pop() eller insert(), men behöver inte bry oss om vad som sker i bakgrunden. Samma tankesätt kan appliceras när vi använder våra egna ADT-funktioner.

• Konstruktorer: my_class = create_class(list_of_students)
• Selektorer: student = get_student(my_class, "Anders Andersson")
• Iteratorer: print_grades(my_class)
• Modifikatorer: change_grade(my_class, student, 5)

Som du ser kan dessa funktioner användas utan att vi vet exakt hur ADTn är representerad. Vi tar till exempel emot en lista av namn vid anrop av konstruktorn och får ut en skolklass som vi sparar in i my_class. Men eftersom denna variabel bara kommer användas för att anropa andra ADT-funktioner har den interna representationen ingen betydelse. Detta innebär i sin tur att om ADT-representationen ändras ska problemlösarprogrammet vi skrivit fortfarande fungera på samma sätt. Vi kan ändra det tidigare kodexemplet för att visa detta.

def create_class(list_of_names):
    class_dict = {}
    for name in list_of_names:
        class_dict[name] = 0
    return class_dict

def get_student(class_dict, name):
    return (name, class_dict[name])

def change_grade(class_dict, student, grade):
    class_dict[student[0]] = grade

Här väljer i stället ADT-programmeraren att representera klassen som en dictionary. Anropen till funktionerna fungerar dock på samma sätt som tidigare, vilket leder till att följande exempel fortfarande fungerar och ger samma resultat.

my_class = create_class(list_of_students)
student = get_student(my_class, "Anders Andersson")
change_grade(my_class, student, 5)

När blir en ADT-funktion för specifik?

Det kan vara svårt att sätta en specifik gräns gällande detta, och det är även beroende av vad ADTn representerar. Som tumregel kan du tänka att ADT-funktionen ska vara användbar om din ADT används i ett annat syfte. Som exempel kan vi ta en titt på punkt 2 i algoritmen för solitaire keystream i lab 3.

"Flytta joker A ner ett steg i kortleken. Ifall jokern redan är längst ner i kortleken flyttas den under det översta kortet."

Det kan kännas självklart att skapa en funktion i stil med "move_joker_a()" för att utföra denna uppgift. Funktionen är absolut bra att ha för att dela upp koden och göra den lättläst, men är denna funktion lämplig som ADT-funktion? Fundera över tumregeln igen. Om denna ADT användes för att spela ett kortspel inser man att funktionen "move_joker_a()" är alldeles för specifik för denna uppgift och vi kommer troligtvis inte ha någon användning för den i andra applikationer. Lös i stället denna uppgift (i din roll som problemlösare) med hjälp av mer generella ADT-funktioner. Kanske på följande vis:

def move_joker_a(deck):
    index = get_index(deck, "JokerA")
    if index == nr_of_cards(deck)-1:
        index = 1
    else:
        index += 1
    move_card(deck, "JokerA", index)

För ett annat exempel på en för specifik ADT-funktion kan du reflektera över det tidigare exemplet med pythonlistor som ADT. Om vi exempelvis skulle vilja ta elementet på index 5 i en lista och placera det på index 0, kan vi inte förvänta oss att det finns en funktion i stil med "remove_fifth_element_and_insert_at_index_zero()". Detta är alldeles för specifikt problem för att datatypen list ska lösa det. Men som tur är har listor generella "ADT-funktioner", vilket gör att vi kan lösa uppgiften på följande sätt:

elem = my_list.pop(5)
my_list.insert(0, elem)

Ett annat exempel på detta som specifikt berör ADT-laborationen är när vi ska göra en specifik kuppering av kortleken. Kortleken ska i laborationen delas i 3 delar (A, B och C) beroende på var jokrarna finns i leken. Sedan ska delarna sättas ihop i ordningen C, B och A. Detta kanske känns som att man måste ha en specifik ADT-funktion för. Men det är inte en särskilt användbar funktion utanför det här specifika problemet. Då kanske det istället är lämpligt att skapa ADT-funktioner som problemlösaren kan använda för att lösa delproblem av detta hela problem. Har vi exempelvis möjlighet att hitta index för ett godtyckligt kort kan vi hitta var jokrarna befinner sig i kortleken. Kan vi sedan dela kortleken med hjälp av index och slå ihop flera kortlekar till en så finns alla nödvändiga verktyg för att lösa problemet.

Hur vet jag om jag bryter mot "ADT-reglerna"?

För att avgöra detta är det som tidigare nämnt till stor fördel att använda två separata filer varav en innehåller din ADT och den andra filen innehåller lösningen på laborationen. Om du i din "problemlösarfil" någonstans kan se hur din ADT är representerad så har du brutit mot designmönstret. Några exempel på sätt att hantera en kortlek som bryter eller inte bryter mot ADT trots att de i slutänden kan kännas som att de gör samma sak:

deck.sort()

Funktionen sort() är specifik för listor, vilket innebär att du måste veta att kortleken representeras av en lista. Detta är alltså ett brott mot ADT'n deck.

sort_deck(deck)

Där sort_deck är en ADT-funktion som vi endast anropar och skickar med kortleken som argument. Här behöver vi som problemlösaren inte veta något om den interna representationen, detta är alltså inte ett brott mot ADT'n deck.

deck[0]

Eftersom [0] är direktåtkomst för index i listor med mera skulle detta likt exemplet ovan också avslöja ADTns interna representation.

get_card_at_index(deck, 0)

Här behöver vi som problemlösare inte veta något om den interna representationen.