Help needed: optimizing dictionary creation/access

[Pekka Niiranen]

Hi there,

I have tree-like dictionary

data = {p_name: {p_keyp: {p_cost: [p_unit, t]}}}

which I update by creating nonexisting branches when necessary.
If the full branch already exists I update its 'p_unit' -value only if
it is greater than the presently stored item. See code below.

The use of method "has_key" with nested if -statements works,
but there MUST be a better way.

I was not able to take advantage of dictionary's
"setdefault " method (I got lost in nested setdefaults)
nor did I manage to find an elegant function to
"create the rest of the missing branch from
(this/any) point onwards", like:

try:
data[p_name][p_keyp][p_cost] = [p_unit, t]
error:
<create branch from missing key onwards>

Any ideas?


------------- code starts --------------
def update(p_name, p_keyp, p_cost, p_unit, data):
t = time.asctime()
if data.has_key(p_ name):
if data[p_name].has_key(p_keyp ):
if data[p_name][p_keyp].has_key(p_cost ):
if p_unit > data[p_name][p_keyp][p_cost][0]:
data[p_name][p_keyp][p_cost] = [p_unit, t]
else:
data[p_name][p_keyp][p_cost] = [p_unit, t]
else:
data[p_name][p_keyp] = {p_cost: [p_unit, t]}
else:
data[p_name] = {p_keyp: {p_cost: [p_unit, t]}}
return data

------------- code stops --------------

-pekka-

[Peter Otten]

Re: Help needed: optimizing dictionary creation/access

Pekka Niiranen wrote:
[color=blue]
> def update(p_name, p_keyp, p_cost, p_unit, data):
> t = time.asctime()
> if data.has_key(p_ name):
> if data[p_name].has_key(p_keyp ):
> if data[p_name][p_keyp].has_key(p_cost ):
> if p_unit > data[p_name][p_keyp][p_cost][0]:
> data[p_name][p_keyp][p_cost] = [p_unit, t]
> else:
> data[p_name][p_keyp][p_cost] = [p_unit, t]
> else:
> data[p_name][p_keyp] = {p_cost: [p_unit, t]}
> else:
> data[p_name] = {p_keyp: {p_cost: [p_unit, t]}}
> return data
>[/color]

Untested:

def update(name, keyp, cost, unit, root):
data = root.setdefault (name, {})
data = data.setdefault (keyp, {})
oldunit = data.get(cost, None)
if oldunit:
if unit > oldunit[0]:
oldunit[:] = [unit, time.asctime()]
else:
data[cost] = [unit, time.asctime()]

return root

You might consider using a single dictionary with (name, keyp, cost) tuples
as keys.

Peter

[Pekka Niiranen]

Re: Help needed: optimizing dictionary creation/access

Hmm,

does not using tuple (name, keyp, cost) as key make access time linear?

-pekka-

Peter Otten wrote:
[color=blue]
> Pekka Niiranen wrote:
>
>[color=green]
>>def update(p_name, p_keyp, p_cost, p_unit, data):
>> t = time.asctime()
>> if data.has_key(p_ name):
>> if data[p_name].has_key(p_keyp ):
>> if data[p_name][p_keyp].has_key(p_cost ):
>> if p_unit > data[p_name][p_keyp][p_cost][0]:
>> data[p_name][p_keyp][p_cost] = [p_unit, t]
>> else:
>> data[p_name][p_keyp][p_cost] = [p_unit, t]
>> else:
>> data[p_name][p_keyp] = {p_cost: [p_unit, t]}
>> else:
>> data[p_name] = {p_keyp: {p_cost: [p_unit, t]}}
>> return data
>>[/color]
>
>
> Untested:
>
> def update(name, keyp, cost, unit, root):
> data = root.setdefault (name, {})
> data = data.setdefault (keyp, {})
> oldunit = data.get(cost, None)
> if oldunit:
> if unit > oldunit[0]:
> oldunit[:] = [unit, time.asctime()]
> else:
> data[cost] = [unit, time.asctime()]
>
> return root
>
> You might consider using a single dictionary with (name, keyp, cost) tuples
> as keys.
>
> Peter
>[/color]

[Peter Otten]

Re: Help needed: optimizing dictionary creation/access

Pekka Niiranen wrote:
[color=blue]
> does not using tuple (name, keyp, cost) as key make access time linear?[/color]

I don't see how the kind of key can influence the big-O behaviour of a dict.
A hash is a hash is a hash, after all. Or am I missing something?

Peter

[Edward C. Jones]

Re: Help needed: optimizing dictionary creation/access

Pekka Niiranen wrote:[color=blue]
> Hi there,
>
> I have tree-like dictionary
>
> data = {p_name: {p_keyp: {p_cost: [p_unit, t]}}}[/color]

Try "http://members.tripod. com/~edcjones/MultiDict.py".