DjangoBB LoFi version

Полная версия: Ускорение Python 3.0. No way?

Начало » Python для новичков » Ускорение Python 3.0. No way?

1 2

Isem

Сен. 20, 2011 06:08:25

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

Ну так и простые числа тоже странные )
А само решето не содержит четных и кратных трем, поэтому приходится искусственно выдавать двойку и тройку.

p.s. Или имеется в виду синтаксис? Действительно, саму __iter__ можно превратить в генератор.

Сен. 21, 2011 18:28:38

Я в основном на “raise StopIteration” намекал, ну и на функцию в методе.
Возможно ты что-то такое хотел сделать:

class MyIterator(object):
    def __init__(self, c = 1):
        self.c = c
    def next(self):
        if self.c < 1:
            raise StopIteration
        self.c -= 1
        return self.c

class MyObject(object):
    def __iter__(self):
        return MyIterator()

>>> list(MyObject())
[0]
>>> for i in MyObject():
...     print i
0

..bw

Isem

Сен. 22, 2011 03:45:29

bw

Да нет, чтобы не плодить классы, я воспользовался функцией-генератором. А она уже сама генерирует StopIteration при завершении, то есть не надо его вызывать. Ну и, как оказалось, можно непосредственно __iter__ сделать генератором.
Поэтому получается просто типа:

def __iter__(self):
    for k in range( 10, 0, -1):
        yield k

Таким образом, экземпляр класса уже есть готовый итератор.

elias

Сен. 22, 2011 15:09:08

Я может сейчас и глупость спрошу, но все же позвольте поинтересоваться: зачем вам список простых чисел? Какая конкретная задача ложится на этот список?

Isem

Сен. 23, 2011 05:07:40

Например, для решения уравнений в целых чисел. А список нужен для того, что пока еще не открыли другого способа генерации последовательных простых чисел, так что все в ваших руках.
p.s. Ну а для математика простые числа - это как деньги для банкира.

elias

Сен. 23, 2011 10:17:39

Вопрос вообще-то топикстартеру был. Ему тот список может и не надо вовсе, только зря генерировать его раз за разом будет.

kriban

Сен. 23, 2011 21:33:39

Вот сложность работы с различными структурами
http://wiki.python.org/moin/TimeComplexity
Вот алгоритм проверки числа на простоту, взятый с Ейлера. Работает быстрее проверки по списку, на мой взгляд.

def is_Prime(n):
    '''Check n and return True if n is simple. '''
    if n <= 1:
        return False
    elif n < 4:
        return True  # 2 and 3 are prime
    elif n % 2 == 0:
        return False
    elif n < 9:
        return True  # we have already excluded 4, 6 and 8.
    elif n % 3 == 0:
        return False
    else:
        r = round(n ** 0.5) # n ** 0.5 rounded to the greatest integer r so that r * r <= n
        f = 5
        while f <= r:
            if n % f == 0:
                return False
            if n % (f + 2) == 0:
                return False
            f += 6
    return True

elias

Сен. 23, 2011 21:54:46

Написал для поиска простых чисел, пока не решил, куда всерьёз можно приткнуть, и не знаю, можно ли его еще как-то ускорить (переписать с использованием NumPy, к примеру, я просто не знаком особо с ним)

Алгоритм Миллера-Рабина (Python 3.2.1)

#! /usr/local/bin/python3.2
from random import randint
from math import log, floor
import time

def to_reversed_binary(n):
    r = []
    while n > 0:
        r.append(n & 1)
        n //= 2
    return r


def test(a, n):
    """
        test(a, n) -> bool. Tests whether n is complex.
        Returns:
            - True, if n is complex.
            - False, if n is probably prime.
    """
    b = to_reversed_binary(n - 1)
    k = 1
    for i in range(len(b) - 1, -1, -1):
        x = k
        k = (k * k) % n
        if k == 1 and x != 1 and x != n - 1:
            return True     #Complex
        if b[i] == 1:
            k = (k * a) % n
    if k != 1:
        return True     #Complex
    return False        #Probably prime


def milrab(n):
    """
        milrab(n) -> bool Checks whether n is prime or not
        Returns:
        - True, if n is probably prime.
        - False, if n is complex.
    """
    if n == 1:
        return False
    s = int(floor(log(n, 2)))
    for j in range(1, s + 1):
        a = randint(1, n - 1)
        if test(a, n):
            return False                #n is complex
    return True                         #n is probably prime

Тест:

start = time.time()
print (milrab(4113101149215104800030529537915953170486139623539759933135949994882770404074832568499))
print ('In {0} seconds'.format(time.time() - start))

Output:

True
In 0.6012141704559326 seconds

Число и правда простое, взято из какой-то последовательности.