<p>使用集合</p>
<pre><code>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:])
</code></pre>
<p>对第一个列表使用set,意味着检查该项是否在该列表中现在减少为O(1)</p>
<hr/>
<p>当我写这篇文章的时候,我意识到你甚至可以做得更好。python3中的<a href="https://docs.python.org/3/library/functions.html#func-range" rel="nofollow"><strong>range</strong></a>函数返回一个序列,因此下一部分需要python3</p>
<pre><code>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:])
</code></pre>
<p>更好的是,使用range并在第一个循环中进行检查?你知道吗</p>
<pre><code>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")
</code></pre>