3
\$\begingroup\$

Given sample_size many arrays of length dim. For each index from 1 to dim, i want to give a list of indices, where no sample contained in both indexes 1s. The code is really slow and i want to improve the performance.

# Test set

dim = 10000
sample_size = 1000

from random import *

randBinList = lambda n: [randint(0,1) for b in range(1,n+1)]

samples = [randBinList(dim) for s in xrange(sample_size)]


# Find all variables that are not both 1 in one sample

node_neighbours = {}
for node in xrange(1,dim+1):
    node_neighbours[node] = []
    for node2 in xrange(1,dim+1):
        if node != node2:
            test_failed = False
            for s in samples:
                v1 = s[node-1]
                v2 = s[node2-1]
                if v1 == 1 and v2 == 1:
                    test_failed = True
                    break
            if not test_failed:
                node_neighbours[node].append(node2)
    #print node, ":", node_neighbours[node]
\$\endgroup\$
  • \$\begingroup\$ I'm confused on why it would be necessary to check through every pairing to see if all sample values for each pairing contain 1s. What I get is that if an index has all 1s for all of the samples, then it it is a neighbour for every other index that also has all 1s for all of the samples. You would just need to loop through each index for each of the samples once (and construct your pairs after ward). \$\endgroup\$ – abrarisme Nov 22 '16 at 21:47
  • \$\begingroup\$ Two indices are neighbors if the value is never 1 in both indices at the same time in any sample. \$\endgroup\$ – user3613886 Nov 22 '16 at 22:11
2
\$\begingroup\$

First off, I don't understand why you so much time dealing with off-by-one indices that you created in the first place:

for node in xrange(1,dim+1):
    for node2 in xrange(1,dim+1):
        for s in samples:
            v1 = s[node-1]
            v2 = s[node2-1]
            if v1 == 1 and v2 == 1:

You could simply write xrange(dim) and s[node] and s[node2]. If you want a 1-based indexing when storing the results, you can still use node + 1 and node2 + 1 when appending the results.

You can also take advantage of the fact that node being a neighbour of node2 will imply that node2 will be a neighbour of node and cut down half of your computations (and a test as well):

for node in xrange(dim):
    for node2 in xrange(node + 1, dim):
        test_failed = False
        for s in samples:
            v1 = s[node]
            v2 = s[node2]
            if v1 == 1 and v2 == 1:
                test_failed = True
                break
        if not test_failed:
            node_neighbours[node + 1].append(node2 + 1)
            node_neighbours[node2 + 1].append(node + 1)

Other tiny improvements includes removing the test_failed flag by using the for ... else construct and testing equality with the extended comparisons:

for node in xrange(dim):
    for node2 in xrange(node + 1, dim):
        for s in samples:
            v1 = s[node]
            v2 = s[node2]
            if v1 == v2 == 1:
                break
        else:
            node_neighbours[node + 1].append(node2 + 1)
            node_neighbours[node2 + 1].append(node + 1)

But a bigger improvement can be achieved using the C core of Python instead of these 2 for loops. Because they perform exactly what itertools.combinations does:

for node1, node2 in itertools.combinations(xrange(dim), 2):
    for s in samples:
        if s[node1] == s[node2] == 1:
            break
    else:
        node_neighbours[node1 + 1].append(node2 + 1)
        node_neighbours[node2 + 1].append(node1 + 1)

Also note that all the provided snippets seems to take for granted that lists for each nodes has already been populated in node_neighbours. This is easily achieved using collections.defaultdict as such:

node_neighbours = defaultdict(list)

You should also wrap this code into a function to better separate the "initialization" or generation of test data from the actual computation. And testing this function should be done in an if __name__ == '__main__': clause:

import itertools
from collections import defaultdict


def pairs_never_both_one(samples, dim=None):
    if dim is None:
        dim = len(samples[0])

    node_neighbours = defaultdict(list)
    for node1, node2 in itertools.combinations(xrange(dim), 2):
        for s in samples:
            if s[node1] == s[node2] == 1:
                break
        else:
            node_neighbours[node1 + 1].append(node2 + 1)
            node_neighbours[node2 + 1].append(node1 + 1)

    return node_neighbours


if __name__ == '__main__':
    from random import randint

    dim = 10000
    sample_size = 1000
    samples = [[randint(0, 1) for _ in xrange(dim)] for _ in xrange(sample_size)]
    print pairs_never_both_one(samples, dim)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.