Как повысить эффективность этой программы?

Question

Хронометража следующей программы (которая находится внутри функции штриха) является 110.726383227 секундами

Если я запускаю ту же программу без окружив его функцию (штрих) это время работает в 222.006502634 секундах

Я сделал значительное улучшение производительности путем ее включения в функцию.

все еще есть какая-либо возможность повысить эффективность этой программы?

# This is a program to find sum of prime numbers till 2 billion 

def prime(): 
import time 
start_time = time.clock() 

num = 2 
j=1 
tot_sum = 0 

for num in xrange(2,2000000): 
    count = 0 
    for j in xrange(1,int(num**0.5)+1): # checking from 1 to sqrt(n)+1 
     if(num % j == 0): 
      count = count+1 

    if(count == 1): 
     tot_sum = tot_sum + num 

print "total sum is %d" % tot_sum 

print time.clock() - start_time, "seconds" 

Answer 1

Если вы хотите, чтобы решить эту проблему без внешней LIBS, есть некоторые очевидные улучшения, которые вы можете сделать:

def prime(): 
    import time 
    start_time = time.clock() 

    tot_sum = 2 

    for num in xrange(3, 2000000, 2): 
      isPrime = True 
      for j in xrange(3, int(num ** 0.5) + 1, 2): 
       if(num % j == 0): 
        isPrime = False 
        break 

      if isPrime: 
       tot_sum = tot_sum + num 

    print "total sum is %d" % tot_sum 

    print time.clock() - start_time, "seconds" 

prime() 

Не проверять более 2 четных чисел, не проверяя все делители, если один найдено. Ваш исходный код работает на моей машине в 172.924809 секунд, а мой пробег - 8.492169 секунд.

При использовании внешнего LIBS разрешено, я предлагаю gmpy2:

def prime(): 
    from gmpy2 import is_prime 
    import time 
    start_time = time.clock() 

    print "total sum is %d" % (sum(filter(is_prime, xrange(3,2000000,2)))+2) 

    print time.clock() - start_time, "seconds" 

prime() 

Это работает в 1,691812 секунды

Answer 2

Возможно, это связано с тем, как python разрешает переменные. Грубо, когда вы вводите функцию, python создает новое пространство имен, которое по существу сопоставляет все переменные, локальные с этой функцией. Затем Python может использовать пространство имен для определения значений всех переменных, к которым обращается программист. Порядок разрешения имен переменных выглядит следующим образом:

• Lookup имя переменной в локальном пространстве имен
• Lookup имя переменной в глобальном пространстве имен
• имя Lookup в Python встроенные модули.

Performing поиски могут быть дорогими, и общий совет производительности в Python является use local variables именно по этой причине: как минимум, это позволит избежать делать два Lookups вместо одного. Кроме того, новые компиляторы python также, похоже, делают дополнительные оптимизации для удаления даже одного lookup into the local namespace, но просто обрабатывают переменную как непосредственное значение.

Хороший способ проверки того, может ли эта оптимизация произойти только из-за поиска пространства имен, может быть (запрет других оптимизаций, о которых я не знаю), чтобы обернуть всю вашу логику в функцию, но сделать все переменные, повторное использование глобального. Если все замедляется, вы можете догадаться, что это поиск пространства имен занимает столько времени.