Die folgende Klasse zeigt die einfachste Implementation einer Multimengen (Bag). Zur Datenhaltung wir eine Python Liste, die einem dynamischen (vergrösser/verkleinerbarem) Array entspricht.
class Bag:
def __init__(self):
self._data = []
def add(self, item):
self._data.append(item)
def size(self):
return len(self._data)
def isEmpty(self):
return self.size() == 0
class Iterator:
def __init__(self, bag):
self._currentItem = 0
self.bag = bag
def hasNext(self):
return (self._currentItem < self.bag.size())
def next(self):
item = self.bag._data[self._currentItem]
self._currentItem += 1
return item
def iterator(self):
return Bag.Iterator(self)
Bags sind immer dann sinnvoll, wenn die Reihenfolge der Elemente für eine Berechnung nicht relevant sind. Ein typisches Beispiel ist die Berechnung von Mittelwert und Varianz in einem Datensatz.
Damit wir auch wissen ob unsere Berechnungen funktionieren, kreieren wir Testdaten mit einem bekanntem Mittelwert und Varianz. Die einfachste Variante ist, diese einfach zufällig von der Normalverteilung zu samplen.
from random import gauss
rng = testdata = [gauss(1.0, 4) for _ in range(1000)]
Als erstes fügen wir die Testdaten ein:
b = Bag()
for t in testdata:
b.add(t)
Dann berechnen wir den mean. Wie benutzen dazu den Iterator.
sum = 0.0
it = b.iterator()
while it.hasNext():
sum += it.next()
mean = sum / b.size()
Und schlussendlich können wir die Varianz berechnen. Beachten Sie, dass wir dazu einen neuen Iterator erstellen müssen, damit wir wieder durch den ganzen Bag durchlaufen.
from math import sqrt
squaredDeviation = 0.0
it = b.iterator()
while (it.hasNext()):
v = it.next();
squaredDeviation += (v - mean) * (v - mean)
var = sqrt(squaredDeviation / b.size())
print("mean %f, variance : %f"%(mean, var))