improving a huge double-for cycle

[Harald Luessen]

On Thu, 18 Sep 2008 Bruno Desthuilliers wrote:

># Harald : uncomment this and run test_results. As far as I can tell, it
># doesn't yields the expected results
>
>## IN7 = IN[:]
>## def sortk7(n):
>##     return n.coordinates[0]
>
>## def doubles7():
>##     "is ordering better ? - Nope Sir, it's broken..."
>##     IN7.sort(key=sortk)
>##     SN = []
>##     sn_append = SN.append
>##     in_len = len(IN)
>##     for i in xrange(in_len):
>##         node_i = IN[i]
>##         coords_i = node_i.coordinates
>##         for j in xrange(i+1, in_len):
>##             if coords_i[0] == IN[j].coordinates[0]:
>##                 if coords_i[1] == IN[j].coordinates[1]:
>##                     sn_append(node_i)
>##             else:
>##                 break
>##     return SN
...
>Results here (py2.5, gentoo linux, athlonxp1800, 512 ram):
>
> >>> test_results()
>True
> >>> test_times()
>doubles0 : 1.55667901039
>doubles1 : 0.719144105911
>doubles2 : 0.703393936157
>doubles3 : 0.700654983521
>doubles4 : 0.706257104874
>doubles5 : 0.528184890747
>doubles6 : 0.461633205414
>doubles8 : 0.0134379863739
>doubles9 : 0.0108540058136

When you change my code then do it right. :-)
You forgot to change the IN to IN7 at _every_ place.
And the sortk should be sortk7 in _both_ places.

I never let the code run before myself. I just wrote it 
in the newsreader. But now i did and I have a second 
version as bonus.


IN7 = IN[:]

def sortk7(n):
    return n.coordinates[0], n.coordinates[1]

def doubles7():
    IN7.sort(key=sortk7)
    SN = []
    sn_append = SN.append
    in_len = len(IN7)
    for i in xrange(in_len):
        node_i = IN7[i]
        coords_i = node_i.coordinates
        for j in xrange(i+1, in_len):
            if coords_i[0] == IN7[j].coordinates[0]:
                if coords_i[1] == IN7[j].coordinates[1]:
                    sn_append(node_i)
            else:
                break
    return SN


def comp7( x, y ):
     return cmp( x.coordinates, y.coordinates )

def doubles7a():
    IN7.sort( comp7 )
    SN = []
    sn_append = SN.append
    in_len = len(IN7)
    for i in xrange(in_len):
        node_i = IN7[i]
        for j in xrange(i+1, in_len):
            node_j = IN7[j]
            if comp7( node_i, node_j ) == 0:
                sn_append(node_i)
            else:
                break
    return SN


Here are the results. (py2.5, WindowsXP, Pentium4, 2.6GHz, 1.5GB):
My version is not so bad.

doubles0 : 1.03830598582
doubles1 : 0.47943719104
doubles2 : 0.487412506338
doubles3 : 0.475924733451
doubles4 : 0.466548681466
doubles5 : 0.340487967046
doubles6 : 0.278480365521
doubles7 : 0.0953190978183
doubles7a : 0.0784233750379
doubles8 : 0.010236496538
doubles9 : 0.00742803903848


Harald