Оптимизация питона для петель

Question

Вот две программы, которые наивно вычисляют количество простых чисел < = n.
Один находится в Python, а другой - на Java.

public class prime{ 
    public static void main(String args[]){ 
     int n = Integer.parseInt(args[0]); 
     int nps = 0; 
boolean isp; 

     for(int i = 1; i <= n; i++){ 
      isp = true; 

      for(int k = 2; k < i; k++){ 
       if((i*1.0/k) == (i/k)) isp = false; 
      } 
      if(isp){nps++;} 
} 
     System.out.println(nps); 
    } 
} 


`#!/usr/bin/python`                                   
import sys 
n = int(sys.argv[1]) 
nps = 0 

for i in range(1,n+1): 
    isp = True 
    for k in range(2,i): 
     if((i*1.0/k) == (i/k)): isp = False 
    if isp == True: nps = nps + 1 
print nps 

Запуск их на п = 10000 я получаю следующие тайминги.
оболочки: ~ $ время питон prime.py 10000 & & время ява премьер 10000

реальные 0m49.833s
пользователя 0m49.815s
SYS 0m0.012s

real 0m1.491s
пользователь 0m1.468s
sys 0m0.016s

Я использую для петель в python неправильно здесь или это python на самом деле это намного медленнее?

Я не ищу ответа, специально созданного для вычисления простых чисел, но мне интересно, если код python обычно используется умнее.

код Java был скомпилирован с JAVAC 1.6.0_20
Запуск с Java версии "1.6.0_18"
OpenJDK Runtime Environment (IcedTea6 1.8.1) (6b18-1.8.1-0ubuntu1 ~ 9.10.1) OpenJDK Client VM (сборка 16.0-b13, смешанный режим, обмен)

Питон:
Python 2.6.4 (r264: 75706, 7 декабря 2009, 18:45:15)

Answer 1

Как уже отмечалось, прямо Python на самом деле не для такого рода вещи. То, что алгоритм первичной проверки наивна, также не является точкой. Однако с двумя простыми вещами я смог значительно сократить время на Python, используя оригинальный алгоритм.

Во-первых, положите все внутри функции, назовите ее main() или что-то в этом роде. Это уменьшило время на моей машине в Python с 20,6 секунд до 14,54 секунд. Делать вещи во всем мире медленнее, чем выполнять их в функции.

Во-вторых, используйте Psyco, JIT-компилятор. Для этого нужно добавить две строки в верхней части файла (и, конечно, установлен имеющий психо):

import psyco 
psyco.full() 

Это принесло окончательное время 2,77 секунды.

Последнее примечание. Я решил использовать для этого Cython, и получил время до 0,8533. Однако, зная, как сделать несколько изменений, чтобы сделать его быстрым, Cython-код не является тем, что я рекомендую для обычного пользователя.

Answer 2

Да, Python медленнее, примерно в сто раз медленнее C. Вы можете использовать xrange вместо диапазона для небольшого ускорения, но кроме этого это нормально.

В конечном счете то, что вы делаете неправильно, заключается в том, что вы делаете это на простом Python, вместо использования оптимизированных библиотек, таких как Numpy или Psyco.

Java поставляется с jit-компилятором, который имеет большое значение, когда вы просто хрустете номера.

Answer 3

Вы можете сделать свой Python примерно в два раза быстрее, заменив этот сложный тест с

if i % k == 0: isp = False 

Вы также можете сделать это примерно в восемь раз быстрее (при п = 10000), чем путем добавления перерыва после этого испа = False.

Также сделайте себе одолжение и пропустите четные числа (добавив один к nps, чтобы начать включать 2).

Наконец, вам нужно только k, чтобы перейти к sqrt (i).

Конечно, если вы вносите одинаковые изменения в Java, это все равно примерно в 10 раз быстрее, чем оптимизированный Python.

Answer 4

Если вы хотите сделать это быстро, Python, вероятно, не путь вперед, но вы можете немного ускорить его. Во-первых, вы используете довольно медленный способ проверить делимость. Modulo быстрее. Вы также можете остановить внутренний цикл (с k), как только он обнаружит совпадение. Я бы сделал что-то вроде этого:

nps = 0 
for i in range(1, n+1): 
    if all(i % k for k in range(2, i)): # i.e. if divisible by none of them 
     nps += 1 

Это снижает его с 25 до 1,5 с для меня. Использование xrange приводит к снижению до 0,9 с.

Вы можете ускорить его, сохранив список простых чисел, которые вы уже нашли, и тестируете их, а не каждое число до i (если я не делится на 2, он не будет делимым на 4, 6, 8 ...).

Answer 5

Да, Python - один из самых медленных практических языков, с которыми вы столкнетесь. While петли немного быстрее, чем for i in xrange(), но в конечном итоге Python всегда будет намного, намного медленнее, чем что-либо еще.

Python имеет свое место: теория и идеи прототипирования или в любой ситуации, когда способность быстро генерировать код важнее, чем производительность кода.

Python - это язык сценариев. Не язык программирования.

Answer 6

Мальчик, когда вы сказали, что это наивная реализация, вы наверняка не шутили!

Но да, разница в производительности от одного до двух порядков не является неожиданностью при сравнении JIT-скомпилированного оптимизированного машинного кода с интерпретируемым языком. Альтернативная реализация Python, такая как Jython, которая работает на виртуальной машине Java, может быть быстрее для этой задачи; вы могли бы дать ему вихрь. Cython, который позволяет добавлять статическую типизацию в Python и получать C-подобную производительность в некоторых случаях, может также стоить исследовать.

Даже при рассмотрении стандартного интерпретатора Python, CPython, однако, возникает вопрос: достаточно ли Python для задачи? Будет ли время, когда вы сохраняете запись кода на динамическом языке, таком как Python, компенсирует дополнительное время его работы? Если бы вам пришлось написать данную программу на Java, было бы слишком много работы, чтобы стоить проблемы?

Рассмотрите, например, что программа Python, работающая на современном компьютере, будет работать так же быстро, как и Java-программа, работающая на 10-летнем компьютере. Компьютер, который у вас был десять лет назад, был достаточно быстрым для многих вещей, не так ли?

У Python есть ряд функций, которые делают его отличным для числовой работы. К ним относятся целочисленный тип, который поддерживает неограниченное количество цифр, десятичный тип с неограниченной точностью и дополнительную библиотеку, называемую NumPy, специально для вычислений. Однако скорость исполнения, как правило, не является одной из основных претензий на славу. Там, где это превосходно, нужно заставить компьютер делать то, что вы хотите, с минимальным когнитивным трением.

Answer 7

Почему вы не публикуете что-то об использовании памяти, а не только о скорости? Попытка получить простой сервлет на tomcat тратит 3GB на моем сервере.

Что вы сделали с примерами, там не очень хорошо. Вам нужно использовать numpy. Заменяйте для/range с помощью циклов while, тем самым избегая создания списка.

Наконец, python вполне подходит для хромирования числа, по крайней мере, людьми, которые делают это правильно, и знают, что такое сито из Eratosthenes или операция mod.

Answer 8

Есть много вещей, которые вы можете сделать для этого алгоритма, чтобы ускорить его, но большинство из них также ускорит версию Java. Некоторые из них ускорят Python больше, чем Java, поэтому они заслуживают тестирования.

Вот лишь несколько изменений, которые ускоряют его от 11,4 до 2,8 секунды на моей системе:

nps = 0 
for i in range(1,n+1): 
    isp = True 
    for k in range(2,i): 
     isp = isp and (i % k != 0) 
    if isp: nps = nps + 1 
print nps 

Answer 9

Python - это язык, который, по иронии судьбы, хорошо подходит для разработки алгоритмов. Даже модифицированный алгоритм:

# See Thomas K for use of all(), many posters for sqrt optimization 
nps = 0 
for i in xrange(1, n+1): 
    if all(i % k for k in xrange(2, 1 + int(i ** 0.5))): 
     nps += 1 

работает значительно ниже одной секунды. Код:

def eras(n): 
    last = n + 1 
    sieve = [0,0] + range(2, last) 
    sqn = int(round(n ** 0.5)) 
    it = (i for i in xrange(2, sqn + 1) if sieve[i]) 
    for i in it: 
     sieve[i*i:last:i] = [0] * (n//i - i + 1) 
    return filter(None, sieve) 

еще быстрее. Попробуйте these.

Дело в том, что python обычно достаточно быстр для разработки вашего решения. Если он недостаточно быстрый для производства, используйте numpy или Jython для увеличения производительности. Или переместите его на скомпилированный язык, взяв с собой ваши наблюдения за алгоритмами, изученные на python.