leetcode-Count Primes 以及python的小特性

五郎.

　　题目大家都非常熟悉，求小于n的所有素数的个数。
　　
　　自己写的python 代码老是通不过时间门槛，无奈去看了看大家写的code。下面是我看到的投票最高的code：



class Solution:
# @param {integer} n
# @return {integer}
def countPrimes(self, n):
if n < 3:
return 0
primes = [True] * n
primes[0] = primes[1] = False
for i in range(2, int(n ** 0.5) + 1):
if primes:
primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
return sum(primes)

　　下面的code是有人针对上面这个code进行改进的code：



class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 2:
return 0
prime = [True] * n
prime[:2] = [False, False]
for base in xrange(2, int((n - 1) ** 0.5) + 1):
if prime[base]:
prime[base ** 2::base] = [False] * len(prime[base ** 2::base])
return sum(prime)

　　算法都是一样的，细节处有些不同，比方在对开头if的判断；对prime数组赋值的语句。这里我很好奇，这些改变到底有没有性能的提升，提升了多少。
　　下面是我的在python下得分析：



➜  ~  python -m timeit -s 'int(3 ** 0.5) + 1'
100000000 loops, best of 3: 0.0119 usec per loop
➜  ~  python -m timeit -s 'int(3 ** 0.5 + 1)' # better but not obiviosly
100000000 loops, best of 3: 0.0117 usec per loop
➜  ~  python -m timeit -s 'l = [False] * 1000' 'l[0] = l[1] = True' # better
10000000 loops, best of 3: 0.102 usec per loop
➜  ~  python -m timeit -s 'l = [False] * 1000' 'l[:2] = [True, True]'
10000000 loops, best of 3: 0.172 usec per loop
➜  ~  python -m timeit -s 'for i in range(100): i >= 2'
100000000 loops, best of 3: 0.0118 usec per loop
➜  ~  python -m timeit -s 'for i in range(100): i > 3' # better but not obiviosly
100000000 loops, best of 3: 0.0116 usec per loop

　　所以总结下来：
　　1. 如果我们使用int()之后还要做算术运算，最好先把最终结果算出来，再进行int操作；
　　2. 如果我们想要对某个数列进行赋值，单个的进行赋值比使用[:]批量赋值要快（这个从实用性来看具体场合具体分析）
　　3. 如果我们进行大小判断，单纯的><比 >= <=要计算的更快一些。