AuK/Konkrete Datenstrukturen/Stack
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Python</language>
Der Stack (Stapel) wurde als [[AuK/Abstrakte_Datentypen#Stack|abstrakter Datentyp]] charakterisiert. Hier werden nun verschiedene konkrete Datenstrukturen zur Implementation dieses ADT verwendet. Anschließend wird ein so implementierter Stack zur Umkehrung einer Liste natürlicher Zahlen verwendet und eine Effizienzbetrachtung angeschlossen.
Das in Python eingebaute Listen-`reverse` verwendet ein dynamisches Array. Es wird zu Beginn so groß dimensioniert, dass es für viele Anwendungsfälle ausreicht. Selbst wenn für `push` und `pop` jeweils ein konstanter Aufwand erforderlich ist, wird dieser durch die Schleife (Listenumkehr) "aufgefressen". Wie bei den anderen Implementierungen liegt der Aufwand zur Umkehrung einer Zahlenfolge in $\mathcal{O}(n)$, allerdings mit einem deutlich kleineren Faktor als bei den anderen konkreten Datentypen (Gerade mit geringerem Anstieg).
<code id="5f389802bf8ae">
## Implementation mit Python-Liste
# (veränderlich, unbeschränkt, Zugriff über Index und am Ende)
# Variante 1: append()/push(i) und pop(i): beide in O(1)
class Stack1:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
tos = self.items[len(self.items)-1]
self.items.pop()
return tos
def size(self):
return len(self.items)
</code>
<code id="5f389802bf931">
# Variante 2: insert(i)/push(i) und pop(i): beide in O(n), wobei n = Stack-size
# ineffizienter als Variante 1
class Stack2:
def __init__(self):
self.items = []
self.topIndex = 0
self.maxIndex = 400000
def isEmpty(self):
return self.topIndex <= 0
def push(self, item):
if self.topIndex <= self.maxIndex:
self.items.insert(self.topIndex, item)
self.topIndex = self.topIndex+1
else:
print("Stapel voll.")
def pop(self):
self.topIndex = self.topIndex-1
tos = self.items[self.topIndex]
self.items.pop(self.topIndex) # in O(n)
return tos
def size(self):
return self.topIndex
def __str__(self):
return "[" + (", ".join(map(str, self.items))) + "]"
</code>
<run id="5f389802bf9b3">
## Anwendung
st2 = Stack2()
st2.isEmpty()
st2.push(727)
st2.push(13)
st2.push(123)
st2.push(727)
st2.push(123)
print(st2)
</run>
<code id="5f371229e73b1">
### Variante 3: Stack-Impl. mittels einfach verketteter Liste
## Einfach verkettete Liste (singly linked list)
# Elemente der Liste sind Knoten (node),
# die einen Daten- und einen Referenzteil enthalten
class Node:
"""linked list"""
def __init__(self, data):
self.data = data
self.next = None
def getData(self):
return self.data
def setData(self, somedata):
self.data = somedata
def getNext(self):
return self.next
def setNext(self, somenext):
self.next = somenext
## first = Node(1)
## second = Node(2)
## first.next = second
## first.next.data
## first.getNext().getData()
class SinglyLinkedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def traverse(self):
def traversal(curNode):
if curNode is None:
print()
else:
print(curNode.getData())
traversal(curNode.getNext())
traversal(self.head)
def prepend(self, item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
def append(self, item):
curNode = self.head
while curNode.getNext() is not None:
curNode = curNode.getNext()
temp = Node(item)
curNode.setNext(temp)
def removeHead(self):
self.head = self.head.getNext()
# Stack3 verwendet den ADT "SinglyLinkedList"
class Stack3:
def __init__(self):
self.items = SinglyLinkedList()
def isEmpty(self):
return self.items.isEmpty()
def push(self, item):
self.items.prepend(item)
def pop(self):
tos = self.items.head.getData() # Durchgriff auf ADT "Node"
self.items.removeHead()
return tos
def size(self):
print('Sag ich nicht.')
</code>
<code id="5f371229e7417">
### GLEICHER Algorithmus über VERSCHIEDENEN konkreten Datentypen
## Anwendung mit Stack: Invertieren einer Liste
# Beispiel: myreverse([1, 2, [3, 4], 5]) = [5, [3, 4], 2, 1]
# from stack import Stack1, Stack2, Stack3
import timeit
import random
import matplotlib.pyplot as plt
def myreverse(ls):
s = Stack1() # Datenstruktur hier ändern (EINZIGER Eingriff) !!!!!!!!!!!!!!!!!!!!!
result = [] # Liste
for item in ls:
s.push(item)
while not(s.isEmpty()):
result.append(s.pop())
return result
## ls = [i for i in range(10)]
## print(ls)
## print(myreverse(ls))
## Effizienzanalyse
def analyze(fn, maxi=10000, step=500):
'''Funktion zur Ermittlung der Laufzeiten T(n) in Abhängigkeit von der Problemgröße n'''
tx = []
ty = []
global n # Damit es im Timer verwendet werden kann
for n in range(1, maxi, step): # Wortlängen n (Problemgröße)
tt = []
for i in range(10): # Anzahl k der Instanzen für jedes n
v = fn + '(ls)'
t = timeit.Timer(v, 'gc.enable(); \
from __main__ import ' + fn + ', myreverse, n; \
ls = [i for i in range(n)]') # wie eval
tt = tt + [t.timeit(number=1)]
tt.reverse() # sort(), falls best case gesucht
tx.append(n)
ty.append(tt[0]) # ist das Maximum der Zeitenliste
return tx, ty
plt.figure('Umkehr einer Listen')
result = analyze('myreverse')
plt.plot(result[0], result[1], 'bo', label='myreverse')
plt.legend(loc='upper left')
plt.show()
# --------------------------------------------------------------------------------
#
# Ergebnisse:
#
# Alle drei in O(n), n ... Anzahl der Listenelemente
# Ursache: Die Schleifen arbeiten mit O(n) und verschlingen den O(1)-Vorteil.
#
# Da push() und pop() von Stack1 in O(1) ist der Anstieg der Geraden geringer.
#
# Die Stack-Impl. 3 mit einfach verketteten Listen ist die ineffizienteste.
#
# --------------------------------------------------------------------------------
### Alternative: Verwendung eines anderen Datentyps: (Python-) Liste
def myreverse(ls):
ls.reverse()
return ls
## plt.figure('Umkehr einer Liste')
## result = analyze('myreverse',30000)
## plt.plot(result[0], result[1], 'bo', label='myreverse')
## plt.legend(loc='upper left')
## plt.show()
# -------------------------------------------------------------------------------
#
# Ergebnis:
#
# Liegt ebenfalls in O(n), n ... Anzahl der Listenelemente
# Ist wesentlich schneller (Geradenanstieg geringer) als bei Wahl von Stack 1, 2, 3.
#
# Die Python-Impl. verwendet ein ARRAY (aus C) und dimensioniert es so groß,
# dass es für viele Anwendungen ausreicht. Falls es voll ist, wird ein neues
# (wiederum over-allocated) ARRAY bereitgestellt und der Inhalt das alten
# dorhin KOPIERT. ---> Amorisierte Effizienz ist sehr gut.
# Deshalb gibt es in der Aufwandsgrafik immer wieder "Ausreißer".
#
# --------------------------------------------------------------------------------
</code>
[[Datei:Myreverse_plot.png]]