Uporaba slovarja v Pythonu kot polje


Že skoraj dve leti se ukvarjam s programiranjem v Pythonu pa sem šele sedaj ugotovil, da lahko built-in podatkovno strukturo slovar ((dict)) uporabim tudi kot dvodimenzionalno polje, saj slovar za ključ sprejme tudi n-terico ((tuple)). Do sedaj sem namreč skoraj vedno za dvodimenzionalno polje uporabljal seznam ((list)) seznamov.

Prednost uporabe slovarja kot dvo- ali večdimenzionalno polje je v tem, da je časovna zahtevnost iskanja elementa amortizirane časovne zahtevnosti O(1), ta pa ni odvisna od števila ključev v slovarju. Na drugi strani traja iskanje elementa v seznamu O(n), kjer je n število elementov v seznamu. Če imamo seznam seznamov, kjer je v seznamu n podseznamov s po m elementi, potem je časovna zahtevnost iskanja elementa kar O(n*m).

Slovar kot polje zelo prav pride pri matrikah, kjer je večina njenih elementov enaki neki privzeti vrednosti (na primer 0). Za boljšo ponazoritev si oglejte spodnji primer učinkovitega shranjevanje matrike, ki ima neničelne elemente samo na glavni diagonali in branje vrednosti iz nje na klasičen način (po stolpcih in vrsticah):

[python]
from collections import defaultdict

M = [[1, 0, 0, 0, 0], \
[0, 3, 0, 0, 0], \
[0, 0, 5, 0, 0], \
[0, 0, 0, 2, 0], \
[0, 0, 0, 0, 7]]

m = 5
n = 5

matrix = defaultdict(int)

for i, row in enumerate(M):
matrix[i, i] = row[i]

for i in range(5):
for j in range(5):
print matrix[i, j]
[/python]

Pythonov modul collections vsebuje razred defaultdict, ki je posebne vrste slovar. Posebnost tega tipa slovarja je, da če bomo v njem poizvedovali po ključu, ki ne obstaja v njem, potem se bo vrnila neka privzeta vrednost, ki jo določimo ob kreiranju defaultdict objekta. Tako nam v zgornjem primeru slovar sam poskrbi za “shranjenje” ničel in tako vsebuje samo 5 elementov in ne 25, kot bi jih sicer (privzeta vrednost je določena s funkcijo int, ki vrne 0).