← Сtrl

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/
Можно совместно.

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

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

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

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

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

Отредактировано (Июль 11, 2010 18:39:36)

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

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

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

Запуск программ из Python
Кодировки в python
Мой блог

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

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

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

Отредактировано (Июль 11, 2010 23:28:22)

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

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

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

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

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

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

Уведомления

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Board footer