Решето Эратосфена: что делает его быстрее


Я подумывала задачи 23 из проекта Эйлера. Она включает в себя сложности, где вы должны разложить на множители простых чисел. Я уже делал это в проблемы я решил ранее, но это было необходимо только для того, чтобы премьер-списка пока относительно небольшое количество.

Так я уже реализовал алгоритм, когда я взглянул на эту проблему. Я хранил номера в списке отмечены те, что не были простые числа и удалить их из списка, это в Python. Он работал хорошо для небольших списков, но когда я пошла по-крупному, использование памяти было слишком много.

Я еще хотел использовать алгоритм Эратосфена, но мне все еще нужно решение моей проблемы с памятью. Поэтому я решил, я не знаю, если это лучшее решение, чтобы записать список в файл и постоянно переписывать этот файл.

Мне удалось сделать этот алгоритм, но это не очень быстро. Чтобы найти простые числа до числа 20 000 он взял мою программу 405 секунд, или 6'45".

Есть ли способ я могу улучшить эту реализацию? Не перезаписывая файл, кэширования данных в оперативной памяти и т. д.?

SieveCash.py (В Python 3)

import tempfile
import os
import sys

def createSieve(outputFile, maxp, logging=0):
    """Creates a sieve and stores one prime per line in file outputFile."""
    # Write a list of all numbers to check to a file
    myNumFile = createBeginNumberList(maxp, outputFile)

    # Do the looping
    rfh = open(myNumFile, "r")
    try:
        totalRead = 0
        for i in range(maxp+1):
            # log if necessary
            if logging > 0 and i % logging == 0:
                print("Checking number", i, "(" + str(int(i/(maxp+1)*100)) + "%)")

            # do thingy
            bytesRead, myNum = readNumber(rfh)
            if bytesRead == 0:
                break

            totalRead += bytesRead

            if myNum != 0:
                rfh.close()
                rfh = None

                rewriteFileWithoutMultiples(myNumFile, myNum, totalRead)

                rfh = open(myNumFile, "r")
                rfh.seek(totalRead)

    finally:
        if rfh != None:
            rfh.close()

    # Remove zeros
    removeZerosInFile(outputFile)

    return myNumFile


def createBeginNumberList(maxn, fileName):
    """@return value: the file path"""

    tfh = open(fileName, "w")
    try:
        writeLineToFile(tfh, "0")
        writeLineToFile(tfh, "0")
        for i in range(2, maxn+1):
            writeLineToFile(tfh, str(i))
    finally:
        tfh.close()

    return fileName

def rewriteFileWithoutMultiples(inputFilename, multiple, startPos):
    rfh = open(inputFilename, "r")
    try:
        writeFile = tempfile.mkstemp()
        os.close(writeFile[0])
        wfh = open(writeFile[1], "w")
    except:
        rfh.close()
        raise

    # Rewrite file
    try:
        readBytes = 0
        while readBytes < startPos:
            b, aNum = readNumber(rfh)
            readBytes += b
            writeLineToFile(wfh, str(aNum))

        while True:
            b, aNum = readNumber(rfh)
            if aNum == None:
                break

            if aNum % multiple == 0:
                writeLineToFile(wfh, "0")
            else:
                writeLineToFile(wfh, str(aNum))
    finally:
        rfh.close()
        wfh.close()

    # Copy
    copyFile(writeFile[1], inputFilename)

def copyFile(source, dest):
    rfh = open(source, "r")
    try:
        wfh = open(dest, "w")
    except:
        rfh.close()
        raise

    try:
        aLine = rfh.readline()
        while len(aLine) != 0:
            wfh.write(aLine)
            aLine = rfh.readline()
    finally:
        rfh.close()
        wfh.close()

def removeZerosInFile(inputFile):
    rfh = open(inputFile, "r")
    try:
        writeFile = tempfile.mkstemp()
        os.close(writeFile[0])
        wfh = open(writeFile[1], "w")
    except:
        rfh.close()
        raise

    # Rewrite file
    try:
        while True:
            b, aNum = readNumber(rfh)
            if aNum == None:
                break

            if aNum != 0:
                writeLineToFile(wfh, str(aNum))

    finally:
        rfh.close()
        wfh.close()

    # Copy
    copyFile(writeFile[1], inputFile)



def writeLineToFile(fh, l):
    try:
        fh.write(l)
        fh.write('\n')
    except:
        fh.close()
        raise

def readNumber(fh):
    mynum = fh.readline()
    numb = len(mynum)
    mynum = mynum.strip('\n')

    if len(mynum) == 0:
        return (0, None)

    return (numb, int(mynum))

if __name__ == "__main__":
    if len(sys.argv) < 2:
        print("Usage:", sys.argv[0], "MAX_PRIME [LOG_INTERVAL]")
        sys.exit(1)

    maxp = int(sys.argv[1])
    logging = int(maxp / 100)
    try:
        logging = int(sys.argv[2])
    except:
        pass

    print("Creating seive until number", maxp, "with logging interval", logging)
    createSieve(os.path.expanduser("~/Desktop/Sieve-" + str(maxp) + ".txt"),
                maxp, logging)

Выход Программы (На iMac 2.16 ГГц Intel Соге 2 Duo, 1 ГБ оперативной памяти)

имак-Ван-ief2:23 ief2$ секунд=0; питон3 SieveCash.py 20000 2000; Эхо $секунд
Создание сито до 20000 с вырубкой интервал 2000
Проверив количество 0 (0%)
Проверка номер 2000 (9%)
Проверив количество 4000 (19%)
Контрольный номер 6000 (29%)
Контрольный номер 8000 (39%)
Проверив количество 10000 (49%)
Проверка кол-12000 (59%)
Проверка кол-14000 (69%)
Проверив количество 16000 (79%)
Проверка количества 18000 (89%)
Проверив количество 20000 (99%)
405



Комментарии
4 ответа

Если пространство является проблемой, немного-массив может помочь. Простой и unoptimised (я не так хорошо знаю питон),

import sys
import array

def sieve(n):
sieveBits = (n-1) // 2
sieveInts = (sieveBits+31) // 32
sieveBound = int(n**0.5) // 2
arr = array.array('I')
arr.extend((0,)*sieveInts)
for i in xrange(sieveBound):
if (arr[i >> 5] & (1 << (i&31))) == 0:
for j in xrange(2*i*(i+3)+3,sieveBits,2*i+3):
arr[j >> 5] |= 1 << (j&31)
return arr

def primes(n):
arr = sieve(n)
primes = [2] + [2*i+3 for i in xrange((n-1)//2) if arr[i >> 5] & (1 << (i & 31)) == 0]
return primes

if __name__ == "__main__":
if len(sys.argv) > 1:
up = int(sys.argv[1])
else:
up = 100000
print len(primes(up))

Это собака-медленно (4.6 секунд до сито до 10.000.000), но фильтровать не занимает много памяти.

2
ответ дан 2 декабря 2011 в 08:12 Источник Поделиться

Записи на диск будет очень медленно. Не делай этого.

Если вы работаете из памяти, попробуйте использовать стандартный модуль массива или библиотеки библиотеки numpy. Оба обеспечивают эффективную массивов для проведения большого числа ценностей. Ваш только уходит из памяти, потому что списки в Python не хранить свои ценности в памяти эффективным образом.

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

2
ответ дан 2 декабря 2011 в 11:12 Источник Поделиться

Вот мой вариант сита. Ideone находит 2262 простые числа меньше 20000 в 0.02 секунды.

def sieve(n):
m = (n-1) // 2
b = [True]*m
i,p,ps = 0,3,[2]
while p*p < n:
if b[i]:
ps.append(p)
j = 2*i*i + 6*i + 3
while j < m:
b[j] = False
j = j + 2*i + 3
i+=1; p+=2
while i < m:
if b[i]:
ps.append(p)
i+=1; p+=2
return ps

1
ответ дан 2 декабря 2011 в 08:12 Источник Поделиться

Одно незначительное улучшение-использовать xrange вместо диапазона. В вашем случае, вам не нужен диапазон, и xrange имеет лучшую производительность памяти, что может сделать небольшая разница.

0
ответ дан 2 декабря 2011 в 07:12 Источник Поделиться