dictionary comparison

[Olivier Dagenais]

What about my solution?  It was O(n) and gave you the opportunity to find
out the difference between the two dictionaries...  Is that not what you
want?  Remember that you don't usually need to search a dictionary like you
would an array, since has_key() can give you an answer in (on average) O(1)
time....

--
----------------------------------------------------------------------
Olivier A. Dagenais - Carleton University - Computer Science III


<theoryboy at my-deja.com> wrote in message news:8n0ebs$65n$1 at nnrp1.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.