dictionary comparison

[theoryboy at my-deja.com]

Yes, I guess I should have been more specific.

My application area is that of labelled finite state automata (FSA).
Each automata is represented by a dictionary file, where the index is
the state and each entry consists of a list of two item lists. Each
inner list contains the name of a transition, and which state that
transition leads to. A typical entry might look like this:

{'state1': [['do_A', 'state2'],['do_B', 'state3']], ...

so 'state1' consists of two transitions, 'do_A' leading to 'state2' and
'do_B' leading to 'state3'.

On a number of occasions, I wish to compare each state in an FSA with
all other states, and perform processing based on properties of those
states. For example, I want to find states which have identical
transitions, and put one of these states into a list to keep, and the
other into a list to be reduced. However, if I simply nest two loops:

for state1 in FSA.keys()
	for state2 in FSA.keys()
		if FSA[state1] is not FSA[state2] and\
		   FSA[state1] == FSA[state2]:
			keep_list.append(state1)
			remove_list.append(state2)

I will of course get duplicate entries. I could simply check to see if
the items have already been added, but this still means n^2 comparisons,
not sum to n which is all I need.

The same problem can be true of lists, but with lists it is easy enough
to use numerical indices to make sure the start of the inner loop
"follows" the outer loop. This obviously cannot be done with
dicitionaries, but is there a similar solution that's staring me in the
face somewhere?

Peter


> What sort of comparison do you require?  If it's just equality,
> as was already indicated, dict1==dict2 will work -- but if what
> you want to check is, say, whether the set of keys are the
> same (independently of what value corresponds to each key),
> or other kinds of comparison, it won't do.  I can't tell from
> these two non-nested empty (syntactically invalid) loops
> what it is that you mean to do...
>
> Alex
>
>


Sent via Deja.com http://www.deja.com/
Before you buy.