Generizität

Generizität

-

Definition

Algorihmen 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
• Code austauschen in Bibliotheken

--> Dies soll ohne Neuimplemenation geschehen

1. Beispiel : Kopieren eines Containers

def copyArray(a):

r =[]

for k in a

r.append(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

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

Verbesserung durch Verallgemeinerung zweier Aspekt :

• Navigation durch die Quelldaten
• Aufbauen der Zieldatenstruktur

Wie kann man so zwischen einem Array und einer Liste navigieren, 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)