Generizität

Definition in der Informatik :

Algortihmen und Datenstrukturen so zu entwerfen und 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

1.Variante:

def copyArray(a):
  r =[]
  for k in a
  r.append(k)
return k

2.Variante:

class Node :
 def__init__(self,data,next)
    self.data = data
    self.next = next
 return k

3.Variante:

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

4.Variante:

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 uninteressanten Unterschied

Verbesserung durch Verallgemeinerung zweier Aspekte :

• Navigation durch die Quelldaten
• Aufbauen der Zieldatenstruktur

Wie kann man so zwischen einem Array und einer Liste navigieren, so dass man den Unterschied nicht mehr merkt?

--> 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)
    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 :
  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)
 def__iter__(self):
      return ListIterator(self.sentinel.next)

2. Navigation in der Quelldatenstruktur(Iteration) soll
für alle Datenstrukturen funktionieren

• Objekt, dass auf ein Element des Containers zeigt
• zum nächsten Element weiter rücken kann
• anzeigt, wenn das Ende der Sequenz erreicht ist

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 

was tun " for k in quelle":
iter = quelle__iter__()
 try :
    while True :
    k = iter.next()
    ...# Schleifeninhalt
    except StopIteration: pass

class ListIterator:
   def__init__(self, node):
       self.node = node
   def next(self):
       if self.node.isSentinel():
          raise StopIteraion()       #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 erzeugen

besser stattdessen :

     self__class__(self.node)

class ReverseListIterator(ListIterator)
  def next(self):
      if self.node isSentinel(): raise StopIteration()
      r = self.node.data
      self.node = self.node.prev
      return r

revarray = genericCopy(list, reverseIter()[]),
revlist = genericCopy(reversed(array), DoublyLinkedList())

Verallgemeinerung auf Funktionen die " etwas tun":

def sumArray(a):
        s = 0
        for k in a :
            s+=a       # s = add(s,k)
      return s 

def maxList(l):
   m = -1111111
   while l is not None [not l is Sentinel(l)]
        m = max(m, l.data)                    # max ist eingebaute Funkion in Python
        l =l.next

3.Funktoren

Zur Verallgemeinerung werden Funktoren eingerichtet:

• Funktor muss "callable" sein :

falls f Funktor: v = f(a1, a2) callable ist z.B. eine Funktion

• Objekt wo __call___ definiert

def doSomethingGeneric(functor, iterator, for k in iterator: intial):
   initial = functor(initial, k)
   return initial

m = doSomethingGeneric(max,list -1111111)
statt maxList

def add(x,y) return x+y
  s = doSomethingGeneric(add, array,o)
statt sumArray

def append(x,y):
     x.append(y)
   return x

array4 = doSomethingGeneric(append, array[])
Statt genericCopy

• doSomethingGeneric() gibt es in vielen Programmiersprachen

• • in Python : reduce in C++ : accumulate

verwandte generische Funkionen

map: [x1, x2,...] --> [f(x1),f(x2),...] alle funktionalen Sprachen ( Haskell,Lisp,...)

map ist in C++ "transform"

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 Algorihmus 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__() # DoublylinkedNode

• EqualityComparable('=='), LessThanComparable('<')

ThreeWayComparable(__cmp__)

• Indexable("a[k]")
• Mapping("a[key]")

• Iteratoren : Forward(next), BidirektionalIterator(next, prev), RandomAccessIterator(nex(k))

• Container : Sequence

Mathematische Konzepte :

Addable(__add__)
Subtractable(__sub__)
Multiplyable(__mul__)
Dividable(__div__)

Ein offered Interface is mehr als ein required Interface.