python - Difference in run time complexity of two seemingly similar solutions

Question

I was trying to solve an assignment and wrote a solution that seems very close to the solution I found online when I set out to find more efficient solutions.

This is the assignment statement

The goal of this problem is to implement a variant of the 2-SUM algorithm covered in this week's lectures.

The file contains 1 million integers, both positive and negative (there might be some repetitions!).This is your array of integers, with the ith row of the file specifying the ith entry of the array.

Your task is to compute the number of target values t in the interval [-10000,10000] (inclusive) such that there are distinct numbers x,y in the input file that satisfy x+y=t The variable all_ints is a list containing all the integers

hashtable = set(all_ints)
min_t = -1024
max_t = -min_t + 1

solutions = 0
k = 0

from time import time

# Solution 1 that I wrote
t0 = time()
for n in range(min_t, max_t):
    solutions+=1 if any([True if 2*i!=n and n-i in hashtable else False for i in hashtable]) else 0


# Solution 2 that I found online
t1 = time()
solutions2 = sum(1 for n in range(min_t, max_t) if any(n - x in hashtable and 2 * x != n for x in hashtable))
t2 = time()

print(t1-t0) #857.0168697834015
print(t2-t1) #591.8803908824921

Upon basic inspection, these two solutions look very similar. Yet, their run times are quite different and while both scale linearly, they deviate further away when I decrease the value of min_t.

What is the underlying difference between the two implementations that causing this

标签： pythonalgorithmperformance

Answer 1

您的额外列表理解创建可能会减慢您的算法，从而提供额外的容器开销。

第二种解决方案使用生成器，它在计算时立即产生值，而不需要列表。