Folgende Aufrufe illustrieren verschiedene Möglichkeiten ein Array in Python zu erzeugen.
[]
[]
["a", "list", "of", "strings"]
['a', 'list', 'of', 'strings']
[None] * 10
[None, None, None, None, None, None, None, None, None, None]
Lesen und Setzen von Elementen passiert via dem [] Operator. Falls der Index negativ ist, wird vom Ende gezählt.
xs = ["a", "b", "c", "d"]
print(xs[0])
a
print(xs[-1])
d
xs[2]="c'"
xs
['a', 'b', "c'", 'd']
Mittels insert und append können neue Elemente zum Array hinzugefügt werden.
xs.insert(2, "bb")
xs.append("dd")
xs
['a', 'b', 'bb', "c'", 'd', 'dd']
Ob ein Element existiert kann mittels dem "in" operator ermittelt werden. Den Index eines Elements erhält man via der Methode index. Was macht index, wenn das Element nicht exisitert?
"z" in xs
False
"b" in xs
True
xs.index("b")
1
Im folgenden messen wir die Laufzeit der verschiedenen Operationen für Arrays von wachsender Grösse
import timeit
import random
arrays = [ [0]*(10**i) for i in range(1, 8)]
def accessArray(a):
r = random.randint(0, len(a)-1)
a[r] = 10
def findInArray(a):
c = "you wont find me" in a
def appendToArray(a):
for i in range(0, 10000):
a.append(1)
def insertIntoArray(a):
a.insert(0, "newElement")
for array in arrays:
print(timeit.timeit(lambda: accessArray(array), number=100000))
0.4285048023926774 0.45788037844373325 0.4079051139990926 0.516654931818135 0.4410786754879885 0.47750460327658883 0.4547844311746001
for array in arrays:
print(timeit.timeit(lambda: findInArray(array), number=100))
0.00012070129918129169 0.0005743575427019643 0.006207905935096125 0.05329660291530569 0.5000802622584692 3.666414863502842 37.244375381040456
for array in arrays:
print(timeit.timeit(lambda: appendToArray(array), number=100))
0.32479364799149124 0.21886101491728027 0.33826580150383734 0.30265276001585306 0.328408528737377 0.21884664571500423 0.30730838155568563
# we need to reinitialize the arrays, as the append in the previous cell
# changed them
arrays = [ [0]*(10**i) for i in range(1, 8)]
for array in arrays:
print(timeit.timeit(lambda: insertIntoArray(array), number=1000))
0.001226719326375303 0.0013683586060224684 0.001967759615567388 0.016258136560793446 0.17450534021139674 1.4883985113506384 14.917255564473585
Achtung: Der Befehl getsizeof funktioniert nur für primitive Datentypen (int, ...)
import sys
for array in arrays:
print(sys.getsizeof(array))
8208 9864 16728 90120 900120 9000120 90000120
Folgender Code illustriert wie man ein Array effizient vergrössern kann.
Da es in Python nicht möglich ist, direkt auf einen Speicherblock zuzugreifen, wird der Speicher hier durch die Liste _data
repräsentiert.
class Array:
def __init__(self):
self._data = [None] # list simulates block of memory
self._lastIdx = 0
def append(self, elem):
if len(self._data) == self._lastIdx:
self._resize(len(self._data) * 2)
self._data[self._lastIdx] = elem
self._lastIdx += 1
def _resize(self, numElements ):
newArray = [None] * numElements
print("resizing from %d to %d"%(len(self._data), numElements))
for i in range(0, len(self._data )):
newArray[i] = self._data[i]
self._data = newArray
def __str__(self):
return str(self._data)
def length(self):
return self._lastIdx
Wir testen die Methode durch wiederholtes Aufrufen der append Funktion.
Wir sehen, dass in unserer Implementation, die methode resize nicht bei jedem append
Call aufgerufen wird.
a = Array()
for i in range(0, 128):
a.append("x")
print(a.length())
resizing from 1 to 2 resizing from 2 to 4 resizing from 4 to 8 resizing from 8 to 16 resizing from 16 to 32 resizing from 32 to 64 resizing from 64 to 128 128