Upload
others
View
2
Download
0
Embed Size (px)
Citation preview
Diskrete Modellierung
Wintersemester 2018/19
Martin Mundhenk
Uni Jena, Institut fur Informatik
13. November 2018
3.3 Entwurf von Datentypen
Durch das Erzeugen von Datentypen
entwickelt der Programmierer eine eigene Sprache,
mit der uber die Daten”gesprochen“ werden kann.
Deshalb muss man beim Entwickeln einer Idee fur ein Programm das Ziel haben, die benotigten
Datentypen zu verstehen und zu designen.
In dieser Vorlesung werden wir (nochmal) betrachten, welche Moglichkeiten man hat, und wie man
beim Design einerseits die Implementierung des Datentyps und andererseits dessen Benutzung im
Auge behalten muss.
Dazu werden wir ein paar Beispiele sehen.
3.3.1
Einschub: Der eingebaute Datentyp set
Teil der API:
Operation Beschreibungset( ) eine neue leere Menge
s.add(item) fuge item zur Menge s hinzu (falls es nicht bereits in s ist)
item in s ist item in der Menge s (kann nur gelesen werden)
s.remove(item) entferne item aus der Menge s
for elem in s: Iteration uber die Elemente der Menge s
s.intersection(t) die Schnittmenge der Mengen s und t
s.union(t) die Vereinigungsmenge der Mengen s und t
Der Datentyp set ist ahnlich wie list (Array), jedoch enthalt set die Eintrage ungeordnet.Der Test item in s und die Operation s.remove(item) gehen deshalb schneller als bei list.
3.3.2
Gleichheit von Referenzen is
Die Operatoren is bzw. is not prufen, ob zwei Referenzen gleich sind.
>>> a = [1,2]
>>> b = [1,2]
>>> c = a
>>> a is b
False
>>> a is c
True
>>> d = (1,2)
>>> a is d
False
is und is not sind auf alle Datentypen anwendbar.
3.3.3
Gleichheit der Werte des Objekts: ==
kann auf Objekte mit Wert vom gleichen Datentyp angewendet werden.Es kann durch die spezielle Methode eq () definiert werden.Ist sie nicht definiert, dann ersetzt Python es durch is .
class Charge1:
def __init__(self, x0, y0, q0):
self._xkoord = x0
self._ykoord = y0
self._ladung = q0
# test.py benutzt Charge1
c1 = Charge1(1,2,3)
c2 = Charge1(1,2,3)
print(c1==c2)
# test.py
# False
class Charge2:
def __init__(self, x0, y0, q0):
...
def __eq__(self,other):
if self._xkoord != other._xkoord: return False
if self._ykoord != other._ykoord: return False
if self._ladung != other._ladung: return False
return True
# test.py benutzt Charge2
c1 = Charge2(1,2,3)
c2 = Charge2(1,2,3)
print(c1==c2)
# test.py
# True
3.3.4
3.3.5
Spezielle Methoden fur weitere Vergleichsperatoren
3.3.6
Wenn eine Klasse den Vergleichsoperator < (spezielle Methode __lt__) implementiert,konnen Arrays aus Instanzen der Klasse mit Python’s sort sortiert werden.
from vector import Vector
import random
#----------------------------------------------------------
# oVector erweitert Vector um den <-Vergleich.
class oVector(Vector):
def __lt__(self, other): return self*self<other*other
#------------------------------------------------------------
# Erzeuge ein Array a aus 10 zufallig gewahlten 2-dimens.
# oVector-Instanzen und gib sie aus.
a = []
for i in range(10):
a += [oVector((random.randint(1,10), random.randint(1,10)))]
print('Vor dem Sortieren:')
for i in range(len(a)): print(str(a[i]), a[i]*a[i])
# Sortiere das Array a (entsprechend dem <-Vergleich von oVector)
# und gib es aus.
a.sort()
print('Nach dem Sortieren:')
for i in range(len(a)): print(str(a[i]), a[i]*a[i])
python ordnung.py
Vor dem Sortieren:
('(8, 9)', 145)
('(2, 2)', 8)
('(6, 7)', 85)
('(9, 10)', 181)
('(10, 2)', 104)
('(5, 1)', 26)
('(6, 2)', 40)
('(6, 9)', 117)
('(1, 3)', 10)
('(3, 8)', 73)
Nach dem Sortieren:
('(2, 2)', 8)
('(1, 3)', 10)
('(5, 1)', 26)
('(6, 2)', 40)
('(3, 8)', 73)
('(6, 7)', 85)
('(10, 2)', 104)
('(6, 9)', 117)
('(8, 9)', 145)
('(9, 10)', 181)3.3.7
Vererbung
Python unterstutzt die Definition von Beziehungen zwischen Klassen.
Man kann (neue) Klassen als Unterklassen bereits definierter (Ober-)Klassen definieren. Die Unterklassenerben Instanzen-Variablen und Methoden ihrer Oberklassen.
Dieses Konzept ist sehr umfangreich und wir begnugen uns
mit einem kleinen (Bruch und gBruch) Beispiel
und einem etwas großeren (Spielstein, Abprallen, Durchlaufen, . . . ) Beispiel.
3.3.8
class Bruch:
# Klasse fur ungekurzte rationale Zahlen
def __init__(self, zaehler, nenner):
self._z = zaehler
self._n = nenner
def __add__(self,other):
return Bruch(self._z*other._n + other._z*self._n,
self._n*other._n)
def __str__(self):
return str(self._z) + " / " + str(self._n)
# bruchtest.py benutzt Bruch und gBruch
a = Bruch(27,6)
print(a)
a = gBruch(27,6)
print(a)
print(gBruch(3,4) + gBruch(1,4))
# python bruchtest.py
# 27 / 6
# 9 / 2
# 1 / 1
class gBruch(Bruch):
# Unterklasse von Bruch fur gekurzte Bruche
def __init__(self, zaehler, nenner):
self._z = zaehler
self._n = nenner
# Bruch.__init__(self, zaehler, nenner) # geht auch ...
self._kuerzen()
def _ggT(self):
(a, b) = (self._z, self._n)
while a%b != 0: (a,b) = (b,a%b)
return b
def _kuerzen(self):
g = self._ggT()
self._z = self._z / g
self._n = self._n / g
def __add__(self, other):
return gBruch(self._z*other._n + other._z*self._n, self._n*other._n)
def __str__(self):
return Bruch.__str__(self)
3.3.9
Abschlussbeispiel
Wir wollen eine Art Billard-Spiel implementieren.
Wie die Kugeln beim Billard sausen Spielsteine uber ein
Spielfeld.
Wenn sie zusammenstoßen, andern sie Richtung und Tempo.
Wenn sie am Rand anstoßen,
prallen sie ab oder kommen an der anderen Seite wieder raus.
Außerdem konnen sie dabei auch ihr Tempo andern.
Wenn sie zu schnell oder zu langsam werden,
kann ihr Tempo geandert werden.
3.3.10
Abschlussbeispiel
Wir wollen eine Art Billard-Spiel implementieren.
Wie die Kugeln beim Billard sausen Spielsteine uber ein
Spielfeld.
Wenn sie zusammenstoßen, andern sie Richtung und Tempo.
Wenn sie am Rand anstoßen,
prallen sie ab oder kommen an der anderen Seite wieder raus.
Außerdem konnen sie dabei auch ihr Tempo andern.
Wenn sie zu schnell oder zu langsam werden,
kann ihr Tempo geandert werden.
3.3.10
Die Struktur der Klassen: die Basis-Klasse Spielstein
class Spielstein
implementiert alle Eigenschaften, die alle Spielsteine gemeinsam haben.
Instanz-Variablen: _position x- und y -Koordinate (Vector) (-1. . . +1,-1 . . . +1)_richtung Vector (normalisiert auf Lange 1)_geschwindigkeit float 0.05. . . 0.1_farbe
_groesse
Methoden: __init__ erzeuge neuen Spielstein mit zufallig gewahlten Instanz-Werten
testeZusammenstoss testet, ob der Spielstein mit einem anderen zusammenstoßt
schritt macht einen Schritt mit dem Spielstein
neueBewegungZwischenspeichern speichert neue Bewegungswerte des Spielsteins
bewegungAktualisieren speichert die neuen Bew.werte in die Instanz-Variablen
anstossLiRe testet, ob der Spielstein am linken oder rechten Rand anstoßt
anstossObUn testet, ob der Spielstein am oberen oder unteren Rand anstoßt
_x, _y, _dx, _dy gibt Koordinaten der Position und der Richtung zuruck3.3.11
Ein Ausschnitt aus der Implementierung.
class Spielstein:
# Ein neuer Spielstein.
def __init__(self, farbe):
....
# testeZusammenstoss( ) erhalt als Argument einen Spielstein kb
# und gibt zuruck, ob dieser Spielstein mit Spielstein kb zusammenstoßt.
def testeZusammenstoss(self, kb):
return abs(self._position-kb._position) < self._groesse + kb._groesse
# schritt( ) andert die Position dieses Spielsteins entsprechend Richtung und Geschwindigkeit
def schritt( self ):
if self.randAnstoss(): self.tempowechsel()
# Falls dieser Spielstein zu schnell/zu langsam wird, dann wird er abgebremst/beschleunigt.
self.abbremsen()
# Setze diesen Spielstein auf seine neue Position.
self._position = self._position + self._richtung.skalar(self._geschwindigkeit)
Die Instanz-Methoden randAnstoss, tempowechsel und abbremsen
sind nicht in der Klasse Spielstein implementiert,sondern werden in Unterklassen von Spielstein implementiert.
3.3.12
Klassen fur Rand-Abprall-Eigenschaften
Die beiden folgenden Klassen sind Unterklassen von Spielstein
und implementieren die Methode randAnstoss mit unterschiedlichem Effekt.
class Abprallen(Spielstein)
Methode: randAnstoss lasst den Spielstein am Rand abprallen
class Durchlaufen(Spielstein)
Methode: randAnstoss lasst den Spielstein am Rand verschwinden und an der anderenSeite wieder herauskommen
Die Methode randAnstoss wird in Methode schritt der Oberklasse Spielstein aufgerufen.Bei der Implementierung einer Klasse fur einen bestimmten Spielsteinmuss eine dieser beiden Klassen als Oberklasse gewahlt werden.Damit wird die Eigenschaft des Spielsteins festgelegt.
3.3.13
class Abprallen(Spielstein):
# randAnstoss() andert den Richtungs-Vektor des Spielsteins, falls er an eine Seite des Feldes stoßt.
# Die Anderung des Richtungs-Vektors entspricht einem Abprallen (Einfallswinkel=Ausfallswikel).
# Beim Anstoßen an den Rand ist der Ruckgabewert True, anderenfalls False.
def randAnstoss(self):
# Falls der Spielstein an die rechte oder linke Seite des Feldes stoßt, dann andert er seine x-Richtung.
if self.anstossLiRe(): self._richtung = Vector((-self._dx(),self._dy()))
# Falls der Spielstein an die untere oder obere Seite stoßt, dann andert er seine y-Richtung.
elif self.anstossObUn(): self._richtung = Vector((self._dx(),-self._dy()))
else: return False
return True
class Durchlaufen(Spielstein):
# randAnstoss() andert die Koordinaten des Spielsteins, falls er an eine Seite des Feldes stoßt.
# Er kommt dann an der gegenuberliegenden Seite wieder ins Feld.
# In dem Fall ist der Ruckgabewert True, anderenfalls False.
def randAnstoss(self):
# Falls der Spielstein an die rechte oder linke Seite des Feldes stoßt,
# kommt er an der linken bzw. rechten Seite wieder ins Feld.
if self.anstossLiRe(): self._position = Vector((-self._x(),self._y()))
# Falls der Spielstein an die untere oder obere Seite des Feldes stoßt,
# kommt er an der oberen bzw. unteren Seite wieder ins Feld.
elif self.anstossObUn(): self._position = Vector((self._x(),-self._y()))
else: return False
return True3.3.14
Klassen fur Tempo-Anderungen beim Rand-Anstoß
Die drei folgenden Klassen sind Unterklassen von Spielstein
und implementieren unterschiedliche Tempo-Anderungen des Spielsteins tempowechsel.
class Schneller(Spielstein)
Methode: tempowechsel erhoht die Geschwindigkeit des Spielsteins um 5%
class Langsamer(Spielstein)
Methode: tempowechsel verringert die Geschwindigkeit des Spielsteins um 5%
class Gleichschnell(Spielstein)
Methode: tempowechsel lasst die Geschwindigkeit des Spielsteins unverandert
Die Methode tempowechsel wird in Methode schritt der Oberklasse Spielstein aufgerufen.Bei der Implementierung einer Klasse fur einen bestimmten Spielsteinmuss eine dieser Klassen als Oberklasse gewahlt werden. Damit wird die Eigenschaft desSpielsteins festgelegt.
3.3.15
class Schneller(Spielstein):
def tempowechsel(self):
self._geschwindigkeit *= 1.05
class Langsamer(Spielstein):
def tempowechsel(self):
self._geschwindigkeit *= 0.95
class Gleichschnell(Spielstein):
def tempowechsel(self): return
3.3.16
Klassen fur Abbrems-Eigenschaften
Die beiden folgenden Klassen sind Unterklassen von Spielstein
und implementieren die Methode abbremsen mit unterschiedlichem Effekt.
class Abgebremst(Spielstein)
Methode: abbremsen verringert die Geschwindigkeit des Spielstein, wenn er zu schnell wirdund erhoht die Geschwindigkeit des Spielstein, wenn er zu langsam wird
class Ungebremst(Spielstein)
Methode: abbremsen lasst die Geschwindigkeit des Spielstein unverandert
Die Methode abbremsen wird in Methode schritt der Oberklasse Spielstein aufgerufen.Bei der Implementierung einer Klasse fur einen bestimmten Spielsteinmuss eine dieser beiden Klassen als Oberklasse gewahlt werden.Damit wird die Eigenschaft des Spielsteins festgelegt.
3.3.17
class Abgebremst(Spielstein):
# Falls der Spielstein zu schnell wird, dann wird er abgebremst.
def abbremsen( self ):
if abs(self._geschwindigkeit)>0.3:
self._geschwindigkeit /= 5
elif abs(self._geschwindigkeit)<0.06:
self._geschwindigkeit *= 5
class Ungebremst(Spielstein):
# Der Spielstein wird nicht abgebremst.
def abbremsen( self ): return
3.3.18
Klassen fur Spielsteine
Die folgenden Klassen sind Unterklassen der o.g. Unterklassen von Spielstein.Sie implementieren die Methode male zur graphischen Darstellung des Spielsteinsund wahlen weitere Eigenschaften des Spielstein aus o.g. Unterklassen.
class Kreis(Abprallen, Langsamer, Abgebremst)
Methode: male malt den Spielstein als Kreis
class Quadrat(Abprallen, Schneller, Abgebremst)
Methode: male malt den Spielstein als Quadrat
class Dreieck(Durchlaufen, Gleichschnell, Ungebremst)
Methode: male malt den Spielstein als Dreieck
Bei der Klassen-Definition wird durch die Angabe der Oberklassen festgelegt, welche (weiteren)Eigenschaften der Spielstein hat.
3.3.19
class Kreis(Abprallen, Langsamer, Abgebremst):
# male( ) malt den Spielstein als Kreis auf die Leinwand von stddraw.
def male( self ):
stddraw.setPenColor(self._farbe)
stddraw.filledCircle(self._x(), self._y(), self._groesse)
class Quadrat(Abprallen, Schneller, Abgebremst):
# male( ) malt den Spielstein als Quadrat auf die Leinwand von stddraw.
def male( self ):
stddraw.setPenColor(self._farbe)
stddraw.filledSquare(self._x(), self._y(), self._groesse)
class Dreieck(Durchlaufen, Gleichschnell, Ungebremst):
# male( ) malt den Spielstein als Dreieck auf die Leinwand von stddraw.
def male( self ):
stddraw.setPenColor(self._farbe)
x = [self._x(), self._x()-self._groesse*0.3, self._x()+self._groesse*0.3]
y = [self._y()+self._groesse, self._y()-self._groesse*0.3, self._y()-self._groesse*0.3]
stddraw.filledPolygon(x, y)
3.3.20
Die Klasse fur das Spielfeld
class Spielfeld
implementiert ein Spielfeld mit Spielsteinen,
beobachtet Zusammenstoße von Spielsteinen
und lasst die Spielsteine einen Schritt laufen.
Instanz-Variablen: _alleSpielsteine ein set aus den Spielsteinen, die auf dem Spielfeld sind
Methoden: __init__ erzeugt ein neues Spielfeld mit n zufallig gewahlten Spielsteinen
zusammenstoesse kontrolliert fur jeden Spielstein, ob er mit anderen zusammenstoßt,und andert seine Bewegung entsprechend
aktualisiere lasst alle Spielsteine einen Schritt laufen
male malt alle Spielsteine auf die Leinwand von stddraw
3.3.21
Das Hauptprogramm.
# Erzeuge ein Spielfeld mit sovielen Spielsteinen, wie auf der Kommandozeile angegeben ist.
F = Spielfeld( int(sys.argv[1]) )
# Setze die Leinwandgroße, und setze die x- und y-Skala der Leinwand auf -1..+1 .
stddraw.setCanvasSize(800,800)
stddraw.setXscale(-1.0, 1.0)
stddraw.setYscale(-1.0, 1.0)
# Die Spielsteine werden auf der Leinwand 10000 Schritte bewegt.
n = 0
while n<1000:
n += 1
F.aktualisiere( )
F.male( )
stddraw.show()
3.3.22
Zusammenfassung
Jede Programmiersprache bietet (andere) Moglichkeiten zum Entwurf von Datentypen.
Wir haben verschiedene Prinzipien gesehen, die stets beachtet werden sollten.
Beim Entwurf eines modularen Programms werden die Aufgaben,
die das Programm losen sollen, in Einzelteile zerlegt.
Beim Entwurf von Datentypen werden die Daten, mit denen das Programm arbeiten soll, und die
typische Benutzung der Daten zusammengesetzt.
Diese beiden unterschiedlichen Aufgaben mussen beim Programmieren zusammen gelost werden.
3.3.23