Increasing efficiency on a network randomization algorithm on Julia

user_11607243 0
Viewed 55

My problem is the following. I have the adjacency matrix Mat for a neural network. I want to randomize this network in the sense that I want to choose 4 notes randomly (say i,j,p,q) such that i and p are connected (which means Mat[p,i] = 1) and j and q are connected AND i and q are not connected (Mat[q,j] = 0)and j and p are not connected. I then connect i and q and j and p and disconnect the previous nodes. In one run, I want to do this 10^6 times.

So far I have two versions, one using a for loop and one recursively.

newmat = copy(Mat)
for trial in 1:Niter
        count = 0
        while count < 1
            i,j,p,q = sample(Nodes,4,replace = false) #Choosing 4 nodes at random   
            if (newmat[p,i] == 1 && newmat[q,j] == 1) && (newmat[p,j] == 0 && newmat[q,i] == 0)
                newmat[p,i] = 0
                newmat[q,j] = 0
                newmat[p,j] = 1
                newmat[q,i] = 1
                count += 1
            end 
        end
end

Doing this recursively runs about just as fast until Niter = 10^4 after which I get a Stack Overflow error. How can I improve this?

julia recursion for-loop
1 Answers

I assume you are talking about a recursive variant of the for trial in 1:Niter.

To avoid stack overflows like this, a general rule of thumb (in languages without tail recursion elimination) is to not use recursion unless you know the recursion depth will not scale more than logarithmically.

The cases where this is applicable is mostly algorithms that are like tree traversals, with a "naturally occuring" recursive structure. Your case of a simple for loop can be viewed as the degenerate variant of that, with a "linked list" tree, but is not a all natural.

Just don't do it. There's nothing bad about a loop for some sequential processing like this. Julia is an imperative language, after all.

(If you want to do this with a recursive structure for fun or exercise: look up trampolines. They allow you to write code structured as tail recursive, but with the allocation happening by mutation and on the heap.)

user_13462760
Related