Iterative uniform recombination of integer lists in python with numba

Question

I have a list of N integers and I iteratively take two integers at random, which are not at the same position in the list and uniformly recombine their binary representation, e.g. in intList = [1,4,1,5] (N=4) the number on the second and third position is chosen, aka 4 & 1, and their binary represenations 4=100 & 1=001 is uniformly recombined. Uniformly recombined means that I chose either the 1 or the 0 of the first position, one of the two 0's of the second position and either the 0 or 1 of the third position. This could result in 000 or 101 or 100 or 001. The result is saved as integer in the list. In each iteration I do this recombination for all N integers. This happens in a function with a numba decorator. My code is:

@nb.njit()
def comb():
    iterations = 100000
    N = 1000
    intList = list(range(N))   # this is just an example of possible integer lists
    l = 10   # length of the largest binary representation. 
    intList_temp = [0]*N
    for _ in range(iterations):
        for x3 in range(N):
            intList_temp[x3] = intList[x3]
        for x3 in range(N):
            randint1 = random.randint(0, N - 1)
            randint2 = random.randint(0, N - 1)
            while randint1 == randint2:
                randint1 = random.randint(0, N - 1)
                randint2 = random.randint(0, N - 1)
            a = intList[randint1]
            b = intList[randint2]
            c = a ^ ((a ^ b) & random.randint(0, (1 << l) - 1))
            intList_temp[x3] = c
        for x3 in range(N):
            intList[x3] = intList_temp[x3]
    return intList

print(timeit(lambda: comb(), number=1))
>>>2.59s

My question is, can this be improved?

Answer 1

No significant performance improvement but cleaner code.

Because temp_list is overwritten element-wise you can create it once and then leave it. At the end of each iteration you can then copy the entire list into int_list for the next iteration.

Similarly you can simplify creating the random ints a and b a bit. There are a lot of ways that get close to this in numpy but nothing I can find that beats the naive sampling directly works with numba and numba beats any overall solution I can think of without it.

Unfortunately (or maybe fortunately depending on your view), the numba compiler is compiling it down to the best solution I can think of for both your original version and this. Only difference is readabilitiy:

@nb.njit()
def comb(int_list, l, iterations):
    n = len(int_list)

    temp_list = int_list

    for _ in range(iterations):
        for i in range(n):
            a, b = 0, 0
            while a == b:
                a = random.randint(0, n - 1)
                b = random.randint(0, n - 1)

            temp_list[i] = a ^ ((a ^ b) & random.randint(0, l))

        int_list = temp_list

    return int_list

print(timeit(lambda: comb(list(range(1000)), (1 << 10) - 1, 100000), number=10))

Answer 2

One obvious improvement is the repeated calculations of N-1 and 1<<l - 1 -- those can be calculated once outside the loop and put in variables.

Another wasted effort is the triple initialization of intList_temp. There is no reason to set it to 0, set it to intList, then set it to the actually calculated values.

Also that while loop to ensure the values are distinct is unnecessary. There's plenty of code out there to generate two distinct random numbers with just two random calls. (Hint: if the first random number is chosen arbitrarily, how many valid choices are there for the second random number?)

But I don't think either of these will make much of a difference in speed.

Have you profiled this?

Answer 3

for x3 in range(N):
            intList_temp[x3] = intList[x3]

and

for x3 in range(N):
            intList[x3] = intList_temp[x3]

look pretty messy, I'm not proficient in python, but there should be an implementation of copying a vector much faster.