Sieb von Eratosthenes: schneller machen

  • Ich habe darüber nachgedacht, das Problem 23 von Project Euler auszuführen. Es beinhaltet die Schwierigkeit, bei der Primzahlen faktorisiert werden müssen. Ich hatte das schon bei Problemen getan, die ich zuvor gelöst hatte, aber es war nur nötig, eine Primeliste zu haben, bis eine relativ kleine Zahl vorlag.

    Ich hatte den Algorithmus also bereits implementiert, als ich es nahm Ein Blick auf dieses Problem. Ich speicherte Zahlen in einer Liste, markierte diejenigen, die keine Primzahlen waren, und entfernte sie von der Liste. Dies alles in Python. Für kleine Listen hat es gut funktioniert, aber als ich groß wurde, war der Speicherbedarf einfach zu groß.

    Ich wollte immer noch den Algorithmus von Eratosthenes verwenden, brauchte aber immer noch eine Lösung zu meinem Gedächtnisproblem. Also entschied ich mich, ich weiß nicht, ob es die beste Lösung ist, die Liste in eine Datei zu schreiben und diese Datei ständig neu zu schreiben.

    Es ist mir gelungen, diesen Algorithmus zu erstellen. aber es ist nicht wirklich schnell. Um Primzahlen bis zur Zahl 20 000 zu finden, brauchte mein Programm 405 Sekunden oder 6'45 ".

    Gibt es eine Möglichkeit, diese Implementierung zu verbessern? Kein Umschreiben der Dateien, keine Einlösung Daten im RAM usw.?

     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)
     

    Programmausgabe (Auf einem iMac 2,16 GHz Intel Core 2 Duo mit 1 GB RAM)

    imac-van-ief2: 23 ief2 $ SECONDS = 0; python3 SieveCash.py 20000 2000; echo $ SECONDS
    Erstellen einer eigenen Nummer 20000 mit Protokollierung Intervall 2000
    Überprüfung der Nummer 0 (0%)
    Überprüfung der Nummer 2000 (9%)
    Überprüfung der Nummer 4000 (19%)
    Überprüfung der Nummer 6000 (29%)
    Überprüfung der Nummer 8000 (39%)
    Überprüfung der Nummer 10000 (49%)
    Überprüfung der Nummer 12000 (59%)
    Überprüfung der Nummer 14000 (69%)
    Überprüfungsnummer 16000 (79%)
    Überprüfungsnummer 18000 (89%)
    Überprüfungsnummer 20000 (99%)
    405 < br />

    21 May 2014
    Morwenn
4 answers
  • Wenn Leerzeichen das Problem ist, kann ein Bit-Array hilfreich sein. Unkompliziert und unoptimiert (ich kenne Python nicht so gut),

     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))
     

    Es ist langsam (4,6 Sekunden) (bis 10.000.000), aber das Sieben braucht nicht viel Speicher.

    03 December 2011
    Daniel Fischer
  • Das Schreiben auf die Festplatte wird sehr langsam sein. Tun Sie das nicht.

    Wenn Sie nicht genügend Speicher haben, versuchen Sie es mit dem Standard-Array-Modul oder der Numpy-Bibliothek. Beide bieten effiziente Arrays zum Speichern einer großen Anzahl von Werten. Ihnen fehlt nur der Speicher, da die Listen von Python ihre Werte nicht speichereffizient speichern.

    Wenn Sie aus irgendeinem Grund nicht genug Speicher haben, sollten Sie diesen Code hier posten, und wir erklären Ihnen gerne, wie Sie die Speichernutzung verbessern können / p>

    03 December 2011
    Mark Cidade
  • Hier ist meine Version des Siebs. Ideone findet die 2262-Primzahlen in 0,02 Sekunden unter 20000.

     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
     
    03 December 2011
    user448810
  • Eine kleine Verbesserung ist die Verwendung von xrange anstelle von range. In Ihrem Fall benötigen Sie range nicht, und xrange hat eine bessere Speicherleistung, was einen kleinen Unterschied machen kann.

    02 December 2011