Generizität

Generzität :

Algorithmen 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

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
 return k

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

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

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 Seninel 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)

2. Navigation in der Quelldatenstruktur(Iteratoren) 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 

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)

Was tut Python bei " for k in quelle":

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, 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 = -1111111111111111
   while not l isSentinel:
        m = max(m, l.data)                    # max ist eingebaute Funkion in Python
        l =l.next

Zur Verallgemeinerung werden Funktoren eingerichtet:

• 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, intial):
      for k in iterator
            initial = functor(initial, k)
   return initial

Statt maxList:

m = doSomethingGeneric(max,list -11111111111)  

Statt sumArray :

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

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 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__() 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(nex(k))

• Container : Sequence # Array

Mathematische Konzepte :

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

Ein offered Interface is mehr als ein required Interface.