Approximate comparison of two lists of floats

[Dan Stromberg]

You'd probably better explain in English which things truly need to be
compared with what.  Right now, your first version is, I believe, an O(n^4)
algorithm, which is extremely expensive, while your second (set-based)
version appears to be O(n^3), which is quite a bit better, but still not
stellar.

I suspect you could just flatten your list of lists of numbers down to a
single list of numbers, and then extract the maximum and minimum numbers
using the min and max functions, and then compare those two results within
tolerance, but further discussion should determine if that's correct.  If
this would give the correct result, it should be an O(n) algorithm, which is
vastly faster.

The main question in my mind is: Are the inner lists (in your list of lists)
things that need to be somehow compared as a unit against all the other such
units, or are they all the same kind of thing that just happens to be in an
unnecessarily structured representation right now.

On Thu, Jul 28, 2011 at 12:11 AM, Christian Doll <dollebolle at gmail.com>wrote:

> Hello,
>
> i have e little performance problem with my code...
>
> i have to compare many lists of very much floats. at moment i have
> nested for-loops
>
> for a in range( len(lists) ):
>    for b in range( a+1 , len(lists) ):
>        for valuea in lists[a]:
>            equal=False
>            for valueb in lists[b]:
>                if inTolerance( valuea , valueb , 1.0): # inTolerance
> is an own function, which checks if the difference of valuea and
> valueb is not more then 1.0%
>                    equal=True
>                    break
>    if equal:
>        print a , "and" , b , "are equal"
>
> i found a version with set which is faster, but i cannot assign an
> tolerance (%)
> for a in range( len(lists) ):
>    for b in range( a+1 , len(lists) ):
>        if len( lists[a] ) ==
> len( set( lists[a] ).intersection( set( lists[b] ) ) ):
>            print a , "and" , b , "are equal"
>
> have you an idea how i can change my code, that i can compare many
> lists of floats with a tolerance in percentage very fast?
>
> (sorry for my bad englisch ;-) )
>
> thanks
> christian
> --
> http://mail.python.org/mailman/listinfo/python-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20110728/e9fba672/attachment.html>