fai
Авг. 17, 2011 18:48:23
Столкнулся с проблемой производительности.
Алгоритм выбрал самый быстрый.
Тестировал профайлером cProfile.
Больное место скрипта - запись в список и проверка элементов списка.
PyPy и Psycho вроде давно не развиваются. IronPython, Jython и прочие прозволяют писать на версиях до 3-ей.
Итак, что делать? Валить на компилируемые языки, переходить на перечисленные реализации питона или что-то ещё?
В самых критичных участках кода: цикл for, пробег по списку, добавление в список и подсчёты (длинная арифметика).
dartNNN
Авг. 17, 2011 18:53:08
Фигня, любой алгоритм можно улучшить, тем более в python с его ленивыми вычислениями. Покажите код, на кофейной гуще не гадаю) А если предполагать, то циклы иногда можно заменить векторными вычислениями - больше скорость, больше памяти.
fai
Авг. 17, 2011 18:59:12
Вот самая тормозная и занимающая 80% времени функция:
def isPrime(n):
global primes
for p in primes:
if not n%p:
return False
primes.append(n)
return True
primes- список простых чисел (список доходит до 100к).
Можно сделать список статическим, но в том то и соль, что простые числа должны генерироваться по мере надобности, а значит нужен либо очень большой список сразу, либо генерация на лету.
o7412369815963
Авг. 17, 2011 19:03:45
fai
Авг. 17, 2011 19:06:05
Сейчас реализую решето Эратосфена, если не поможет напишу.
doza_and
Авг. 17, 2011 21:29:22
:):):)У меня была поучительная история с решетом. Приятель сдавал, хотел на c# написать. Когда большое решето - его приятно упаковать - использовать не обычный массив а битовый - так больше влезает и по памяти меньше хождений. Сказано сделали: крутой алгоритм на c и с# с какой-то встроенной реализацией bitarray - получили одинаковую производительность….
Тут главное т.з. надо понять какая производительность нужна. В данном случае например: сформировать набор простых чисел при взломе кода до приезда полиции которая добирается до банка за 10 мин. У вас есть масштаб времени в который вы должны уложиться (время приезда полиции, время жизни человека, средняя наработка на отказ компа)?
http://code.google.com/p/python-bitstring/
GaiveR
Авг. 18, 2011 02:27:14
У меня уже ночь наступила, и мозг может соображать плохо. Но зачем вам пытаться делить на все 100к чисел? Достаточно ведь проверять делители до sqrt(n).
upd: разве что n заведомо больше тех чисел, что находятся в primes
Isem
Авг. 18, 2011 11:53:13
Вот генератор простых чисел на решете Эратосфена. Диапазон до 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)
dvs
Сен. 14, 2011 19:39:04
fai
PyPy и Psycho вроде давно не развиваются.
PyPy – ещё как развивается!
bw
Сен. 15, 2011 07:15:16
Не по теме, но…
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
# ...
..bw