I learned ruby last year, and I am curious to see if I can actually do the things ruby is meant to help us do. I have working code that does what I describe below, but it is very slow, and I would love to learn from some ruby (or "FP") gurus how to take my relationship with execution time "to the next level."

In the end, it seems to be a question of how to "pre-compile" a lambda?

Here is the essential problem. You have a large graph, V, which you can represent as a (symmetric) matrix, V[i,j], telling you which points are connected to each other. It might be, for example, a 10^3 lattice. You also have a (much smaller) "diagram", call it D, which you can also represent as a (symmetric) matrix, D[a,b]. A diagram might be, for example, a three-vertex loop:

Code: Select all

`[ 0 1 1 `

1 0 1

1 1 0 ]

To "apply" the diagram D to the graph V means to sum up a product of V[i,j] elements in a particular fashion. In the case of the loop above, you sum:

Code: Select all

`V[i,j]*V[j,k]*V[k,i]`

over all values of i, j and k. In other words, D gives the patterns of the indicies in the sum.

I thought a long time about how to do this in the general case. Here was my solution.

First, we need a good way to sum over an arbitrary number of indicies (the dimension of the diagram D); you want to be able to pass a block to the center of all the loops. I built the following (m_inner is the dimension of the graph V):

Code: Select all

` def all_sum(n_left,m_inner,block,running=[])`

# sums from 0 to m_inner-1, n_left times (pass n, at the top level,

# where n is the number of verticies in the diagram D)

# (returns an *object* -- a lambda -- that can be executed by call)

# at the center of the loop, passes the call structure through (i.e.,

# on the 3rd iteration of the first loop, 2nd iteration of the second, the block

# is passed [2,1] )

if n_left == 1 then # (if there's only one sum to do, do it)

lambda {

counter = 0

m_inner.times { |i|

counter += block.call(running+[i])

}

counter

}

else # (do the lower sum)

lambda {

counter = 0

m_inner.times { |i|

counter += all_sum(n_left-1,m_inner,block,running+[i]).call

}

counter

}

end

end

Then, of course, you need to define the block at the center. That's just the product defined by the diagram D. Here's the block I pass:

Code: Select all

` inner_summand = lambda { |v_index|`

running_prod=1.0

(@n-1).times { |i|

(i+1).upto(@n-1) { |j|

running_prod *= v.net[v_index[i],v_index[j]]**(@g[i,j])

}

}

running_prod

}

Where @n is the dimension of the diagram D (e.g., in the three-loop above, it's 3), @g is the matrix of the diagram D, and v.net is the matrix associated with the graph V.

If all that makes sense, here is the issue. This is extremely slow. Is there an obvious way to speed it up? It seems like my inner block is being executed over and over again, but there should be a way to speed it up?