To count number of quadruplets with sum = 0

Paul Rubin http
Sat Mar 17 14:58:38 EDT 2007


bearophileHUGS at lycos.com writes:
>     for x in e:
>         for y in r:
>             if -x-y in h:
>                 sch += h[-x-y]

I wonder whether

    g = h.get
    for x in e:
        for y in r:
            if -x-y in h:
                sch += g(-x-y, 0)

might be a little bit faster.  Also, -x-y could be saved in a variable.

It's unfortunate that array.array objects don't support the .sort()
operation.  It would be interesting to compare the sorting-based scheme
with the hashing-based one under psyco.  O(n**2*log(n)) local memory 
references might be faster than O(n**2) hash operations and random
lookups that almost always miss the cache.



More information about the Python-list mailing list