[Python] Conditioneel sorteren van dictionary

[basovic88]

In Python heb ik de volgende dictionary:

Python:

{(0,0,4):243.33, (0,0,1):272.38, (0,0,2):234.98, ... , (-23,36,72):24.23}

De dictionary key is een tuple (x,o,y). De waarde van de key (tuple) is gelijk aan de kosten van de combinatie x,o en y.
De combinatie (0,0,4) kost bijvoorbeeld 243.33 euro.

Nu wil ik van deze dictionary de minimale kosten van alle combinaties (x,o,*).
Bijvoorbeeld ik wil uit deze dictionary de waarde waarvan de key (tuple) gelijk is aan (0,0,*) dus (0,0,1), (0,0,2) etc.

Momenteel los ik dit als volgt op

Python:

def getMin(dict,x,o):
   vals = dict.values()
   keys = dict.keys()
   ary = []
   i = 0

   for k in keys:
      if k[0]==x and k[1]==o
         ary.append(vals[i])
      i += 1

   return min(ary)

Echter, het doorlopen van de complete dictionary van wel 1.000.000 items, is relatief tijdrovend, laat staan als ik dit meer dan 100.000 keer moet doen.
Ik ben echt heel nodig op zoek naar een efficienter alternatief.

Mvg,

Bas

[Tim]

Je zou de waardes kunnen opslaan in een 3d-list ipv een dict, het minimum vinden is dan slechts min(lijst[x][o]). Zonder je datastructuur te veranderen gaat het in ieder geval niet veel sneller worden.

[ Voor 27% gewijzigd door Tim op 08-12-2010 17:12 ]

[basovic88]

Tim schreef op woensdag 08 december 2010 @ 17:11:
Je zou de waardes kunnen opslaan in een 3d-list ipv een dict, het minimum vinden is dan slechts min(lijst[x][o]). Zonder je datastructuur te veranderen gaat het in ieder geval niet veel sneller worden.

Maar de variabelen x en o kunnen ook negatief zijn.
list[x][o] kan dan niet.

Daarom heb ik juist een dictionary gebruikt omdat ik dan een eigen indexering kan toepassen.

[0fbe]

Ik kan op het moment even geen documentatie van Python hierover vinden maar ik vermoed dat het volgende sneller is:

code:

for k, v in dict.iteritems():
    *doe iets met k en v*

In jouw code gebruik je namelijk een lookup in de forloop (vals[i]) wat de complexiteit van de functie naar n² zou kunnen brengen.

Ook kan je de minimale tupel onthouden en zo de min(ary) aan het einde besparen.

Een 3D list is sowieso sneller omdat je dan maar een rij langs hoeft te itereren in plaats een 3 macht zo veel. Je kan natuurlijk gewoon een soort conversie van signed naar unsigned gebruiken om het toch in een 3D list te passen. Netter wordt het er niet op, sneller wel.

[ Voor 24% gewijzigd door 0fbe op 08-12-2010 17:32 ]

[Tim]

In dat geval kan je 3 geneste dicts gebruiken. Of als de keys wel aansluitend zijn, de minimale key bij de index optellen.

[basovic88]

Tim schreef op woensdag 08 december 2010 @ 17:50:
In dat geval kan je 3 geneste dicts gebruiken. Of als de keys wel aansluitend zijn, de minimale key bij de index optellen.

Ah yes, natuurlijk.
Die geneste dictionaries doen het prima.