Generizität: Difference between revisions
Line 173: | Line 173: | ||
'''Verallgemeinerung auf Funktionen die " etwas tun":''' | '''Verallgemeinerung auf Funktionen die " etwas tun":''' | ||
def sumArray(a): | |||
s = 0 | s = 0 | ||
for k in a : | for k in a : | ||
s+=a # s = add(s,k) | s += a # s = add(s,k) | ||
return | return a | ||
def maxList(l): | def maxList(l): | ||
m = -1111111111111111 | m = -1111111111111111 | ||
while not l isSentinel: | while not l.isSentinel: | ||
m = max(m, l.data) # max ist eingebaute Funkion in Python | m = max(m, l.data) # max ist eingebaute Funkion in Python | ||
l =l.next | l =l.next | ||
return m | |||
''' | ''' Verallgemeinerung durch Funktoren :''' | ||
*Funktor muss "callable" sein : falls f Funktor ist, funktioniert v = f(a1, a2,...) | *Funktor muss "callable" sein : falls f Funktor ist, funktioniert v = f(a1, a2,...) | ||
Line 193: | Line 194: | ||
def doSomethingGeneric(functor,iterator, | def doSomethingGeneric(functor,iterator, initial): | ||
for k in iterator | for k in iterator | ||
initial = functor(initial, k) | initial = functor(initial, k) | ||
Line 200: | Line 201: | ||
'''Statt maxList:''' | '''Statt maxList:''' | ||
m = doSomethingGeneric(max,list - | m = doSomethingGeneric(max,list, -1111111111111111) | ||
Line 206: | Line 207: | ||
def add(x,y): return x + y | def add(x,y): return x + y | ||
s = doSomethingGeneric(add, array, | s = doSomethingGeneric(add, array, 0) | ||
'''Statt genericCopy :''' | '''Statt genericCopy :''' | ||
Line 213: | Line 214: | ||
x.append(y) | x.append(y) | ||
return x | return x | ||
array4 = | array4 = doSomeThingGeneric(append, array, []) | ||
'''doSomethingGeneric''' | '''doSomethingGeneric''' gibt es in vielen Programmiersprachen : | ||
*in Python : reduce | *in Python : reduce |
Revision as of 20:33, 18 June 2008
Ziel von generischer Programmierung ist es, Algorithmen und Datenstrukturen so zu entwerfen und zu implementieren, dass sie möglichst vielvältig verwendbar sind.
Gemeint sind :
- verschiedene Anwendungen
- mit vielen Kombinationsmöglichkeiten
- als wiederverwendbare Bibliothek
--> ohne Neuimplemenation
- Code austauschen in Bibliotheken
Beispiel :
Kopieren eines Containers
def copyArray(a): r =[] for k in a r.append(k) return k
class Node : def__init__(self, data, next) self.data = data self.next = next
def copyArrayToList(a) : if len(a) == 0 : return None first = last = Node (a[0], None) for k in a[1:] : last.next = Node(k, None) last = last.next return first
def copyListToArray(l): r = [] while l is not in None : r.append(l.data) l = l.next return r
Beobachtung :
Für N Datenstrukuren ist der Implementaionsaufwand <math>O({N}^2 )</math>. Alle Funktionen machen das gleiche mit uninteressantem Unterschied
Verbesserung durch Verallgemeinerung zweier Aspekte :
- Navigieren durch die Quelldaten
- Aufbauen der Zieldatenstruktur
Vereinheitlichung der Zieldatenstruktur :
- standardisierte Funktion "append"
- Array hat sie schon
- Liste : definiere Klasse DoublyLinkedList
class SentinelTag : pass # keine Daten class DoublyLinkedNode: def__init__(self,data = sentinelTag(), next = None) self.data = data if next is None : self.prev = self.next = self else: self.next = next self.prev = next.prev next.prev.next = self next.prev = self
def isSentinel(self) : return isinstance(self.data, sentinelTag)
class DoublyLinkedList : # Realisiert doppelt verbundene kreisförmige Kette mit Sentinel # als "Anker" def__init__(self): self.sentinel = DoublyLinkedNode() self.size = 0 def__len__(self): return self.size #len(l) def append(self, value): DoublyLinkedNode(value, self.sentinel) self.size += size def__iter__(self): return ListIterator(self.sentinel.next) def reverseIterator(self): return ListIterator(self.sentinel.prev)
def genericCopy(quelle, ziele) :
for k in quelle : ziel.append(k) return ziel
liste = genericCopy(array, DoublyLinkedList()) # Statt copyArrayToList array2 = genericCopy(array,[]) # Statt copyArray array3 = genericCopy(liste,[]) # Statt copyListToArray
Iteratoren
Navigation in der Quelldatenstruktur (Iteratoren) soll
für alle Datenstrukturen funktionieren
- Objekt, das auf ein Element des Containers zeigt
- Zum nächsten Element weiter rücken kann
- anzeigt, wenn das Ende der Sequenz erreicht ist
class ListIterator: def__init__(self, node): self.node = node def next(self): if self.node.isSentinel(): raise StopIteration() #Python Konvention v = self.node.data self.node = self.node.next # zeigt Ende der Sequenz return v # Pythonkonvention, gebe vorigen Wert zurück
def__iter__(self): return ListIterator(self.node) # Pythonkonvention, Kopie des Iterators zurückgeben
besser stattdessen :
return self.__class__(self.node) # ist allgemeiner
Was tut Python bei " for k in quelle"(in gernericCopy)?:
iter = quelle.__iter__() try : while True : k = iter.next() ... # Schleifeninhalt except StopIteration: pass
Rückwärts kopieren :
class ReverseListIterator(ListIterator) def next(self): if self.node.isSentinel(): raise StopIteration() v = self.node.data self.node = self.node.prev return v
revArray = genericCopy(list.reverseIterator(), []), revList = genericCopy(reversed(array), DoublyLinkedList())
Funktoren
Verallgemeinerung auf Funktionen die " etwas tun":
def sumArray(a): s = 0 for k in a : s += a # s = add(s,k) return a
def maxList(l): m = -1111111111111111 while not l.isSentinel: m = max(m, l.data) # max ist eingebaute Funkion in Python l =l.next return m
Verallgemeinerung durch Funktoren :
- Funktor muss "callable" sein : falls f Funktor ist, funktioniert v = f(a1, a2,...)
- Funktion, oder Objekt bei dem die Funktion __call___ definiert ist.
def doSomethingGeneric(functor,iterator, initial): for k in iterator initial = functor(initial, k) return initial
Statt maxList:
m = doSomethingGeneric(max,list, -1111111111111111)
Statt sumArray :
def add(x,y): return x + y s = doSomethingGeneric(add, array, 0)
Statt genericCopy :
def append(x,y): x.append(y) return x array4 = doSomeThingGeneric(append, array, [])
doSomethingGeneric gibt es in vielen Programmiersprachen :
- in Python : reduce
- in C++ : accumulate
...funktionale Sprachen (Lisp, Haskell...)
verwandte generische Funktionen
map:
[x1, x2,...] --> [f(x1),f(x2),...] # Funktor mit einem Argument
Offered Interface versus Required Interface
Interface:
- standardisierte Schnittstelle zwischen Algorithmen und Datenstruktur
Offered Interface:
- Funktionalität, die eine Datenstruktur anbietet.
- Die Datensruktur sollte möglichst vielseitig sein.
z.B. PythonList:
- dynamisches Array
- stack
- deque
- linkedList
- standardisiert durch abstrakte Datentypen
Required Interface:
- Funktionalität, die Algorithmus benutzt
- das required Interface ist meist weniger als das offered Interface
z.B.:
RI lesender Zugriff
OI lesender Zugriff , schreibender Zugriff Konstruktor remove...
- standardisiert über Konzepte
- ADT sind Sammlungen zusammengehörender Konzepte
- RI sollten minimal sein
Konzepte ( + Hierarchie)
- copy Constructible ( P: copy.deepcopy)
- Default Constructible (v1 = v.__class__() ist aufrufbar ) # DoublylinkedNode
- EqualityComparable('=='), LessThanComparable('<')
- ThreeWayComparable(__cmp__ ist aufrufbar)
- Indexable("a[k]", k ist Integer)
- Mapping("a[key]", key ist arbitrary)
- Hashable(__hash__ für key)
- Iteratoren : Forward(next), BidirektionalIterator(next, prev), RandomAccessIterator(next(k))
- Container : Sequence # Array
Mathematische Konzepte :
Addable(__add__) Subtractable(__sub__) Multiplyable(__mul__) Dividable(__div__)
Ein offered Interface is mehr als ein required Interface.