Another optimization request :-)

[Terry Reedy]

jeffg wrote:
> If anyone wants to take this on... I would really really like to have
> the spring_layout modified to support multi-threading if at all
> possible.
> My test data is 20,000, which makes this process 20,000 x 20,000 or
> 400,000,000 (400 million) calculations.  This is taking somewhere
> between 2-3 hours an iteration.
> I plan to plot out over 1,000,000 data points or more, which would put
> this at 1,000,000,000,000 (1 trillion) calculations.  Any help in
> making this more efficient would be much appreciated.
> 
> def spring_layout(G, iterations=50, dim=2, node_pos=None,
> verbose=False):
>     """Spring force model layout"""
>     if node_pos==None :  # set the initial positions randomly in 1x1
> box
>         vpos=random_layout(G, dim=dim)
>     else:
>         vpos=node_pos
>     if iterations==0:
>         return vpos
>     if G.order()==0:
>         k=1.0
>     else:
>         k=N.sqrt(1.0/G.order()) # optimal distance between nodes
>     disp={}         # displacements
> 
>     # initial "temperature" (about .1 of domain area)
>     # this is the largest step allowed in the dynamics
>     # linearly step down by dt on each iteration so
>     # on last iteration it is size dt.
>     t=0.1
>     dt=0.1/float(iterations+1)
>     for i in range(0,iterations):
>         for v in G:
>             if verbose==True:
>                 print("Interation: " + str(i + 1) + ", Calculating: "
> + str(v.encode('iso-8859-15', "replace")))
>             disp[v]=N.zeros(dim)
>             for u in G:
>                 delta=vpos[v]-vpos[u]

Let n = len(vpos).  I believe there are only n-1 different deltas, dns, 
and deltafs, where as n**2 calculations are made.

>                 dn=max(sqrt(N.dot(delta,delta)),0.01)
>                 # repulsive force between all
>                 deltaf=delta*k**2/dn**2
>                 disp[v]=disp[v]+deltaf
>                 # attractive force between neighbors
>                 if G.has_edge(v,u):
>                     deltaf=-delta*dn**2/(k*dn)
>                     disp[v]=disp[v]+deltaf
> 
>         # update positions
>         for v in G:
>             l=max(sqrt(N.dot(disp[v],disp[v])),0.01)
>             vpos[v]=vpos[v]+ disp[v]*t/l
>         t-=dt
>     return vpos

That aside, array calculations like this should be *much* faster with 
numpy.  Or try compiling (with weave or Cython, for instance).