Почему это простое сито так медленно в Python по сравнению с тем же алгоритмом в Java или C #? - PullRequest
Новая
       48

Почему это простое сито так медленно в Python по сравнению с тем же алгоритмом в Java или C #?

0 голосов
/ 02 июля 2018

Я пытаюсь построить сито для решений проекта Эйлера. Я нуждаюсь в простых числах примерно до 100M, желательно с возможностью пойти намного выше.

Эта реализация у меня работает нормально, но очень медленно: 

class Primes:
__size = None
__sieve = []
__primes = []

def __init__(self, size):
    self.__size = size
    self.__sieve = [True] * size
    for x in range(2, size):
        if self.__sieve[x]:
            self.foundPrime(x);

def foundPrime(self, x):
    self.__primes.append(x)
    for duplicate in range(2 * x, self.__size, x):
        self.__sieve[duplicate] = False

Для сита размером 100M эта инициализация занимает около 70 секунд на моем довольно дорогом компьютере. Кто-нибудь знает почему? Потому что в Java и C # это заняло у меня около 1 секунды ...

Итак, этот пост отличается от других постов тем, что я не хочу знать, как реализовать алгоритм, я хочу понять, почему он так медленно работает в Python.

Некоторые отпечатки дают мне информацию, что около 50% времени уходит на поиск первых 100К простых чисел.

1 Ответ

0 голосов
/ 02 июля 2018

В различных тестах, для чего бы они ни стояли, Python зависит от проблемы с одинаковой скоростью до 50 раз медленнее, чем Java. Во многом это связано с интерпретацией Python и компиляцией Java (даже если не с нативным). Руби публикует аналогичные оценки как Python.

Языковой дизайн также дает Java и C # некоторые преимущества.

Существует два хороших способа ускорить процесс, кроме более эффективных методов Python: использовать pypy, который, по сути, выполняет компиляцию вашего python, подобно Java, или писать критические разделы на более быстром языке, таком как C, и вызывать эти подпрограммы из Python, задача, которая на самом деле довольно проста, если вы хорошо владеете быстрым языком.

...