NB_02_Listen_und_Dezimalzahlen_Werkzeuge

(c) 2019/2020 Hochschule Augsburg - Fakultät für Informatik - Prof.Dr.Nik Klever

Werkzeuge für das Arbeiten mit Listen

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.

array

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:

In [18]:
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
In [19]:
from array import array
a = array('H', [4000, 10, 700, 22222])
sum(a)
Out[19]:
26932
In [20]:
a[1:3]
Out[20]:
array('H', [10, 700])

collections

deque

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:

In [21]:
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'])
In [22]:
%%Mooc StringAssessment
Out[22]:

Warteschlangen in der Datenkommunikation

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 paketnr

Geben 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])

Wie lautet der Befehl ein Datenpaket von der Sendequeue zur Empfängerqueue zu schicken?



OrderedDict

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:

In [23]:
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}
Out[23]:
OrderedDict([('Banane', 3), ('Zitrone', 4), ('Kiwi', 1), ('Orange', 2)])
In [24]:
# dictionary sorted by key
OrderedDict(sorted(d.items(), key=lambda t: t[0]))
Out[24]:
OrderedDict([('Banane', 3), ('Kiwi', 1), ('Orange', 2), ('Zitrone', 4)])
In [25]:
# dictionary sorted by value
OrderedDict(sorted(d.items(), key=lambda t: t[1]))
Out[25]:
OrderedDict([('Kiwi', 1), ('Orange', 2), ('Banane', 3), ('Zitrone', 4)])
In [26]:
# dictionary sorted by length of the key string
OrderedDict(sorted(d.items(), key=lambda t: len(t[0])))
Out[26]:
OrderedDict([('Kiwi', 1), ('Banane', 3), ('Orange', 2), ('Zitrone', 4)])
In [27]:
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)])
In [28]:
print(od['Kirsche'])
4

bisect

Zusätzlich zu alternativen Listenimplementierungen bietet die Standard Bibliothek auch weitere Werkzeuge wie das Modul bisect mit Methoden zur Manipulation von sortierten Listen:

In [29]:
import bisect
scores = [(100, 'perl'), (200, 'tcl'), (400, 'lua'), (500, 'python')]
bisect.insort(scores, (300, 'ruby'))
scores
Out[29]:
[(100, 'perl'), (200, 'tcl'), (300, 'ruby'), (400, 'lua'), (500, 'python')]

heapq

"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:

In [30]:
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")
In [31]:
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
In [32]:
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
In [33]:
# visualisierter Heap
Out[33]:
%3 0 0 1 1 0->1 2 2 0->2 6 6 1->6 3 3 1->3 5 5 2->5 4 4 2->4 7 7 6->7 8 8 6->8 9 9 3->9
In [34]:
heappush(data, -5)                 # add a new entry
print(data)
[-5, 0, 2, 6, 1, 5, 4, 7, 8, 9, 3]
In [35]:
# visualisierter Heap
Out[35]:
%3 -5 -5 0 0 -5->0 2 2 -5->2 6 6 0->6 1 1 0->1 5 5 2->5 4 4 2->4 7 7 6->7 8 8 6->8 9 9 1->9 3 3 1->3
In [36]:
p = [heappop(data) for i in range(3)]  # fetch the three smallest entries
p
Out[36]:
[-5, 0, 1]
In [37]:
print(data)
[2, 3, 4, 6, 9, 5, 8, 7]
In [40]:
%%Mooc MoocMultipleChoiceAssessment
Out[40]:

heapq

Es ist folgende Liste gegeben:

a = [-4,2,-3,5,3,8,2,6,9,19,7,17,17,11,17,20]

Ist die obige Liste eine Heap Queue oder nicht ?

Ja
Nein

Dezimalzahlen Arithmetik

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

  • Finanzanwendungen und sonstige Anwendungen, die eine genaue Dezimaldarstellung erfordern,
  • die Kontrolle über die Präzision der Gleitkomma-Arithmetik,
  • die Kontrolle über Rundungsmechanismen, um gesetzliche oder regulatorische Anforderungen zu erfüllen,
  • die Verfolgung von signifikanten Dezimalstellen oder
  • Anwendungen, bei denen der Benutzer erwartet, dass die Ergebnisse mit den von Hand bearbeiteten Berechnungen übereinstimmen.

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:

In [41]:
from decimal import *
round(Decimal('0.70') * Decimal('1.05'), 2)
Out[41]:
Decimal('0.74')
In [42]:
round(.70 * 1.05, 2)
Out[42]:
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:

In [43]:
Decimal('1.00') % Decimal('.10')
Out[43]:
Decimal('0.00')
In [44]:
1.00 % 0.10
Out[44]:
0.09999999999999995
In [45]:
sum([Decimal('0.1')]*10) == Decimal('1.0')
Out[45]:
True
In [46]:
sum([0.1]*10) == 1.0
Out[46]:
False

Das Modul decimal bietet zudem eine Arithmetik mit so viel Genauigkeit wie benötigt wird:

In [47]:
getcontext().prec = 36
Decimal(1) / Decimal(7)
Out[47]:
Decimal('0.142857142857142857142857142857142857')
In [49]:
%%Mooc MoocMultipleChoiceAssessment
Out[49]:

Dezimalzahlen

Es ist folgender Code gegeben:


getcontext().prec = 2
a = 0.5
b = Decimal(10)
print(a+b)

Geben sie das Ergebnis des obigen Codes an:

10
10.5
10.50
TypeError

In [50]:
%%Mooc Video
Out[50]:

Weitere Literatur

In [51]:
%%Mooc WebReference

Brief Tour of the Standard Library - Part II

https://docs.python.org/3/tutorial/stdlib2.html

Hinweis: Kurze Auflistung einiger weiterer Module aus der Standardbibliothek

In [53]:
%%Mooc WebReference

collections — Container datatypes

https://docs.python.org/3/library/collections.html

Hinweis: collextions - Weitere Datentypen für Container Objekte

In [54]:
%%Mooc WebReference

heapq — Heap queue algorithm

https://docs.python.org/3/library/heapq.html

Hinweis: heapq - Heap Queue Algorithmus

In [55]:
%%Mooc WebReference

decimal — Decimal fixed point and floating point arithmetic

https://docs.python.org/3/library/decimal.html

Hinweis: decimal - Dezimalzahlen Arithmetik für Festkomma- und Gleitkommadezimalzahlen