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]

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

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]

Hmm,

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

-pekka-

Pekka Niiranen wrote:

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

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

 

[Peter Otten]

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

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]

Hi there,

I have tree-like dictionary

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

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