DjangoBB LoFi version

Полная версия: Вопрос по производительности при поиске простых чисел

Начало » Python для новичков » Вопрос по производительности при поиске простых чисел

1 2

DuoV

Июль 11, 2010 12:02:50

def primitive2(th):
    a = [2,3,5]
    cur = 7
    while len(a) < th:
        prim = True
        edge = int(sqrt(cur))
        for i in a:
            if i > edge: break
            if not cur%i:
                prim = False
                break
        if prim:
            a.append(cur)
        cur += 2
    return a

это взято из варианта Evgeny.
получаеться
Primitive с (if cur % 10 in (1,3,7,9)) - 0.739934921265
Primitive (cur += 2) - 0.593034029007

DuoV

Июль 11, 2010 12:12:23

Ed
Кстати, если хотите поупражняться в производительности производства prime numbers(и не только), то вам сюда: http://www.spoj.pl/problems/PRIME1/
Можно совместно.

Спасибо за наводку - интересный сайт чтобы потренироваться да еще и в разных языках. С удовольствием присоединюсь по мере возможности.

Июль 11, 2010 18:16:14

Если вернуться к счетчику вместо len(), то будет на несколько процентов быстрее.

Июль 11, 2010 18:39:15

Попробуйте это: http://code.activestate.com/recipes/576596-sieve-of-eratosthenes/
Вопрос производительности можно будет закрыть - это больше, чем в 15 раз быстрее, чем все, что есть в этом треде.

o7412369815963

Июль 11, 2010 21:37:40

for i in xrange(1,th,2):
    if i%10==5: continue

и psyco ещё включить

DuoV

Июль 11, 2010 23:22:58

Ed
Попробуйте это: http://code.activestate.com/recipes/576596-sieve-of-eratosthenes/
Вопрос производительности можно будет закрыть - это больше, чем в 15 раз быстрее, чем все, что есть в этом треде.

Нет слов. Пока полноценно не тестировал - надо на работу, но разок прогнал - работает на порядок шустрей, хотя тут и срезы и filter, который добавлял мне еще секунды. А тут все пролетает. Думаю дело в том что все делается за одну проходку а не каждый раз заново, как все функции в этом треде. Тут реальное сито Эратосфена.
Только стоит учесть, что оно ищет не сколько то элементов, как до этого искали, а не больше n. Но это то что нужно для PRIME1 ).

Zubchick

Июль 12, 2010 00:20:23

странно, что вы не знали о таком распространенном алгоритме :) На русский, кстати, переводится как решето Эратосфена. http://ru.wikipedia.org/wiki/Решето_Эратосфена

DuoV

Июль 12, 2010 00:51:25

Zubchick
странно, что вы не знали о таком распространенном алгоритме :) На русский, кстати, переводится как решето Эратосфена. http://ru.wikipedia.org/wiki/Решето_Эратосфена

Изначально то интересовал, не лучший алгоритм, а почему медленее работает именно тот и сравнение производительности разных алгоритмов.
Но зато вынес для себя новое про что генераторы и срезы не всегда есть добро.
Про сито (можно и решето) Эратосфена, то я знал и когда посмотрел на алогритм, то узнал его. А так сидит оно в памяти где то в глубине со времен института, и пока не ткнули и не вспомнил. :)