Матрис и питон [дубликат]

Для самого быстрого кода решение numpy является лучшим. Однако по чисто академическим причинам я публикую мою чистую версию python, которая немного меньше, чем на 50% быстрее, чем версия поваренной книги, опубликованная выше. Поскольку я делаю весь список в памяти, вам нужно достаточно места для хранения всего, но оно, кажется, масштабируется довольно хорошо.

def daniel_sieve_2(maxNumber):
    """
    Given a number, returns all numbers less than or equal to
    that number which are prime.
    """
    allNumbers = range(3, maxNumber+1, 2)
    for mIndex, number in enumerate(xrange(3, maxNumber+1, 2)):
        if allNumbers[mIndex] == 0:
            continue
        # now set all multiples to 0
        for index in xrange(mIndex+number, (maxNumber-3)/2+1, number):
            allNumbers[index] = 0
    return [2] + filter(lambda n: n!=0, allNumbers)

И результаты:

>>>mine = timeit.Timer("daniel_sieve_2(1000000)",
...                    "from sieves import daniel_sieve_2")
>>>prev = timeit.Timer("get_primes_erat(1000000)",
...                    "from sieves import get_primes_erat")
>>>print "Mine: {0:0.4f} ms".format(min(mine.repeat(3, 1))*1000)
Mine: 428.9446 ms
>>>print "Previous Best {0:0.4f} ms".format(min(prev.repeat(3, 1))*1000)
Previous Best 621.3581 ms

Если у вас есть контроль над N, самый быстрый способ перечислить все простые числа - это прекомпилировать их. Шутки в сторону. Предкомпиляция - это способ, который не учитывается при оптимизации.

Если вы принимаете itertools, но не numpy, вот адаптация rwh_primes2 для Python 3, которая работает на моей машине примерно в два раза быстрее. Единственным существенным изменением является использование bytearray вместо списка для логического и использование сжатия вместо понимания списка для создания окончательного списка. (Я бы добавил это как комментарий, например moarningsun, если бы я был в состоянии.)

import itertools
izip = itertools.zip_longest
chain = itertools.chain.from_iterable
compress = itertools.compress
def rwh_primes2_python3(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    zero = bytearray([False])
    size = n//3 + (n % 6 == 2)
    sieve = bytearray([True]) * size
    sieve[0] = False
    for i in range(int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        start = (k*k+4*k-2*k*(i&1))//3
        sieve[(k*k)//3::2*k]=zero*((size - (k*k)//3 - 1) // (2 * k) + 1)
        sieve[  start ::2*k]=zero*((size -   start  - 1) // (2 * k) + 1)
    ans = [2,3]
    poss = chain(izip(*[range(i, n, 6) for i in (1,5)]))
    ans.extend(compress(poss, sieve))
    return ans

Сравнения:

>>> timeit.timeit('primes.rwh_primes2(10**6)', setup='import primes', number=1)
0.0652179726976101
>>> timeit.timeit('primes.rwh_primes2_python3(10**6)', setup='import primes', number=1)
0.03267321276325674

и

>>> timeit.timeit('primes.rwh_primes2(10**8)', setup='import primes', number=1)
6.394284538007014
>>> timeit.timeit('primes.rwh_primes2_python3(10**8)', setup='import primes', number=1)
3.833829450302801

Используя сито Сундарама , я думаю, что я сломал запись чистого Python:

def sundaram3(max_n):
    numbers = range(3, max_n+1, 2)
    half = (max_n)//2
    initial = 4

    for step in xrange(3, max_n+1, 2):
        for i in xrange(initial, half, step):
            numbers[i-1] = 0
        initial += 2*(step+1)

        if initial > half:
            return [2] + filter(None, numbers)

Сравнение:

C:\USERS>python -m timeit -n10 -s "import get_primes" "get_primes.get_primes_erat(1000000)"
10 loops, best of 3: 710 msec per loop

C:\USERS>python -m timeit -n10 -s "import get_primes" "get_primes.daniel_sieve_2(1000000)"
10 loops, best of 3: 435 msec per loop

C:\USERS>python -m timeit -n10 -s "import get_primes" "get_primes.sundaram3(1000000)"
10 loops, best of 3: 327 msec per loop

Для действительно быстрого решения с достаточно большим N было бы загрузить предварительно просчитанный список простых чисел , сохранить его как кортеж и сделать что-то вроде:

for pos,i in enumerate(primes):
    if i > N:
        print primes[:pos]

Все написано и протестировано. Таким образом, нет необходимости изобретать колесо.

python -m timeit -r10 -s"from sympy import sieve" "primes = list(sieve.primerange(1, 10**6))"

дает нам рекордный разрыв 12,2 мс!

10 loops, best of 10: 12.2 msec per loop

Если это не достаточно быстро, вы можете попробовать PyPy:

pypy -m timeit -r10 -s"from sympy import sieve" "primes = list(sieve.primerange(1, 10**6))"

, в результате чего:

10 loops, best of 10: 2.03 msec per loop

Ответ с 247 списками голосов для 15,9 мс для лучшего решения. Сравните это !!!

Вот код, который я обычно использую для генерации простых чисел в Python:

$ python -mtimeit -s'import sieve' 'sieve.sieve(1000000)' 
10 loops, best of 3: 445 msec per loop
$ cat sieve.py
from math import sqrt

def sieve(size):
 prime=[True]*size
 rng=xrange
 limit=int(sqrt(size))

 for i in rng(3,limit+1,+2):
  if prime[i]:
   prime[i*i::+i]=[False]*len(prime[i*i::+i])

 return [2]+[i for i in rng(3,size,+2) if prime[i]]

if __name__=='__main__':
 print sieve(100)

Он не может конкурировать с более быстрыми решениями, размещенными здесь, но по крайней мере это чистый питон.

Спасибо, что опубликовал этот вопрос. Сегодня я многому научился.

Это можно сравнить с другими.

# You have to list primes upto n
nums = xrange(2, n)
for i in range(2, 10):
    nums = filter(lambda s: s==i or s%i, nums)
print nums

Так просто ...

Немного отличается реализация половинного сита с помощью Numpy:

http://rebrained.com/?p=458

import math
import numpy
def prime6(upto):
    primes=numpy.arange(3,upto+1,2)
    isprime=numpy.ones((upto-1)/2,dtype=bool)
    for factor in primes[:int(math.sqrt(upto))]:
        if isprime[(factor-2)/2]: isprime[(factor*3-2)/2:(upto-1)/2:factor]=0
    return numpy.insert(primes[isprime],0,2)

Может ли кто-то сравнить это с другими таймингами? На моей машине это кажется довольно сопоставимым с другим полурешеткой Numpy.

В общем случае, если вам нужно быстрое вычисление числа, python не лучший выбор. Сегодня существует много более быстрого (и сложного) алгоритма. Например, на моем компьютере я получил 2,2 секунды для вашего кода, а Mathematica получил 0.088005.

Прежде всего: вам нужно установить?

Детерминированная реализация теста Первичности Миллера-Рабина в предположении, что N & lt; 9,080,191

import sys
import random

def miller_rabin_pass(a, n):
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1

    a_to_power = pow(a, d, n)
    if a_to_power == 1:
        return True
    for i in xrange(s-1):
        if a_to_power == n - 1:
            return True
        a_to_power = (a_to_power * a_to_power) % n
    return a_to_power == n - 1


def miller_rabin(n):
    for a in [2, 3, 37, 73]:
      if not miller_rabin_pass(a, n):
        return False
    return True


n = int(sys.argv[1])
primes = [2]
for p in range(3,n,2):
  if miller_rabin(p):
    primes.append(p)
print len(primes)

Согласно статье в Википедии ( http://en.wikipedia.org/wiki/Miller-Rabin_primality_test ) тестирование N & lt; 9,080,191 для a = 2,3,37 и 73 достаточно, чтобы решить, является ли N составным или нет.

И я адаптировал исходный код из вероятностной реализации оригинального теста Миллера-Рабина, найденного здесь: http://en.literateprograms.org/Miller-Rabin_primality_test_ (Python)

Первый раз, используя python, поэтому некоторые из методов, которые я использую в этом, могут показаться немного громоздкими. Я просто конвертировал свой код на C ++ в python, и это то, что у меня есть (хотя и немного медленный в python)

#!/usr/bin/env python
import time

def GetPrimes(n):

    Sieve = [1 for x in xrange(n)]

    Done = False
    w = 3

    while not Done:

        for q in xrange (3, n, 2):
            Prod = w*q
            if Prod < n:
                Sieve[Prod] = 0
            else:
                break

        if w > (n/2):
            Done = True
        w += 2

    return Sieve



start = time.clock()

d = 10000000
Primes = GetPrimes(d)

count = 1 #This is for 2

for x in xrange (3, d, 2):
    if Primes[x]:
        count+=1

elapsed = (time.clock() - start)
print "\nFound", count, "primes in", elapsed, "seconds!\n"

pythonw Primes.py

Найдено 664579

#!/usr/bin/env python
import time

def GetPrimes2(n):

    Sieve = [1 for x in xrange(n)]

    for q in xrange (3, n, 2):
        k = q
        for y in xrange(k*3, n, k*2):
            Sieve[y] = 0

    return Sieve



start = time.clock()

d = 10000000
Primes = GetPrimes2(d)

count = 1 #This is for 2

for x in xrange (3, d, 2):
    if Primes[x]:
        count+=1

elapsed = (time.clock() - start)
print "\nFound", count, "primes in", elapsed, "seconds!\n"

pythonw Primes2.py

Найдено 664579 простых чисел за 10.230172 секунд!

#!/usr/bin/env python
import time

def GetPrimes3(n):

    Sieve = [1 for x in xrange(n)]

    for q in xrange (3, n, 2):
        k = q
        for y in xrange(k*k, n, k << 1):
            Sieve[y] = 0

    return Sieve



start = time.clock()

d = 10000000
Primes = GetPrimes3(d)

count = 1 #This is for 2

for x in xrange (3, d, 2):
    if Primes[x]:
        count+=1

elapsed = (time.clock() - start)
print "\nFound", count, "primes in", elapsed, "seconds!\n"

python Primes2.py

Найдено 664579 простых чисел в 7.113776 секунд!

Для Python 3

def rwh_primes2(n):
    correction = (n%6>1)
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
    sieve = [True] * (n//3)
    sieve[0] = False
    for i in range(int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      ((k*k)//3)      ::2*k]=[False]*((n//6-(k*k)//6-1)//k+1)
        sieve[(k*k+4*k-2*k*(i&1))//3::2*k]=[False]*((n//6-(k*k+4*k-2*k*(i&1))//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

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

from time import time
# 175 ms for all the primes up to the value 10**6
def primes_sieve(limit):
    a = [True] * limit
    a[0] = a[1] = False
    #a[2] = True
    for n in xrange(4, limit, 2):
        a[n] = False
    root_limit = int(limit**.5)+1
    for i in xrange(3,root_limit):
        if a[i]:
            for n in xrange(i*i, limit, 2*i):
                a[n] = False
    return a

LIMIT = 10**6
s=time()
primes = primes_sieve(LIMIT)
print time()-s

Алгоритм работает быстро, но имеет серьезный недостаток:

>>> sorted(get_primes(530))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 527, 529]
>>> 17*31
527
>>> 23*23
529

Вы предполагаете, что numbers.pop() вернет наименьшее число в наборе, но это не гарантируется вообще. Наборы неупорядочены, а pop() удаляет и возвращает произвольный элемент, поэтому его нельзя использовать для выбора следующего простого числа из оставшихся чисел.

Извините за беспокойство, но erat2 () имеет серьезный недостаток в алгоритме.

При поиске следующего композита нам нужно проверить только нечетные числа. q, p оба нечетны; то q + p четно и не нуждается в проверке, но q + 2 * p всегда нечетно. Это исключает проверку «если даже» в условиях цикла while и экономит около 30% времени выполнения.

Пока мы находимся в этом: вместо элегантного «D.pop (q, None)», get и delete использовать метод ', если q в D: p = D [q], del D [q]', что вдвое быстрее! По крайней мере, на моей машине (P3-1Ghz). Поэтому я предлагаю эту реализацию этого умного алгоритма:

def erat3( ):
    from itertools import islice, count

    # q is the running integer that's checked for primeness.
    # yield 2 and no other even number thereafter
    yield 2
    D = {}
    # no need to mark D[4] as we will test odd numbers only
    for q in islice(count(3),0,None,2):
        if q in D:                  #  is composite
            p = D[q]
            del D[q]
            # q is composite. p=D[q] is the first prime that
            # divides it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next
            # multiple of its witnesses to prepare for larger
            # numbers.
            x = q + p+p        # next odd(!) multiple
            while x in D:      # skip composites
                x += p+p
            D[x] = p
        else:                  # is prime
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations.
            D[q*q] = q
            yield q

Это элегантное и более простое решение для поиска простых чисел с использованием сохраненного списка. Начинается с 4 переменных, вам нужно только проверять нечетные простые числа для делителей, и вам нужно проверить только половину того числа, которое вы тестируете как простое (нет смысла тестировать, делят ли 9, 11, 13 на 17) , Он проверяет ранее сохраненные простые числа как делители. `

    # Program to calculate Primes
 primes = [1,3,5,7]
for n in range(9,100000,2):
    for x in range(1,(len(primes)/2)):
        if n % primes[x] == 0:
            break
    else:
        primes.append(n)
print primes