comparing two lists, ndiff performance

[Zbigniew Braniecki]

Hi all.
I'm working on a tool for localizers.

I have two Lists with Entities/Strings/Comments (each L10n file is built 
  of those three elements).

So I have sth like:

l10nObject = []
l10nObject.append(Comment('foo'))
l10nObject.append("string")
l10nObject.append(Entity('name', 'value'))

etc. I can have many strings, many entities and many comments inside.

At some point I want to compare two l10nObjects and see what entities 
were added, what strings were changed, what comments were removed.

So What I did is that I basing on the structure of l10nObject created a 
list of elements with names of the types like:

structure1 = 
['Comment','Entity','Entity','str','str','Entity','Entity','Comment']

and same for structure2.

In result I want to have info about added/removed elements and then I 
can try to match which ones are in reality changed (so compare the value 
of two entities or two comments or two strings) etc.

Long story short. I'm comparing two "structures" using ndiff.
It takes LOONG time.

In case of my script the ndiff takes 80% of the whole script time, and 
in result the new method with ndiff takes over 10 sec for 1000 
iterations, while the old one takes around4 sec for 1000 iterations.

You can take a look at the code at: 
http://svn.braniecki.net/wsvn/Mozpyl10n/lib/mozilla/l10n/diff.py

The def diffToObject at the end is the new method, while def 
compareL10nObjects is the old one.

The new one is of course much better and cleaner (the old one is 
bloated), but I'm wondering if there is a faster way to compare two 
lists and find out what was added, what was removed, what was changed.
I can simply iterate through two lists because I need to keep an order 
(so it's important that the removed line is after the 3 line which was 
not changed etc.)

ndiff plays well here, but it seems to be extremely slow (1000 
iterations of diffToObject takes 10 sec, 7sec of this is in ndiff).

Do you have any idea on how to compare those lists? I have similar 
problem with comparing two directory lists where I also need to keep the 
  order, and I'm using the same ndiff method now.

Is there a way to speed it up? Any easier way? Faster method?

Greetings
Zbigniew Braniecki