# Internal method to calculate the distance between all nodes in Kruskal's Importance (Driver) Algorithm

I've been trying to reduce the indentation from a method in my code. The solution will probably be unrelated to the language, in this case python, although it may rely on some python specific libraries e.g. itertools.

The code below is part of this implementation of Kruskal's algorithm.

def generate_diff(self, ndarr, arr):
"""
Internal method to calculate the difference between all points
"""
l = ndarr.shape
pij = np.empty((l,l,)) * np.nan
pijm = np.empty((l,l,l)) * np.nan
for i in range(l):
for j in range(l):
if i != j:
pij[i, j] = self.pcor_squared(np.array([ndarr[:,i], arr, ndarr[:,j]]))
for m in range(l):
if m != i and m != j and m > j:
pijm[m, i, j] = self.pcor_squared(np.array([ndarr[:,i], arr, ndarr[:,j], ndarr[:, m]]))
return (l, pij, pijm)


As you can see it's looping through the length of the shape 3 times! (in creating i, j, m).

ndarr and arr are just a two dimensional numpy array and a one dimensional numpy array. The specs in the file will enable you to hit the method very quickly if you add an assert False and a run py.test --pdb from the command.

I've tried changing the first line to for i, j in it.combinations(range(l), 2): and doing both sides of the square of the matrix simulataneously with:

pij[i, j] = self.pcor_squared(np.array([ndarr[:,i], arr, ndarr[:,j]]))
pij[j, i] = self.pcor_squared(np.array([ndarr[:,j], arr, ndarr[:,i]]))


but it's a bit off (i.e. gives wrong numbers in the spec).

In short I'm trying to reduce the complexity by making the code linear and hopefully making it more performant by removing the looping. A better understanding of matrices may be key to this.

• This statement seems to contradict wiki.q-researchsoftware.com/wiki/…, specifically: "The time required to compute Kruskal analysis results increases exponentially with the number of independent variables" – Rambatino Oct 3 '16 at 20:12
• There is more than one Kruskal algorithm ... I unfortunately projected my current learning stuff for the next exam onto you and thought you'd have implemented the Minimum Spanning Tree algorithm... alas that's a completely different problem :/ I think it's safe to ignore what I said there :) – Vogel612 Oct 3 '16 at 20:16
• Yeah the guy apparently wrote loads of these algorithms! Still, you didn't need to delete your initial comment ha! – Rambatino Oct 3 '16 at 20:58
• I had the same concern as Vogel612 — "Kruskal's algorithm" always refers to his minimum spanning tree algorithm in my experience. Please can you update the title and question accordingly, and add a link to a description of the algorithm you're trying to implement. In particular, is it the Kruskal–Wallis one-way analysis of variance? – Gareth Rees Oct 4 '16 at 9:08
• Hi @GarethRees I have renamed the title – Rambatino Oct 4 '16 at 9:48

You can use comprehensions.

A comprehension is a special way to write a for loop, or nested for loops. This is a functional part of the language and is derived from set-builder notation. If we look at Wikipedia we'll see:

$S = \{2 \dot{} x | x \in \mathbb{N}, x^2 > 3\}$

In imperative Python this would be:

from itertools import count

S = []
for x in count(0):
if x ** 2 > 3:
S.append(2 * x)
...


Ignoring the inability for this function to complete, that's a bit long winded. Instead we can use a list comprehension:

S = [
2 * x
for x in count(0)
if x ** 2 > 3
]


This allows us to write what would be multiple indentations of code in one line. And so take the code:

for i in range(l):
for j in range(l):
if i != j:
# Do stuff


Using comprehensions we can change it to:

for i, j in [
(i, j)
for i in range(l)
for j in range(l)
if i != j]:
# Do stuff


This allows a large reduction in the amount of tabs. As we can just use two comprehensions.

for i, j in [
(i, j)
for i in range(l)
for j in range(l)
if i != j]:
pij[i,j] = self.pcor_squared(np.array([ndarr[:,i], arr, ndarr[:,j]]))
for m in [m for m in range(l) if m != i and m != j and m > j]:
pijm[m,i,j] = self.pcor_squared(np.array([ndarr[:,i], arr, ndarr[:,j], ndarr[:,m]]))


I'd like to point out two ways to improve on this. As we are currently using list comprehensions that build an entire list before using the first item we can change them to generator comprehensions. This is as simple as changing the [] to (). This would allow us to use the list $\{2 \dot{} x | x \in \mathbb{N}, x^2 > 3\}$, for example:

import itertools

S = (2 * x for x in itertools.count(0) if x ** 2 > 3)
print(list(itertools.islice(S, 10)))


The second way to improve the above is to move the two checks m != j and m > j into the range. This would change the range to range(j + 1, l) and just leave the m != i.

And so you can get:

for i, j in (
(i, j)
for i in range(l)
for j in range(l)
if i != j):
pij[i,j] = self.pcor_squared(np.array([ndarr[:,i], arr, ndarr[:,j]]))
for m in (m for m in range(j + 1, l) if m != i):
pijm[m,i,j] = self.pcor_squared(np.array([ndarr[:,i], arr, ndarr[:,j], ndarr[:,m]]))

• In your last code block it should be for m in (m for m in range(j + 1, l) if m != i) or just for m in (x)range(j+1,l): if m == i: continue where the xrange is for Python 2.x of course. – Graipher Oct 4 '16 at 6:38
• @Graipher thanks I didn't notice I missed the for. – Peilonrayz Oct 4 '16 at 6:54