(c) 2023 Technische Hochschule Augsburg - Fakultät für Informatik - Prof.Dr.Nik Klever - Impressum
Viele Datenstrukturanforderungen können mit dem normalen, built-in Listentyp list erfüllt werden. Allerdings gibt es manchmal die Notwendigkeit alternativer Implementierungen um unterschiedliche Performance Anforderungen erfüllen zu können.
Das Modul array stellt ein array()-Objekt zur Verfügung, das analog wie eine Liste agiert, aber nur homogene Daten verwendet und diese damit kompakter abspeichert. Das folgende Beispiel zeigt ein Array von Zahlen, die als zwei Byte unsignierte Binärzahlen (entsprechend dem Typcode "H") und nicht die üblichen 16 Bytes pro Eintrag, die für reguläre Listen von Python int Objekten gespeichert sind:
import sys
import decimal
d = {
"int": 0,
"float": 0.0,
"dict": dict(),
"set": set(),
"tuple": tuple(),
"list": list(),
"str": "a",
"unicode": u"a",
"decimal": decimal.Decimal(0),
"object": object(),
}
for k, v in d.items():
print(k, sys.getsizeof(v))
int 24 float 24 dict 240 set 224 tuple 48 list 64 str 50 unicode 50 decimal 104 object 16
from array import array
a = array('H', [4000, 10, 700, 22222])
sum(a)
26932
a[1:3]
array('H', [10, 700])
Das Modul collections bietet ein deque() Objekt, das eine Liste mit schnelleren Anhängen und Pops von der linken Seite, aber langsamere Lookups in der Mitte ist. Diese Objekte eignen sich hervorragend für die Implementierung von Warteschlangen (s. Skript Informatik 1, Kapitel Datenstrukturen 1, Unterkapitel Listen:
from collections import deque
d = deque(["task1", "task2", "task3"])
print("Warteschlange:",d)
n = "task4"
print("Neue Aufgabe: {}".format(n))
d.append(n)
print("Warteschlange:",d)
print("Bearbeite:", d.popleft())
print("Warteschlange:",d)
Warteschlange: deque(['task1', 'task2', 'task3']) Neue Aufgabe: task4 Warteschlange: deque(['task1', 'task2', 'task3', 'task4']) Bearbeite: task1 Warteschlange: deque(['task2', 'task3', 'task4'])
%%Mooc StringAssessment
Gegeben seien die folgenden beiden Queues
sender = deque([1, 2, 3, 4])
empfaenger = deque([])Es sollen die Daten-Pakete 1,2,3,4 der Reihe nach vom Sender zum Empfänger geschickt werden. Wie würde eine Funktion send mit den beiden Argumenten sender und empfaenger lauten, die bei jedem Aufruf ein Paket vom sender zum empfaenger schickt und als Rückgabewert die Paketnr zurückgibt
paketnr = 0
def send(sender,empfaenger):
global paketnr
if len(sender):
...
paketnr += 1
return paketnrGeben sie als Antwort den Befehl ein, der in der Zeile mit den 3 Punkten (...) stehen muss. Nach dem Versenden aller Pakete (also nach dem 4-maligen Aufruf von send sollten die beiden Queues folgendermaßen aussehen:
sender = deque([])
empfaenger = deque([1, 2, 3, 4])Das Modul collections bietet weitere Objekte u.a. auch für geordnete Dictionaries: OrderedDict, mit denen die zufällige Anordnung der Schlüsselwerte in normalen Dictionaries durch die Reihenfolge der Einträge ersetzt wird:
from collections import OrderedDict
# regular unsorted dictionary
d = {'Banane': 3, 'Zitrone': 4, 'Kiwi': 1, 'Orange': 2}
print(d)
OrderedDict(d)
{'Banane': 3, 'Zitrone': 4, 'Kiwi': 1, 'Orange': 2}
OrderedDict([('Banane', 3), ('Zitrone', 4), ('Kiwi', 1), ('Orange', 2)])
# dictionary sorted by key
OrderedDict(sorted(d.items(), key=lambda t: t[0]))
OrderedDict([('Banane', 3), ('Kiwi', 1), ('Orange', 2), ('Zitrone', 4)])
# dictionary sorted by value
OrderedDict(sorted(d.items(), key=lambda t: t[1]))
OrderedDict([('Kiwi', 1), ('Orange', 2), ('Banane', 3), ('Zitrone', 4)])
# dictionary sorted by length of the key string
OrderedDict(sorted(d.items(), key=lambda t: len(t[0])))
OrderedDict([('Kiwi', 1), ('Banane', 3), ('Orange', 2), ('Zitrone', 4)])
import random
od = OrderedDict()
ol = ["Kirsche", "Apfel", "Birne", "Himbeere", "Pfirsich"]
for sorte in ol:
od.update({sorte:random.randint(1,10)})
print(od)
OrderedDict([('Kirsche', 4), ('Apfel', 8), ('Birne', 8), ('Himbeere', 8), ('Pfirsich', 4)])
print(od['Kirsche'])
4
Zusätzlich zu alternativen Listenimplementierungen bietet die Standard Bibliothek auch weitere Werkzeuge wie das Modul bisect mit Methoden zur Manipulation von sortierten Listen:
import bisect
scores = [(100, 'perl'), (200, 'tcl'), (400, 'lua'), (500, 'python')]
bisect.insort(scores, (300, 'ruby'))
scores
[(100, 'perl'), (200, 'tcl'), (300, 'ruby'), (400, 'lua'), (500, 'python')]
"Ein Heap in der Informatik ist eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Den Elementen ist dabei ein Schlüssel zugeordnet, der die Priorität der Elemente festlegt. Häufig werden auch die Elemente selbst als Schlüssel verwendet. Über die Menge der Schlüssel muss daher eine totale Ordnung festgelegt sein, über welche die Reihenfolge der eingefügten Elemente festgelegt wird." Quelle: Wikipedia)
Verwendet wird ein Heap oftmals als Implementation für einen dynamische Speicher, d.h. einen Speicherbereich, aus dem zur Laufzeit eines Programms zusammenhängende Speicherabschnitte angefordert und in beliebiger Reihenfolge wieder freigegeben werden können - im Gegensatz zum Stack, bei dem die Speicherabschnitte in der umgekehrten Reihenfolge wieder freigegeben werden müssen, in der sie angefordert wurden.
Der im Modul heapq implementierte Heap ist ein binärer Baum, in dem jeder Elternknoten einen Wert hat, der kleiner oder gleich einem seiner Kinder ist. Diese Implementierung verwendet ein Array, für das
heap[k] <= heap[2\*k+1] und heap[k] <= heap[2\*k+2] für alle k gilt, wobei von Null an gezählt wird.
In Vergleichen werden nicht existierende Elemente als unendlich angesehen. Die interessante Eigenschaft eines Heaps ist, dass sein kleinstes Element immer die Wurzel ist, heap[0].
Das Modul heapq bietet Funktionen zur Implementierung von Mengen auf der Basis regulärer Listen. Der niedrigst bewertete Eintrag wird immer auf Position Null gehalten. Dies wird für Anwendungen verwendet, die immer wieder auf das kleinste Element zugreifen, aber keine vollständige Liste sortieren möchten:
from heapq import heapify, heappop, heappush
def testheap(data):
for i in range(len(data)):
compare = [True,True]
for j in 0,1:
if 2*i+j+1 < len(data):
compare[j] = data[i] <= data[2*i+j+1]
if not (compare[0] and compare[1]):
print("data is not a heap")
break
else:
print("data is a heap")
data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
print(data)
testheap(data)
[1, 3, 5, 7, 9, 2, 4, 6, 8, 0] data is not a heap
heapify(data) # rearrange the list into heap order
print(data)
testheap(data)
[0, 1, 2, 6, 3, 5, 4, 7, 8, 9] data is a heap
# visualisierter Heap
heappush(data, -5) # add a new entry
print(data)
[-5, 0, 2, 6, 1, 5, 4, 7, 8, 9, 3]
# visualisierter Heap
p = [heappop(data) for i in range(3)] # fetch the three smallest entries
p
[-5, 0, 1]
print(data)
[2, 3, 4, 6, 9, 5, 8, 7]
%%Mooc MoocMultipleChoiceAssessment
Es ist folgende Liste gegeben:
a = [-4,2,-3,5,3,8,2,6,9,19,7,17,17,11,17,20]Das Modul dezimal bietet einen Datentyp für die Gleitkomma-Arithmetik von Dezimalzahlen. Im Vergleich zur eingebauten Implementierung der Gleitkomma-Arithmetik von reelle Zahlen vom Typ float ist die Klasse Decimal besonders hilfreich für
Zum Beispiel ergibt die Berechnung einer 5% Steuer auf eine 70 Cent Telefongebühr verschiedene Ergebnisse bei der Gleitkomma-Arithmetik von Dezimalzahlen und der Gleitkomma-Arithmetik von reellen Zahlen. Der Unterschied wird deutlich, wenn die Ergebnisse auf den nächsten Cent gerundet werden:
from decimal import *
round(Decimal('0.70') * Decimal('1.05'), 2)
Decimal('0.74')
round(.70 * 1.05, 2)
0.73
Das Ergebnis einer Berechnung mit Dezimalzahlen behält nachfolgende Nullen, wobei automatisch z.B. vier Stellen signifikant werden, wenn bei den Multiplikanden entsprechend jeweils zwei Stellen signifikant sind. Die Klasse Dezimal reproduziert eine Mathematik mit Bleistift und Papier und vermeidet daher Probleme, die entstehen können, wenn die Gleitkomma-Arithmetik der reellen Zahlen nicht genau die Dezimalzahlen darstellen kann.
Die exakte Darstellung von Dezimalzahlen ermöglicht es der Klasse Decimal, Modulo-Berechnungen und Gleichheitstests durchzuführen, die mit reellen Zahlen vom Typ float nicht durchführbar sind:
Decimal('1.00') % Decimal('.10')
Decimal('0.00')
1.00 % 0.10
0.09999999999999995
sum([Decimal('0.1')]*10) == Decimal('1.0')
True
sum([0.1]*10) == 1.0
False
Das Modul decimal bietet zudem eine Arithmetik mit so viel Genauigkeit wie benötigt wird:
getcontext().prec = 36
Decimal(1) / Decimal(7)
Decimal('0.142857142857142857142857142857142857')
%%Mooc MoocMultipleChoiceAssessment
Es ist folgender Code gegeben:
getcontext().prec = 2
a = 0.5
b = Decimal(10)
print(a+b)%%Mooc Video
%%Mooc WebReference
https://docs.python.org/3/tutorial/stdlib2.html
Hinweis: Kurze Auflistung einiger weiterer Module aus der Standardbibliothek
%%Mooc WebReference
https://docs.python.org/3/library/collections.html
Hinweis: collextions - Weitere Datentypen für Container Objekte
%%Mooc WebReference
https://docs.python.org/3/library/heapq.html
Hinweis: heapq - Heap Queue Algorithmus
%%Mooc WebReference
https://docs.python.org/3/library/decimal.html
Hinweis: decimal - Dezimalzahlen Arithmetik für Festkomma- und Gleitkommadezimalzahlen