如何加速Python脚本迭代嵌套循环？

Question

我正在运行一个Python脚本，它迭代两个巨大的列表并找到匹配的对。你知道吗

然而，这似乎需要永远。如何加速这个脚本？你知道吗

import sys
import random
import itertools

def main(args):
    target_num = int(999999999)
    num_list = range(1, target_num)
    rand_list = []
    hit_list = []

    for _ in itertools.repeat(None, target_num):
        rand_list.append(random.randint(1, target_num))

    for num in num_list:
        for rand_num in rand_list:
            if num == rand_num:
                print "hit"

if __name__ == "__main__":
    main(sys.argv[1:])

Answer 1

如果使用python2，请使用xrange（），它将返回一个类似生成器的对象。你知道吗

# requires Python 2
import random

target_num = 99 # 999999999 are too much items for testing

# target_num random numbers in range 1 .. target_num-1
random_numbers = set(random.randint(1, target_num) for _ in xrange(target_num)) 

hits = set()
for num in xrange(1, target_num):  # check for all numbers in range 1 .. target_num-1
    if num in random_numbers:   # num in set() is O(1)
        hits.add(num)

if len(random_numbers - hits) == 0:
     print "all random numbers are hits!"

# so:
for num in random_numbers:
    print num
# is the same result

Answer 2

使用集合

import sys
import random
import itertools

def main(args):
    target_num = int(999999999)
    num_list = set(range(1, target_num))
    rand_list = []
    hit_list = []

    for _ in itertools.repeat(None, target_num):
        rand_list.append(random.randint(1, target_num))


    for num in rand_list:
        if num in num_list: # O(1)
            print "hit"

if __name__ == "__main__":
    main(sys.argv[1:])

对第一个列表使用set，意味着检查该项是否在该列表中现在减少为O（1）

---

当我写这篇文章的时候，我意识到你甚至可以做得更好。python3中的range函数返回一个序列，因此下一部分需要python3

import sys
import random
import itertools

def main(args):
    target_num = int(999999999)
    num_list = range(1, target_num) # this is a generator
    rand_list = []
    hit_list = []

    for _ in itertools.repeat(None, target_num):
        rand_list.append(random.randint(1, target_num))


    for num in rand_list:
        if num in num_list: # Stil O(1)
            print ("hit")

if __name__ == "__main__":
    main(sys.argv[1:])

更好的是，使用range并在第一个循环中进行检查？你知道吗

for _ in itertools.repeat(None, target_num):
    rand_num = random.randint(1, target_num)
    rand_list.append(rand_num)
    if rand_num in num_list:
        print ("hit")