Python-сообщество

Столкнулся с проблемой производительности.
Алгоритм выбрал самый быстрый.
Тестировал профайлером cProfile.
Больное место скрипта - запись в список и проверка элементов списка.
PyPy и Psycho вроде давно не развиваются. IronPython, Jython и прочие прозволяют писать на версиях до 3-ей.

Итак, что делать? Валить на компилируемые языки, переходить на перечисленные реализации питона или что-то ещё?
В самых критичных участках кода: цикл for, пробег по списку, добавление в список и подсчёты (длинная арифметика).

Фигня, любой алгоритм можно улучшить, тем более в python с его ленивыми вычислениями. Покажите код, на кофейной гуще не гадаю) А если предполагать, то циклы иногда можно заменить векторными вычислениями - больше скорость, больше памяти.

Вот самая тормозная и занимающая 80% времени функция:

def isPrime(n):
global primes
for p in primes:
if not n%p:
return False
primes.append(n)
return True

primes- список простых чисел (список доходит до 100к).

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

Отредактировано (Авг. 17, 2011 19:01:06)

http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0

isSimple вызывается же не 1 раз? нужно больше кода (всю программу)
и вообще что нужно в итоге?

Сейчас реализую решето Эратосфена, если не поможет напишу.

:):):)У меня была поучительная история с решетом. Приятель сдавал, хотел на c# написать. Когда большое решето - его приятно упаковать - использовать не обычный массив а битовый - так больше влезает и по памяти меньше хождений. Сказано сделали: крутой алгоритм на c и с# с какой-то встроенной реализацией bitarray - получили одинаковую производительность….
Тут главное т.з. надо понять какая производительность нужна. В данном случае например: сформировать набор простых чисел при взломе кода до приезда полиции которая добирается до банка за 10 мин. У вас есть масштаб времени в который вы должны уложиться (время приезда полиции, время жизни человека, средняя наработка на отказ компа)?

http://code.google.com/p/python-bitstring/

Отредактировано (Авг. 17, 2011 21:37:11)

У меня уже ночь наступила, и мозг может соображать плохо. Но зачем вам пытаться делить на все 100к чисел? Достаточно ведь проверять делители до sqrt(n).

upd: разве что n заведомо больше тех чисел, что находятся в primes

Отредактировано (Авг. 18, 2011 02:29:16)

Вот генератор простых чисел на решете Эратосфена. Диапазон до 1M генерируется за 1-2 сотые секунды.

import numpy

class Primes:
    def __init__(self, n ):
        """ создаем решето для простых чисел в диапазоне [2, n) """
        self.upto = n
        self.sieve = numpy.ones(n//3 + (n%6==2), dtype=numpy.uint8)
        for i in range(1,int(n**0.5)//3+1):
            if self.sieve[i]:
                k=3*i+1|1
                self.sieve[       k*k//3     ::2*k] = 0
                self.sieve[k*(k-2*(i&1)+4)//3::2*k] = 0        

    def __iter__(self):
        def iterator():
            yield 2
            yield 3
            for k in range( 1, self.upto//3+(self.upto%6==2) ):
                if self.sieve[k]: yield k*3+1|1
            raise StopIteration
        return iterator()
        
    def isprime( self, factor ):
        if (factor&1)==0 or (factor%3)==0: return 1 if factor in {2,3} else False
        return self.sieve[factor//3]

p = Primes(10**6)

Отредактировано (Авг. 18, 2011 12:46:42)

fai
PyPy и Psycho вроде давно не развиваются.

Не по теме, но… Isem, странный у тебя итератор, никогда такого не видел…

# ...
    def __iter__(self):
        yield 2
        yield 3
        for k in range( 1, self.upto//3+(self.upto%6==2) ):
            if self.sieve[k]:
                yield k*3+1 | 1
# ...