How to speed up Python script iterating nested loop?

Question

I'm running a Python script which iterates two huge lists and finds the matching pairs.

However, it seems to take forever. How to speed up this script?

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

Try not to use built-in names as variable names in your code, it has the potential to cause frustration. By this I am referring to your use of list as a variable name — smac89
– smac89, Commented Apr 15, 2016 at 2:46
@Smac89 I was in a hurry to write a question, and made a mistake. I modified the variable name. — Han
– Han, Commented Apr 15, 2016 at 2:52
Is that second nested loop supposed to be read_list or rand_list? — smac89
– smac89, Commented Apr 15, 2016 at 3:02
@Smac89 It is supposed to be rand_list. Sorry for the confusion. — Han
– Han, Commented Apr 15, 2016 at 3:10
Also consider a list comprehension (rand_list = [random.randint(1, target_num) for _ in itertools.repeat(None, target_num)]). They are more efficient than using for loops as you don’t need to load the append attribute off of the list and call it as a function. — ballade4op52
– ballade4op52, Commented Apr 15, 2016 at 3:33

smac89 · Accepted Answer · 2016-04-15 03:41:01Z

3

Use sets

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

Using a set for the first list, means that checking if the item is in that list is now reduced to an O(1)

As I am writing this, I realise you can even do better. The range function in python 3 returns a sequence, so you need python 3 for this next part

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

Even better, using range and do the checking within the first loop?

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")

edited Apr 15, 2016 at 3:41

answered Apr 15, 2016 at 2:49

smac89

43.8k15 gold badges150 silver badges202 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

ShadowRanger Over a year ago

O(1) membership testing is not a feature of xrange, it was only added to range in Python 3.2 when they finally finished implementing the Sequence ABC for range. xrange membership testing generates and tests values one at a time until it gets a hit. Also, neither range nor xrange are generators; they're more or less Sequence objects that can produce iterators, not iterators/generators themselves; if they were generators, iterating them once would exhaust them, but that's not how they behave.

mozman · Accepted Answer · 2016-04-15 04:59:59Z

1

If using Python 2, use xrange(), which returns a generator-like object.

# 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

edited Apr 15, 2016 at 4:59

answered Apr 15, 2016 at 4:26

mozman

2,26910 silver badges25 bronze badges

Collectives™ on Stack Overflow

How to speed up Python script iterating nested loop?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related