How to optimize the performance of nested loops with dynamic data structure updates in Python?

Question

1. How can I optimize this code for better performance while maintaining the correctness of dynamic updates?

2. Is there a way to restructure the nested loop or use a different approach to reduce the time complexity?

data = [i for i in range(1, 101)]  # Example dataset
results = []

for i in range(len(data)):
    for j in range(i + 1, len(data)):
        # Perform some operation
        if data[i] % 2 == 0 and data[j] % 3 == 0:
            results.append((data[i], data[j]))
            # Update the data structure dynamically
            data[i] = data[i] * 2  
            data[j] = data[j] + 1  

print(results)

What I Tried:

1. Tracking Updates Manually:
   I attempted to maintain a separate list to track which indices in data were updated during each iteration, but this became cumbersome and added overhead.

2. Precomputing Valid Pairs:
   I tried generating all valid pairs (data[i], data[j]) before running the loop to eliminate redundant checks. However, this failed because precomputing doesn’t account for the dynamic updates happening inside the loop.

3. Using Sets Instead of Lists:
   I replaced data with a set to reduce the cost of lookups and updates. While this improved performance slightly, it introduced new challenges, like preserving the order and accessing elements by index.

---

What I Expected:

1. Improved Performance:
   I was hoping to reduce the runtime of the nested loops, especially for datasets with millions of elements.

2. Preservation of Correctness:
   I expected that the results would remain accurate and consistent, even with the dynamic updates to data.

3. A Scalable Solution:
   I wanted a scalable approach that could handle larger datasets efficiently without requiring significant reworking of the core logic.

Answer 1

There are some shortcuts to take here:

1. When the if condition is true, then we know that data[j] is a multiple of 3. But as that if block adds one to data[j], this will no longer be the case when the outer loop has made a next iteration and data[j] is visited again. By consequence the if condition can only be true for one specific iteration of the outer loop. The first outer iteration where the if condition could be true is when data[i] is even, which in the example data occurs when i is 1. In the general case we can find that i with a next() call. By consequence we can eliminate the outer loop and take i as a constant. We can remove the condition data[i] % 2 == 0 as it will be true. The reduced code becomes:

   results = []
   n = len(data)
   i = next((i for i, val in enumerate(data) if val % 2 == 0), n)
   for j in range(i + 1, n):
       if data[j] % 3 == 0:
           results.append((data[i], data[j]))
           data[i] = data[i] * 2  
           data[j] = data[j] + 1  
   

   This represents the main efficiency gain, as now there are no nested loops. This has a time complexity of O(𝑛), where 𝑛 is the size of the data list.

2. As the update with data[j] = data[j] + 1 no longer affects the result, we can remove it.

3. As data[i] is not visited in the remaining loop, we might as well use a constant for it -- we could call it coeff, with an initial value of data[i]. This leads to this code:

   results = []
   n = len(data)
   i = next((i for i, val in enumerate(data) if val % 2 == 0), n)
   if i < n:
       coeff = data[i]
   for j in range(i + 1, n):
       if data[j] % 3 == 0:
           results.append((coeff, data[j]))
           coeff = coeff * 2  
   

4. We can turn this into a list comprehension, calculating the coefficient as a multiplication with a power of 2, where the exponent is the index of the pair being appended to the result:

   n = len(data)
   i = next((i for i, val in enumerate(data) if val % 2 == 0), n)
   if i < n:
       coeff = data[i]
   multiples = (data[j] for j in range(i + 1, n) if data[j] % 3 == 0)
   results = [
       (coeff * (1 << exponent), multiple)
       for exponent, multiple in enumerate(multiples)
   ]
   

5. As the iteration over multiples continues after where the first iteration with next stopped, we could use one iterator for both. For example like this:

   mod = 2  # First we look for a multiple of 2
   multiples = (val for val in data if val % mod == 0)
   coeff = next(multiples, 0)  # first multiple of 2
   mod = 3  # from now on look for multiples of 3
   results = [
       (coeff * (1 << exponent), multiple)
       for exponent, multiple in enumerate(multiples)
   ]
   

Answer 2

I originally just thought that a move of the if data[i] % 2 == 0 out of the inner loop would speed things up and that halved the execution time.

I then ran the solution from user trincot and it was an order of magnitude faster than mine. I looked at his code and could not work out what was happening, and, strangely enough, his explanation went over my head.

It was only when I added print statements to the original code and further examples, that it dawned on me that: after the first finding of an even, the loop through the multiples of three will add one to them so multiples of three are only ever found for the first multiple of 2. That is what user trincot says up front, but i could not understand it until I worked it out for myself.

I put the other two solutions as well as mine into functions and timed them. I was pleasantly surprised to find that my use of for loops and append was consistently slightly faster than trincots' while doing essentially the same thing.

My version

def gen2(data):
    "User Paddy3118, after first find of % 3's, will never be found again"
    results = []
    div = 2
    for val in data:
        if val % div == 0:
            if div == 2:
                val2 = val
                div = 3
            else:
                results.append((val2, val))
                val2 *= 2
    return results

Timings

gen Original TIMING
193 µs ± 4.3 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

gen2 User Paddy3118, after first find of % 3's, will never be found again TIMING
5.37 µs ± 220 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

gen3 User trincot TIMING
6.74 µs ± 194 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

Using Python 3.11.3 on Windows

Supplemental

As asked for in the comment by user no comment:

...

def gen3(data):
    "User trincot"
    results = []

    mod = 2  # First we look for a multiple of 2
    multiples = (val for val in data if val % mod == 0)
    coeff = next(multiples, 0)  # first multiple of 2
    mod = 3  # from now on look for multiples of 3
    results = [
        (coeff * (1 << exponent), multiple)
        for exponent, multiple in enumerate(multiples)
    ]
    return results

def gen4(data):
    "User no comment"
    it = iter(data)
    return [
        (a, b)
        for a in it if not a % 2
        for a in [a // 2]
        for b in it if not b % 3
        for a in [a * 2]
    ]

...
# %%
# Executed in vscode/Spyder ipython cell to get %timeit
for func in (gen, gen2, gen3, gen4):
    print(f"{func.__name__} {func.__doc__} TIMING")
    %timeit func([i for i in range(1, 101)])
    print()

Revised timings

gen Original TIMING
191 µs ± 5.32 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

gen2 User Paddy3118, after first find of % 3's, will never be found again TIMING
5.64 µs ± 282 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

gen3 User trincot TIMING
6.99 µs ± 147 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

gen4 User no comment TIMING
4.98 µs ± 94.6 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

And the fastest is...