DjangoBB LoFi version

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

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

1 2

DuoV

Июль 10, 2010 11:46:52

При решении задачки c projecteuler.net. Заморочился с простыми числами.
Реализую эти два способа.
Способ 1
Перебираем все цифры (N), которые оканчиваются на 1, 3, 7 или 9 (всё, что кончается на 0 или 5, явно не простое число ), и делим их на все числа от 3 до корня от N включительно. Цифры 2, 3 и 5, простые числа, заносятся в массив вручную перед началом работы цикла поиска.
Способ 2
Перебираем все цифры (N), которые оканчиваются на 1, 3, 7 или 9 (всё, что кончается на 0 или 5, явно не простое число ), и делим их на все найденные до этого времени простые числа, от 3 до корня от N включительно. Цифры 2, 3 и 5, простые числа, заносятся в массив вручную перед началом работы цикла поиска.

Соответственно реализация:

def primitive1(th):
    a = [1,2,3,5]
    count = 3
    cur = 6
    while count < th:
        if str(cur)[-1] in '024568':
            cur += 1
            continue
        prim = True
        for i in xrange(3,int(math.sqrt(cur))+1):
            if not cur%i:
                prim = False
                break
        if prim:
            a.append(cur)
            count += 1
        cur += 1
    return a 

def primitive2(th):
    a = [1,2,3,5]
    count = 3
    cur = 6
    while count < th:
        if str(cur)[-1] in '024568':
            cur += 1
            continue
        prim = True
        edge = int(math.sqrt(cur))
        for i in (x for x in a[2:] if x <= edge):
            #print i
            if not cur%i:
                prim = False
                break
        if prim:
            a.append(cur)
            count += 1
        cur += 1
    return a

Далее смотрим время исполнения

p = 200
t1 = Timer("primitive1(%d)" % p,"from __main__ import primitive1")
t2 = Timer("primitive2(%d)" % p,"from __main__ import primitive2")   

print "Primitive 1 -", t1.timeit(number=100)
print "Primitive 2 -", t2.timeit(number=100)

получаем такие результаты:

Primitive 1 - 0.263126850128
Primitive 2 - 0.511752128601

вот я сижу и гадаю, что я не так делаю и почему второй алгоритм раза в 2 дольше, хотя должен процентов на 15 быть быстрей первого. Или есть какая особенность python из-за которой увеличиваеться время работы.
Заранее благодарен и приму любую конструктивную критику и исправления.

Июль 10, 2010 21:21:07

Потому, что вы используете во втором случае генераторное выражение и срез. Уберите их и будет быстрее.

DuoV

Июль 11, 2010 01:27:33

Убрал срез и поменял генератор на список:

def primitive2(th):
    a = [2,3,5]
    count = 3
    cur = 6
    while count < th:
        if str(cur)[-1] in '024568':
            cur += 1
            continue
        prim = True
        edge = int(sqrt(cur))
        for i in [x for x in a if x <= edge]:
            #print i
            if not cur%i:
                prim = False
                break
        if prim:
            a.append(cur)
            count += 1
        cur += 1
    return a

получаем не лучше

Primitive 1 - 0.223769187927
Primitive 2 - 0.582427024841

причем если сделать генератор и без среза, то чуть быстрее, но все равно медленнее первого варианта.

for i in (x for x in a if x <= edge):

Primitive 1 - 0.229700803757
Primitive 2 - 0.426733970642

если использовать filter то все еще хуже.

DuoV

Июль 11, 2010 01:54:55

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

def primitive2(th):
    a = [2,3,5]
    count = 3
    cur = 6
    while count < th:
        if str(cur)[-1] in '024568':
            cur += 1
            continue
        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)
            count += 1
        cur += 1
    return a

Хотелось бы конечно засунуть эту проверку в сам for, но предпочтем скорость.
Спасибо, за совет.

Evgeny

Июль 11, 2010 08:01:10

>приму любую конструктивную критику и исправления

А вот вам:

Поступаем так:
Primitive 1 - ваша первая версия Primitive 2
Primitive 2 - ваша новая версия Primitive 2
Primitive 3 - вот такая вот функция:

def primitive3(th):
    a = [1,2,3,5]
    curr = 7
    while len(a)<=th:
       if all((curr%i != 0 for i in a[1:int(math.sqrt(curr))])):
            a.append(curr)
       curr += 2

    return a

Результаты:

Primitive 1 - 0.444778037612
Primitive 2 - 0.176678871871
Primitive 3 - 0.173959577072

И быстрее и читабельнее. Не пишите на питоне в стиле ‘c’.

DuoV

Июль 11, 2010 08:45:48

Насчет избавиться от count - согласен, так читабельнее. Сишные привычки изживаются тяжело.
А вот насчет остального, по тому же списку
Primitive 1 - первая версия Primitive 2
Primitive 2 - новая версия Primitive 2
Primitive 3 - функция Evgeny:

Primitive 1 - 0.176831960678
Primitive 2 - 0.0816051959991
Primitive 3 - 0.126677036285

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

DuoV

Июль 11, 2010 08:49:21

И еще момент -

curr += 2

не то же самое что

if str(cur)[-1] in '024568':

, хотя работает так быстрее, несмотря на то что рассматриваем лишнее число в каждом десятке.
Также обратите внимание

for i in a[1:int(math.sqrt(curr))]

Совсем не то же самое что

for i in a:
            if i > math.sqrt(curr): break

Июль 11, 2010 10:48:15

DuoV
Разобрался вроде.
Торможение давала генерация списка - .
Спасибо, за совет.

Пожалуйста.
Вот вам еще один вариант на основе вашего - еще быстрее и ужаснее :)

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

PS: Наш код генерит на одно число больше(201), чем просят. Так надо?

DuoV

Июль 11, 2010 10:59:26

Ed
Пожалуйста.
Вот вам еще один вариант на основе вашего - еще быстрее и ужаснее :)
    while count < th:
        if cur % 10 in (1,3,7,9):
            prim = True
PS: Наш код генерит на одно число больше(201), чем просят. Так надо?

Спасибо, это гораздо чем проверять последнюю цифру через строку. Но cur += 2 все таки оказывается быстрее - все таки отбрасываем деление и проверку вхождения, что компенсирует “лишнюю” проверку чисел оканчивающихся на 5.
То что генерит на одно число больше не критично для задачи - это легко правиться. Тут меня больше интересовало производительность для разных алгоритмов, для задачи можно было реализовать любым способом.
Согласен, что код выглядит не так красиво как с генераторами списков, но не всегда ведь красота главное.
Честно говоря, не думал что срезы и генераторы списков медленнее чем классический for c if, обычно это не замечается. Так что будет мне хороший урок в плане производительности кода и особенностей реализации алгоритмов для разных языков.

Июль 11, 2010 11:48:41

Я, видимо, что-то пропустил. Покажите, пожалуйста, вариант с count += 2 быстрее моего.
Кстати, если хотите поупражняться в производительности производства prime numbers(и не только), то вам сюда: http://www.spoj.pl/problems/PRIME1/
Можно совместно.