-3

I'm iterating 4 million times (for a project). This is taking forever to do. I was wondering how I can go faster.

numbers = [0,1]
evenNumbers = []
y = 0
l = 0
for x in range (1,4000000):
   l = numbers[x-1] + numbers[x]
   numbers.append(l)

for k in numbers:
   if k % 2 ==0:
      evenNumbers.append(k)

for n in evenNumbers:
   y += n

print(y)
Coder
  • 1
  • 1
    The list append operation is the bottleneck, you might want to take a look at these question: [Reserve memory for list in Python?](https://stackoverflow.com/q/537086/13253010), [Python equivalent of vector::reserve()](https://stackoverflow.com/q/7730754/13253010) – thedemons Nov 11 '22 at 23:36
  • 2
    You are iterating 12 million times, not 4. Why are you not doing all the calculations in a single iteration? – DeepSpace Nov 11 '22 at 23:36
  • 1
    The 1 millionth Fibonacci number already has 208988 digits. By the time you get to 4000000 that grows to 835951. For millions of steps you are doing calculations with hundreds of thousands of digits -- and consuming enormous amounts of memory in the process. It is surprising that you don't get out of memory errors. – John Coleman Nov 11 '22 at 23:52

2 Answers2

2

This is going to be very slow regardless due to the how big the numbers are getting, but you can speed it up significantly by just not storing all the intermediate values:

m, n = 0, 1
y = 0
for _ in range(1, 4000000):
    m, n = n, m + n
    if n % 2 == 0:
        y += n

print(y)
Samwise
  • 68,105
  • 3
  • 30
  • 44
  • How significantly? – Peter Wood Nov 11 '22 at 23:46
  • For smaller values where you can fit it all in memory, the speedup is modest but measurable (the time savings is mostly coming from spending less CPU time in the Python interpreter and the heap manager). Once that list of giant numbers starts getting paged to disk and you hit that I/O bottleneck, the difference is going to be quite a bit less modest, but I'm not going to thrash my PC for the sake of measuring it, and at that point it's going to vary quite a bit by system specs anyway. :) – Samwise Nov 11 '22 at 23:51
  • I think the size of the numbers in the sequence grows exponentially. Running the original program in a standard laptop might not even be possible. – C-3PO Nov 11 '22 at 23:54
  • By the way, I think this problem is simple enough to have an analytical solution. I imagine it being a question in a Coding Challenge from a big tech firm. What could be the answer? – C-3PO Nov 11 '22 at 23:56
0

You should just compare the time it takes for each function here to complete, as they are the three different ways that most would approach iteration.

import time

def foreach(arr):
    for i in range(len(arr)):
        print(arr[i])

def forin(arr):
    for i in arr:
        print(i)

def whileloop(arr):
    i = 0
    while i < len(arr):
        print(arr[i])
        i += 1
        
def main():
    arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

    start = time.time()
    foreach(arr)
    end = time.time()
    print("foreach: ", end - start)

    start = time.time()
    forin(arr)
    end = time.time()
    print("forin: ", end - start)

    start = time.time()
    whileloop(arr)
    end = time.time()
    print("whileloop: ", end - start)

if __name__ == "__main__":
    main()
kryozor
  • 315
  • 1
  • 7