Wie beschleunigt man das Python-Skript, das die verschachtelte Schleife iteriert?

Question

Ich führe ein Python-Skript, das zwei riesige Listen iteriert und die passenden Paare findet.

Es scheint jedoch ewig zu dauern. Wie beschleunigt man dieses Skript?

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

Verwenden

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:]) 

Unter Verwendung eines Satzes für die erste Liste enthält, bedeutet, dass geprüft wird, ob das Element in dieser Liste ist jetzt auf einen O reduziert wird (1)

---

Während ich dies schreibe, merke ich, dass du es sogar besser machen kannst. Die range Funktion in Python 3 gibt eine Sequenz, so müssen Sie Python 3 für diesen nächsten Teil besser

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:]) 

Selbst, Bereich verwenden und die Kontrolle innerhalb der ersten Schleife zu tun?

Answer 2

Wenn Sie Python 2 verwenden, verwenden Sie xrange(), das ein generatorähnliches Objekt zurückgibt.

# 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