[Tutor] Re: Comparing lists

[Derrick 'dman' Hudson]

--mSxgbZZZvrAyzONB
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Tue, Jul 09, 2002 at 02:55:28PM +0000, Terje Johan Abrahamsen wrote:
| I am trying to find out if there is some number that exists in both lists=
.=20
| It doesn't matter if they are in the same place or not. I just want to fi=
nd=20
| if some number exists in both lists, or if all numbers differs from all=
=20
| numbers in the other list.

Several people have posted the most obvious solution (a nested loop),
but that method is O(n**2).  (read: order n squared)  As the inputs
increase in size, the execution time increases exponentially.  (IOW,
if you double the size of the input data, you *square* the execution
time)

Since python has dictionaries built-in, and your data is hashable,
I'll use it instead :

# build your lists first, however you do that
l1 =3D [data]
l2 =3D [data]

# put all the elements of the first list into the dictionary as keys
d1 =3D {}
for item in l1 :
    d1[item] =3D None

for item in l2 :
    if d1.has_key( item ) :
        print item , "is in both lists"
    else :
        print item , "is NOT in both lists"


This method is O(n).  Rather than comparing each element of l2 to each
element of l1 (nxm comparisons), I use the effectiveness of hashing to
perform one comparison for each element of l2 (n comparisons).  I've
also eliminated any duplicate items in l1.  For large inputs where
duplicate elements are expected, you would be better off doing the
same for l2 -- pack it into a dict (as a faster way of removing
duplicates than sorting) then iterate over the keys.  For small
inputs, however, that would have more overhead and hurt performance.

What it looks like you're really interested in, though, is either a
Set or a Multiset structure.  Sets are structures that don't have any
order, and equality comparisons are a matter of seeing if each has the
same elements.  I'm sure you can find a Set implementation in python
on the web somewhere, or it would be fairly easy to write one
yourself.

HTH,
-D

--=20
=20
Many are the plans in a man's heart,
but it is the Lord's purpose that prevails.
        Proverbs 19:21
=20
http://dman.ddts.net/~dman/


--mSxgbZZZvrAyzONB
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iEYEARECAAYFAj0rFl8ACgkQO8l8XBKTpRRPzACfYg9MbvThap3XP+OOQ8QolzDA
KGUAnA3NBMq3Z/9qlvuUD6E4zO8oP9Ic
=E676
-----END PGP SIGNATURE-----

--mSxgbZZZvrAyzONB--