gistfile1.py

#!/usr/bin/python2.6

import random

values = range(0, 10000)
customers = []
unpaid_customers = []

# generate a bunch of random values between 0 - 1000
for value in values:
  if random.randrange(0, 10, 1) < 7:
    customers.append(value)

# generate 1% ids that could be matching with the ones in customer_ids
for value in values:
  if random.randrange(0, 100, 1) == 1:
    unpaid_customers.append(value)

print 'customers ids len : %d' % len(customers)
print 'unpaid customers ids len: %d' % len(unpaid_customers)

# parse by only looking at first item of unpaid customers
# O(1) vs O(n) for unpaid_customers
# O(n) vs O(n2) for global lookup
for customer_id in customers:
    if unpaid_customers:
        if customer_id >= unpaid_customers[0]:
            current_id = unpaid_customers.pop(0)
            if customer_id == current_id:
                print '%d is a match.' % current_id