嵌套循环或'in'，哪个更快？(Nested Loop or 'in', which is faster?)

我是一个python新手，并正在研究一些基本的编码挑战，并希望有人可以解释以下哪些代码片段运行得更快。 关键是看列表中是否有一对整数加起来为100：

list = [1,2,3,99,5] for i in list: for j in list: if i + j == 100: return True

要么：

list = [1,2,3,99,5] for i in list: diff = 100 - i if diff in list: return True

I am a python novice and was studying some basic coding challenges and was hoping to someone could explain which of the following snippets of code would run faster. The point is to see if there are pairs of integers within the list that add up to 100:

list = [1,2,3,99,5] for i in list: for j in list: if i + j == 100: return True

or:

list = [1,2,3,99,5] for i in list: diff = 100 - i if diff in list: return True

最满意答案

基准

这个自制的随机基准测试表明，在大多数情况下，使用in的解决方案明显更快。 我没有调查，但我确实遇到了一些运行，其中嵌套for循环的解决方案在使用样本大小时稍快。

import time, random def time_it(f, rep=100000): sample = [[random.randint(0, 100) for _ in range(20)] for _ in range(rep // 100)] start = time.time() for i in range(rep): f(sample[i % len(sample)]) return (time.time() - start) def nested_for(lst): for i in lst: for j in lst: if i + j == 100: return True def nested_in(lst): for i in lst: diff = 100 - i if diff in lst: return True print('for:', time_it(nested_for)) print('in:', time_it(nested_in))

产量

for: 0.7093353271484375 in: 0.24253296852111816

在每次迭代中删除j的赋值可能会消除解决方案中的大量开销。

起色

虽然注意两种解决方案都是O（n 2 ） 。 您可以使用set来实现O（n） 。 由于set对其项进行哈希处理，因此查找为O（1） 。

def contains_diff(lst): elements = set(lst) return any(100 - i in elements for i in elements) print(contains_diff([1, 2, 3, 99])) # True print(contains_diff([1, 2, 3])) # False

有趣的是，如果您对上述情况进行基准测试，它通常会慢in解决方案。 这是因为在随机列表中快速找到100的总和的概率相对较高。 如果你想让你想要找到的差异增大，那么建立一个set的开销会很快被set查找的速度所补偿。

边注

作为旁注，您不应该将list用作变量名，因为它会覆盖内置list 。

Benchmark

This homemade, randomized benchmark demonstrates that the solution using in is significantly faster in most case. I did not investigate, but I did encounter some runs where the solution with the nested for-loops was slightly faster when toying with the sample size.

import time, random def time_it(f, rep=100000): sample = [[random.randint(0, 100) for _ in range(20)] for _ in range(rep // 100)] start = time.time() for i in range(rep): f(sample[i % len(sample)]) return (time.time() - start) def nested_for(lst): for i in lst: for j in lst: if i + j == 100: return True def nested_in(lst): for i in lst: diff = 100 - i if diff in lst: return True print('for:', time_it(nested_for)) print('in:', time_it(nested_in))

Output

for: 0.7093353271484375 in: 0.24253296852111816

Removing the assignation of j on every iteration is probably what removes a big overhead in the solution with the in.

Improvement

Although note that both solutions are O(n2). You can achieve O(n) by using a set. Since a set hashes its items, lookup is O(1).

def contains_diff(lst): elements = set(lst) return any(100 - i in elements for i in elements) print(contains_diff([1, 2, 3, 99])) # True print(contains_diff([1, 2, 3])) # False

Interestingly enough, if you benchmark the above it will be generally slower than the in solution. This is because the probability of in finding a sum of 100 quickly in a randomized list is relatively high. If you let the difference you want to find grow, then the overhead of building a set is rapidly compensated by the speed of set lookup.

Sidenote

As a sidenote, you should not be using the list as a variable name as it overwrites the builtin list.

嵌套循环或'in'，哪个更快？(Nested Loop or 'in', which is faster?)

我是一个python新手，并正在研究一些基本的编码挑战，并希望有人可以解释以下哪些代码片段运行得更快。 关键是看列表中是否有一对整数加起来为100：

list = [1,2,3,99,5] for i in list: for j in list: if i + j == 100: return True

要么：

list = [1,2,3,99,5] for i in list: diff = 100 - i if diff in list: return True

I am a python novice and was studying some basic coding challenges and was hoping to someone could explain which of the following snippets of code would run faster. The point is to see if there are pairs of integers within the list that add up to 100:

list = [1,2,3,99,5] for i in list: for j in list: if i + j == 100: return True

or:

list = [1,2,3,99,5] for i in list: diff = 100 - i if diff in list: return True

最满意答案

基准

这个自制的随机基准测试表明，在大多数情况下，使用in的解决方案明显更快。 我没有调查，但我确实遇到了一些运行，其中嵌套for循环的解决方案在使用样本大小时稍快。

import time, random def time_it(f, rep=100000): sample = [[random.randint(0, 100) for _ in range(20)] for _ in range(rep // 100)] start = time.time() for i in range(rep): f(sample[i % len(sample)]) return (time.time() - start) def nested_for(lst): for i in lst: for j in lst: if i + j == 100: return True def nested_in(lst): for i in lst: diff = 100 - i if diff in lst: return True print('for:', time_it(nested_for)) print('in:', time_it(nested_in))

产量

for: 0.7093353271484375 in: 0.24253296852111816

在每次迭代中删除j的赋值可能会消除解决方案中的大量开销。

起色

虽然注意两种解决方案都是O（n 2 ） 。 您可以使用set来实现O（n） 。 由于set对其项进行哈希处理，因此查找为O（1） 。

def contains_diff(lst): elements = set(lst) return any(100 - i in elements for i in elements) print(contains_diff([1, 2, 3, 99])) # True print(contains_diff([1, 2, 3])) # False

有趣的是，如果您对上述情况进行基准测试，它通常会慢in解决方案。 这是因为在随机列表中快速找到100的总和的概率相对较高。 如果你想让你想要找到的差异增大，那么建立一个set的开销会很快被set查找的速度所补偿。

边注

作为旁注，您不应该将list用作变量名，因为它会覆盖内置list 。

Benchmark

This homemade, randomized benchmark demonstrates that the solution using in is significantly faster in most case. I did not investigate, but I did encounter some runs where the solution with the nested for-loops was slightly faster when toying with the sample size.

import time, random def time_it(f, rep=100000): sample = [[random.randint(0, 100) for _ in range(20)] for _ in range(rep // 100)] start = time.time() for i in range(rep): f(sample[i % len(sample)]) return (time.time() - start) def nested_for(lst): for i in lst: for j in lst: if i + j == 100: return True def nested_in(lst): for i in lst: diff = 100 - i if diff in lst: return True print('for:', time_it(nested_for)) print('in:', time_it(nested_in))

Output

for: 0.7093353271484375 in: 0.24253296852111816

Removing the assignation of j on every iteration is probably what removes a big overhead in the solution with the in.

Improvement

Although note that both solutions are O(n2). You can achieve O(n) by using a set. Since a set hashes its items, lookup is O(1).

def contains_diff(lst): elements = set(lst) return any(100 - i in elements for i in elements) print(contains_diff([1, 2, 3, 99])) # True print(contains_diff([1, 2, 3])) # False

Interestingly enough, if you benchmark the above it will be generally slower than the in solution. This is because the probability of in finding a sum of 100 quickly in a randomized list is relatively high. If you let the difference you want to find grow, then the overhead of building a set is rapidly compensated by the speed of set lookup.

Sidenote

As a sidenote, you should not be using the list as a variable name as it overwrites the builtin list.