Styjun

My problem is very similar to this post:
Python : count the number of changes of numbers

But since I cannot comment yet, I would like to know if there is a faster way?

My code is significantly the same as in the link, but the ranges of i and j are way much bigger (around one million in total) , meaning that it takes a significantly larger time to count (more than a day!)

It is most definitely a better idea to save all the transition counts to a data structure instead of counting the appearances of each individual transition. It could be something like this:

def count_transitions(numbers):
 n = max(numbers)
 transitions = [[0] * (n + 1) for _ in range(n + 1)]
 for i in range(len(numbers) - 1):
 n1 = numbers[i]
 n2 = numbers[i + 1]
 transitions[n1][n2] += 1
 return transitions

An example of how you could use it:

test_data = [1, 0, 1, 0, 1, 2, 0, 2, 0, 1, 1]
test_result = count_transitions(test_data)
for i, row in enumerate(test_result):
 for j, count in enumerate(row):
 print(f'i -> j: count')

Output:

0 -> 0: 0
0 -> 1: 3
0 -> 2: 1
1 -> 0: 2
1 -> 1: 1
1 -> 2: 1
2 -> 0: 2
2 -> 1: 0
2 -> 2: 0

Now, another matter is making this fast. This algorithm should already be much faster, because it has linear complexity instead of cubic, but we can use a couple of tools to make it still better. For example, using NumPy you could do it just like this:

import numpy as np

def count_transitions_np(numbers):
 numbers = np.asarray(numbers)
 n = numbers.max()
 transitions = np.zeros((n + 1, n + 1), dtype=np.int32)
 np.add.at(transitions, (numbers[:-1], numbers[1:]), 1)
 return transitions

Or you can use Numba with something like this:

@nb.njit
def count_transitions_nb(numbers):
 n = 0
 for num in numbers:
 n = max(num, n)
 transitions = np.zeros((n + 1, n + 1), dtype=np.int32)
 for i in range(len(numbers) - 1):
 n1 = numbers[i]
 n2 = numbers[i + 1]
 transitions[n1, n2] += 1
 return transitions

Finally, yet another option is to build a sparse matrix with SciPy. Note this is not the same as a dense matrix, but you may be able to work with it too.

import numpy as np
import scipy.sparse

def count_transitions_sp(numbers):
 numbers = np.asarray(numbers)
 n = numbers.max()
 v = np.ones(len(numbers) - 1, dtype=np.int32)
 return scipy.sparse.coo_matrix((v, (numbers[:-1], numbers[1:])), (n + 1, n + 1))

And now a small benchmark:

import random

# Generate input data
random.seed(100)
numbers = [random.randint(0, 1000) for _ in range(1000000)]

# Check results are correct
result1 = count_transitions(numbers)
result2 = count_transitions_np(numbers).tolist()
result3 = count_transitions_nb(numbers).tolist()
result4 = count_transitions_sp(numbers).todense().tolist()
print(result1 == result2)
# True
print(result1 == result3)
# True
print(result1 == result4)
# True

# NumPy version of data for NumPy, Numba and SciPy
numbers_np = np.asarray(numbers)
# Time it with IPython
%timeit count_transitions(numbers)
# 178 ms ± 633 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit count_transitions_np(numbers_np)
# 80.7 ms ± 663 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit count_transitions_nb(numbers_np)
# 5.36 ms ± 240 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit count_transitions_sp(numbers_np)
# 4.05 ms ± 47.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

As you see, Numba can be really fast, and sparse matrices are quick to build too if you can use them.