Return to Revisions

Python has PEP 8, a well-followed coding standard. It's a good idea to stick to it. One point is that most things, global constants and classes asside, should be snake_case.

You don't use FromGridToList, so chuck it.

Your from_list_to_grid is only ever used for one of its results, so split it up. I'd also inline it. Note that you can use // for flooring division.

The calculation l_ - (l_//U)*U is just l_ % U.

This gives

di = np.array([np.abs(l//U - i//U) for i, x in enumerate(Ulist)])
di = np.minimum(di, U-di)

dj = np.array([np.abs(l%U - i%U) for i, x in enumerate(Ulist)])
dj = np.minimum(dj, U-dj)

Then you can move the abs out and vectorize:

di = np.abs(l//U - Ulist_indices//U)
di = np.minimum(di, U-di)

dj = np.abs(l%U - Ulist_indices%U)
dj = np.minimum(dj, U-dj)

This takes ~0.04 seconds for U=25 for me, handily defeating alexwlchan's.

It takes ~0.6 seconds seconds for U=60. Caching Ulist_indices//U and Ulist_indices%U divides that by 3.

Now we can start vectorizing the whole loop, but it's so large that we seem to lose memory locality and it actually doesn't help!

Here's the code:

from __future__ import print_function

import numpy
from numpy import minimum, newaxis

def gen_distances(ulist):
    u = len(ulist) ** 0.5
    indices = numpy.arange(u ** 2, dtype=float)

    indices_div_u = indices // u
    indices_mod_u = indices %  u

    for val in ulist:
        di = numpy.abs(val // u - indices_div_u)
        dj = numpy.abs(val %  u - indices_mod_u)

        di = minimum(di, u-di)
        dj = minimum(dj, u-dj)

        yield numpy.sqrt(di**2 + dj**2)

def main():
    ulist = numpy.arange(60**2, dtype=float)

    import time
    start_time = time.time()
    dist_array = numpy.vstack(gen_distances(ulist))
    print(time.time() - start_time, 'seconds')

main()
#>>> 0.19192290306091309 seconds

This takes me ~6 seconds for U=150, and I run out of memory if I go significantly higher.