Accélérer les opérations sur les chaînes de bits/bit en Python ?

Question

J'ai écrit un générateur de nombres premiers en utilisant Le tamis d'Eratosthène et Python 3.1. Le code s'exécute correctement et gracieusement en 0,32 secondes sur ideone.com pour générer des nombres premiers jusqu'à 1.000.000.

# from bitstring import BitString

def prime_numbers(limit=1000000):
    '''Prime number generator. Yields the series
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...    
    using Sieve of Eratosthenes.
    '''
    yield 2
    sub_limit = int(limit**0.5) 
    flags = [False, False] + [True] * (limit - 2)   
#     flags = BitString(limit)
    # Step through all the odd numbers
    for i in range(3, limit, 2):       
        if flags[i] is False:
#        if flags[i] is True:
            continue
        yield i
        # Exclude further multiples of the current prime number
        if i <= sub_limit:
            for j in range(i*3, limit, i<<1):
                flags[j] = False
#                flags[j] = True

Le problème est que je manque de mémoire lorsque j'essaie de générer des nombres jusqu'à 1 000 000 000.

    flags = [False, False] + [True] * (limit - 2)   
MemoryError

Comme vous pouvez l'imaginer, allouer 1 milliard de valeurs booléennes ( 1 octet 4 ou 8 octets (voir le commentaire) chacun en Python) n'est vraiment pas faisable, alors j'ai cherché dans chaîne de bits . Je me suis dit que l'utilisation d'un bit pour chaque drapeau serait beaucoup plus efficace en mémoire. Cependant, les performances du programme ont chuté de façon drastique - 24 secondes d'exécution, pour des nombres premiers jusqu'à 1.000.000. Ceci est probablement dû à l'implémentation interne de bitstring.

Vous pouvez commenter/décommenter les trois lignes pour voir ce que j'ai changé pour utiliser BitString, comme le bout de code ci-dessus.

Ma question est la suivante , Y a-t-il un moyen d'accélérer mon programme, avec ou sans bitstring ?

Edit : Veuillez tester le code vous-même avant de le poster. Je ne peux pas accepter des réponses qui fonctionnent plus lentement que mon code existant, naturellement.

Modifiez à nouveau :

J'ai compilé une liste de repères sur ma machine.

Answer 1

Il y a quelques petites optimisations pour votre version. En inversant les rôles de True et False, vous pouvez changer " if flags[i] is False: " à " if flags[i]: ". Et la valeur de départ pour le deuxième range La déclaration peut être i*i au lieu de i*3 . Votre version originale prend 0,166 secondes sur mon système. Avec ces changements, la version ci-dessous prend 0,156 secondes sur mon système.

def prime_numbers(limit=1000000):
    '''Prime number generator. Yields the series
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
    using Sieve of Eratosthenes.
    '''
    yield 2
    sub_limit = int(limit**0.5)
    flags = [True, True] + [False] * (limit - 2)
    # Step through all the odd numbers
    for i in range(3, limit, 2):
        if flags[i]:
            continue
        yield i
        # Exclude further multiples of the current prime number
        if i <= sub_limit:
            for j in range(i*i, limit, i<<1):
                flags[j] = True

Cela n'aide pas votre problème de mémoire, cependant.

Pour entrer dans le monde des extensions C, j'ai utilisé la version de développement de gmpy . (La version de développement s'appelle gmpy2 et supporte les entiers mutables appelés xmpz. En utilisant gmpy2 et le code suivant, j'ai un temps d'exécution de 0,140 secondes. Le temps d'exécution pour une limite de 1.000.000.000 est de 158 secondes.

import gmpy2

def prime_numbers(limit=1000000):
    '''Prime number generator. Yields the series
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
    using Sieve of Eratosthenes.
    '''
    yield 2
    sub_limit = int(limit**0.5)
    # Actual number is 2*bit_position + 1.
    oddnums = gmpy2.xmpz(1)
    current = 0
    while True:
        current += 1
        current = oddnums.bit_scan0(current)
        prime = 2 * current + 1
        if prime > limit:
            break
        yield prime
        # Exclude further multiples of the current prime number
        if prime <= sub_limit:
            for j in range(2*current*(current+1), limit>>1, prime):
                oddnums.bit_set(j)

En poussant les optimisations, et en sacrifiant la clarté, j'obtiens des temps d'exécution de 0,107 et 123 secondes avec le code suivant :

import gmpy2

def prime_numbers(limit=1000000):
    '''Prime number generator. Yields the series
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
    using Sieve of Eratosthenes.
    '''
    yield 2
    sub_limit = int(limit**0.5)
    # Actual number is 2*bit_position + 1.
    oddnums = gmpy2.xmpz(1)
    f_set = oddnums.bit_set
    f_scan0 = oddnums.bit_scan0
    current = 0
    while True:
        current += 1
        current = f_scan0(current)
        prime = 2 * current + 1
        if prime > limit:
            break
        yield prime
        # Exclude further multiples of the current prime number
        if prime <= sub_limit:
            list(map(f_set,range(2*current*(current+1), limit>>1, prime)))

Edit : Sur la base de cet exercice, j'ai modifié gmpy2 pour accepter xmpz.bit_set(iterator) . En utilisant le code suivant, le temps d'exécution pour tous les nombres premiers inférieurs à 1 000 000 000 est de 56 secondes pour Python 2.7 et de 74 secondes pour Python 3.2. (Comme indiqué dans les commentaires, xrange est plus rapide que range .)

import gmpy2

try:
    range = xrange
except NameError:
    pass

def prime_numbers(limit=1000000):
    '''Prime number generator. Yields the series
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
    using Sieve of Eratosthenes.
    '''
    yield 2
    sub_limit = int(limit**0.5)
    oddnums = gmpy2.xmpz(1)
    f_scan0 = oddnums.bit_scan0
    current = 0
    while True:
        current += 1
        current = f_scan0(current)
        prime = 2 * current + 1
        if prime > limit:
            break
        yield prime
        if prime <= sub_limit:
            oddnums.bit_set(iter(range(2*current*(current+1), limit>>1, prime)))

Edit #2 : Encore un essai ! J'ai modifié gmpy2 pour accepter xmpz.bit_set(slice) . En utilisant le code suivant, le temps d'exécution pour tous les nombres premiers inférieurs à 1 000 000 000 est d'environ 40 secondes pour Python 2.7 et Python 3.2.

from __future__ import print_function
import time
import gmpy2

def prime_numbers(limit=1000000):
    '''Prime number generator. Yields the series
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
    using Sieve of Eratosthenes.
    '''
    yield 2
    sub_limit = int(limit**0.5)
    flags = gmpy2.xmpz(1)
    # pre-allocate the total length
    flags.bit_set((limit>>1)+1)
    f_scan0 = flags.bit_scan0
    current = 0
    while True:
        current += 1
        current = f_scan0(current)
        prime = 2 * current + 1
        if prime > limit:
            break
        yield prime
        if prime <= sub_limit:
            flags.bit_set(slice(2*current*(current+1), limit>>1, prime))

start = time.time()
result = list(prime_numbers(1000000000))
print(time.time() - start)

Edit #3 : J'ai mis à jour gmpy2 pour supporter correctement le découpage au niveau du bit d'un xmpz. Pas de changement dans les performances mais une API bien plus agréable. J'ai fait quelques ajustements et j'ai réussi à réduire le temps à environ 37 secondes. (Voir Edit #4 pour les changements dans gmpy2 2.0.0b1).

from __future__ import print_function
import time
import gmpy2

def prime_numbers(limit=1000000):
    '''Prime number generator. Yields the series
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
    using Sieve of Eratosthenes.
    '''
    sub_limit = int(limit**0.5)
    flags = gmpy2.xmpz(1)
    flags[(limit>>1)+1] = True
    f_scan0 = flags.bit_scan0
    current = 0
    prime = 2
    while prime <= sub_limit:
        yield prime
        current += 1
        current = f_scan0(current)
        prime = 2 * current + 1
        flags[2*current*(current+1):limit>>1:prime] = True
    while prime <= limit:
        yield prime
        current += 1
        current = f_scan0(current)
        prime = 2 * current + 1

start = time.time()
result = list(prime_numbers(1000000000))
print(time.time() - start)

Edit #4 : J'ai fait quelques changements dans gmpy2 2.0.0b1 qui cassent l'exemple précédent. gmpy2 ne traite plus True comme une valeur spéciale qui fournit une source infinie de 1-bits. -1 devrait être utilisé à la place.

from __future__ import print_function
import time
import gmpy2

def prime_numbers(limit=1000000):
    '''Prime number generator. Yields the series
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
    using Sieve of Eratosthenes.
    '''
    sub_limit = int(limit**0.5)
    flags = gmpy2.xmpz(1)
    flags[(limit>>1)+1] = 1
    f_scan0 = flags.bit_scan0
    current = 0
    prime = 2
    while prime <= sub_limit:
        yield prime
        current += 1
        current = f_scan0(current)
        prime = 2 * current + 1
        flags[2*current*(current+1):limit>>1:prime] = -1
    while prime <= limit:
        yield prime
        current += 1
        current = f_scan0(current)
        prime = 2 * current + 1

start = time.time()
result = list(prime_numbers(1000000000))
print(time.time() - start)

Edit #5 : J'ai apporté quelques améliorations à gmpy2 2.0.0b2. Vous pouvez maintenant itérer sur tous les bits qui sont soit activés soit désactivés. Le temps d'exécution a été amélioré de ~30%.

from __future__ import print_function
import time
import gmpy2

def sieve(limit=1000000):
    '''Returns a generator that yields the prime numbers up to limit.'''

    # Increment by 1 to account for the fact that slices do not include
    # the last index value but we do want to include the last value for
    # calculating a list of primes.
    sieve_limit = gmpy2.isqrt(limit) + 1
    limit += 1

    # Mark bit positions 0 and 1 as not prime.
    bitmap = gmpy2.xmpz(3)

    # Process 2 separately. This allows us to use p+p for the step size
    # when sieving the remaining primes.
    bitmap[4 : limit : 2] = -1

    # Sieve the remaining primes.
    for p in bitmap.iter_clear(3, sieve_limit):
        bitmap[p*p : limit : p+p] = -1

    return bitmap.iter_clear(2, limit)

if __name__ == "__main__":
    start = time.time()
    result = list(sieve(1000000000))
    print(time.time() - start)
    print(len(result))

Answer 2

OK, il s'agit de ma deuxième réponse, mais comme la rapidité est essentielle, j'ai pensé que je devais mentionner l'initiative de la Commission européenne. tableau de bits même s'il s'agit d'un module chaîne de bits La némésis de l'artiste :). Il est idéalement adapté à ce cas car non seulement il s'agit d'une extension C (et donc plus rapide que le Python pur n'a aucune chance de l'être), mais il supporte également les affectations de tranches.

Je n'ai même pas essayé d'optimiser ceci, j'ai juste réécrit la version bittring. Sur ma machine, j'obtiens 0,16 seconde pour les nombres premiers inférieurs à un million.

Pour un milliard, il fonctionne parfaitement bien et se termine en 2 minutes 31 secondes.

import bitarray

def prime_bitarray(limit=1000000):
    yield 2
    flags = bitarray.bitarray(limit)
    flags.setall(False)
    sub_limit = int(limit**0.5)
    for i in range(3, limit, 2):
        if not flags[i]:
            yield i
            if i <= sub_limit:
                flags[3*i:limit:i*2] = True

Answer 3

Ok, voici un benchmarking complet (presque complet) que j'ai fait ce soir pour voir quel code tourne le plus vite. J'espère que quelqu'un trouvera cette liste utile. J'ai omis tout ce qui prend plus de 30 secondes à compléter sur ma machine.

Je tiens à remercier tous ceux qui ont contribué. Vos efforts m'ont apporté beaucoup d'informations et j'espère que vous aussi.

Ma machine : AMD ZM-86, 2.40 Ghz Dual-Core, avec 4GB de RAM. C'est un ordinateur portable HP Touchsmart Tx2. Notez que bien que j'aie pu faire un lien vers un pastebin, J'ai testé tous les éléments suivants sur ma propre machine.

J'ajouterai le benchmark gmpy2 dès que je serai en mesure de le construire.

Tous les benchmarks sont testés dans Python 2.6 x86

Renvoi d'une liste de nombres premiers n jusqu'à 1.000.000 : ( Utilisation de Python générateurs)

Version du générateur numpy de Sebastian (mise à jour) - 121 ms @

Tamis + roue de Mark - 154 ms

La version de Robert avec le découpage en tranches - 159 ms

Ma version améliorée avec le découpage en tranches - 205 ms

Générateur Numpy avec enumerate - 249 ms @

Le tamis de base de Mark - 317 ms

l'amélioration de mon original par casevh solution - 343 ms

Ma solution modifiée pour le générateur numpy - 407 ms

Ma méthode originale dans le question - 409 ms

Solution Bitarray - 414 ms @

Python pur avec bytearray - 1394 ms @

La solution BitString de Scott - 6659 ms @

@" signifie que cette méthode est capable de générer jusqu'à n < 1.000.000.000 on ma configuration machine.

De plus, si vous n'avez pas besoin du générateur générateur et que vous voulez juste la liste complète en une seule fois :

solution numpy de RosettaCode - 32 ms @

(La solution numpy est également capable de générer jusqu'à 1 milliard, ce qui a pris 61,6259 secondes. Je soupçonne que la mémoire a été échangée une fois, d'où le temps double).

Answer 4

Question connexe : Le moyen le plus rapide de lister tous les nombres premiers inférieurs à N en python .

Bonjour, moi aussi je cherche un code en Python pour générer des nombres premiers jusqu'à 10^9 aussi vite que possible, ce qui est difficile en raison du problème de mémoire. Jusqu'à présent, j'ai trouvé ceci pour générer des nombres premiers jusqu'à 10^6 & 10^7 (respectivement 0,171s & 1,764s sur ma vieille machine), qui semble être légèrement plus rapide (du moins sur mon ordinateur) que "Ma version améliorée avec le découpage en tranches" du poste précédent, probablement parce que j'utilise n//i-i +1 (voir ci-dessous) au lieu de l'analogue len(flags[i2::i<<1]) dans l'autre code. Veuillez me corriger si je me trompe. Toute suggestion d'amélioration est la bienvenue.

def primes(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
    return [2] + [i for i in xrange(3,n,2) if sieve[i]]

Dans un de ses codes, Xavier utilise flags[i2::i<<1] y len(flags[i2::i<<1]) . J'ai calculé la taille explicitement, en utilisant le fait qu'entre i*i..n nous avons (n-i*i)//2*i des multiples de 2*i parce que nous voulons compter i*i nous additionnons aussi 1 así que len(sieve[i*i::2*i]) est égal à (n-i*i)//(2*i) +1 . Cela rend le code plus rapide. Un générateur de base basé sur le code ci-dessus serait :

def primesgen(n):
    """ Generates all primes <= n """
    sieve = [True] * n
    yield 2
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            yield i
            sieve[i*i::2*i] = [False]*((n-i*i-1)/(2*i)+1)
    for i in xrange(i+2,n,2):
        if sieve[i]: yield i

Avec un peu de modification, on peut écrire une version légèrement plus lente du code ci-dessus qui commence avec un tamis de la moitié de la taille de l'appareil. sieve = [True] * (n//2) et travaille pour le même n Je ne suis pas sûr que cela se reflète dans la question de la mémoire. A titre d'exemple de mise en œuvre, voici la version modifiée du code numpy rosetta (peut-être plus rapide) qui commence avec un tamis de la moitié de la taille.

import numpy
def primesfrom3to(n):
    """ Returns a array of primes, 3 <= p < n """
    sieve = numpy.ones(n/2, dtype=numpy.bool)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]: sieve[i*i/2::i] = False
    return 2*numpy.nonzero(sieve)[0][1::]+1

Un générateur plus rapide et plus économe en mémoire serait :

import numpy
def primesgen1(n):
""" Input n>=6, Generates all primes < n """
sieve1 = numpy.ones(n/6+1, dtype=numpy.bool)
sieve5 = numpy.ones(n/6  , dtype=numpy.bool)
sieve1[0] = False
yield 2; yield 3;
for i in xrange(int(n**0.5)/6+1):
    if sieve1[i]:
        k=6*i+1; yield k;
        sieve1[ ((k*k)/6) ::k] = False
        sieve5[(k*k+4*k)/6::k] = False
    if sieve5[i]:
        k=6*i+5; yield k;
        sieve1[ ((k*k)/6) ::k] = False
        sieve5[(k*k+2*k)/6::k] = False
for i in xrange(i+1,n/6):
        if sieve1[i]: yield 6*i+1
        if sieve5[i]: yield 6*i+5
if n%6 > 1:
    if sieve1[i+1]: yield 6*(i+1)+1

ou avec un peu plus de code :

import numpy
def primesgen(n):
    """ Input n>=30, Generates all primes < n """
    size = n/30 + 1
    sieve01 = numpy.ones(size, dtype=numpy.bool)
    sieve07 = numpy.ones(size, dtype=numpy.bool)
    sieve11 = numpy.ones(size, dtype=numpy.bool)
    sieve13 = numpy.ones(size, dtype=numpy.bool)
    sieve17 = numpy.ones(size, dtype=numpy.bool)
    sieve19 = numpy.ones(size, dtype=numpy.bool)
    sieve23 = numpy.ones(size, dtype=numpy.bool)
    sieve29 = numpy.ones(size, dtype=numpy.bool)
    sieve01[0] = False
    yield 2; yield 3; yield 5;
    for i in xrange(int(n**0.5)/30+1):
        if sieve01[i]:
            k=30*i+1; yield k;
            sieve01[     (k*k)/30::k] = False
            sieve07[(k*k+ 6*k)/30::k] = False
            sieve11[(k*k+10*k)/30::k] = False
            sieve13[(k*k+12*k)/30::k] = False
            sieve17[(k*k+16*k)/30::k] = False
            sieve19[(k*k+18*k)/30::k] = False
            sieve23[(k*k+22*k)/30::k] = False
            sieve29[(k*k+28*k)/30::k] = False
        if sieve07[i]:
            k=30*i+7; yield k;
            sieve01[(k*k+ 6*k)/30::k] = False
            sieve07[(k*k+24*k)/30::k] = False
            sieve11[(k*k+16*k)/30::k] = False
            sieve13[(k*k+12*k)/30::k] = False
            sieve17[(k*k+ 4*k)/30::k] = False
            sieve19[     (k*k)/30::k] = False
            sieve23[(k*k+22*k)/30::k] = False
            sieve29[(k*k+10*k)/30::k] = False
        if sieve11[i]:
            k=30*i+11; yield k;
            sieve01[     (k*k)/30::k] = False
            sieve07[(k*k+ 6*k)/30::k] = False
            sieve11[(k*k+20*k)/30::k] = False
            sieve13[(k*k+12*k)/30::k] = False
            sieve17[(k*k+26*k)/30::k] = False
            sieve19[(k*k+18*k)/30::k] = False
            sieve23[(k*k+ 2*k)/30::k] = False
            sieve29[(k*k+ 8*k)/30::k] = False
        if sieve13[i]:
            k=30*i+13; yield k;
            sieve01[(k*k+24*k)/30::k] = False
            sieve07[(k*k+ 6*k)/30::k] = False
            sieve11[(k*k+ 4*k)/30::k] = False
            sieve13[(k*k+18*k)/30::k] = False
            sieve17[(k*k+16*k)/30::k] = False
            sieve19[     (k*k)/30::k] = False
            sieve23[(k*k+28*k)/30::k] = False
            sieve29[(k*k+10*k)/30::k] = False
        if sieve17[i]:
            k=30*i+17; yield k;
            sieve01[(k*k+ 6*k)/30::k] = False
            sieve07[(k*k+24*k)/30::k] = False
            sieve11[(k*k+26*k)/30::k] = False
            sieve13[(k*k+12*k)/30::k] = False
            sieve17[(k*k+14*k)/30::k] = False
            sieve19[     (k*k)/30::k] = False
            sieve23[(k*k+ 2*k)/30::k] = False
            sieve29[(k*k+20*k)/30::k] = False
        if sieve19[i]:
            k=30*i+19; yield k;
            sieve01[     (k*k)/30::k] = False
            sieve07[(k*k+24*k)/30::k] = False
            sieve11[(k*k+10*k)/30::k] = False
            sieve13[(k*k+18*k)/30::k] = False
            sieve17[(k*k+ 4*k)/30::k] = False
            sieve19[(k*k+12*k)/30::k] = False
            sieve23[(k*k+28*k)/30::k] = False
            sieve29[(k*k+22*k)/30::k] = False
        if sieve23[i]:
            k=30*i+23; yield k;
            sieve01[(k*k+24*k)/30::k] = False
            sieve07[(k*k+ 6*k)/30::k] = False
            sieve11[(k*k+14*k)/30::k] = False
            sieve13[(k*k+18*k)/30::k] = False
            sieve17[(k*k+26*k)/30::k] = False
            sieve19[     (k*k)/30::k] = False
            sieve23[(k*k+ 8*k)/30::k] = False
            sieve29[(k*k+20*k)/30::k] = False
        if sieve29[i]:
            k=30*i+29; yield k;
            sieve01[     (k*k)/30::k] = False
            sieve07[(k*k+24*k)/30::k] = False
            sieve11[(k*k+20*k)/30::k] = False
            sieve13[(k*k+18*k)/30::k] = False
            sieve17[(k*k+14*k)/30::k] = False
            sieve19[(k*k+12*k)/30::k] = False
            sieve23[(k*k+ 8*k)/30::k] = False
            sieve29[(k*k+ 2*k)/30::k] = False
    for i in xrange(i+1,n/30):
            if sieve01[i]: yield 30*i+1
            if sieve07[i]: yield 30*i+7
            if sieve11[i]: yield 30*i+11
            if sieve13[i]: yield 30*i+13
            if sieve17[i]: yield 30*i+17
            if sieve19[i]: yield 30*i+19
            if sieve23[i]: yield 30*i+23
            if sieve29[i]: yield 30*i+29
    i += 1
    mod30 = n%30
    if mod30 > 1:
        if sieve01[i]: yield 30*i+1
    if mod30 > 7:
        if sieve07[i]: yield 30*i+7
    if mod30 > 11:
        if sieve11[i]: yield 30*i+11
    if mod30 > 13:
        if sieve13[i]: yield 30*i+13
    if mod30 > 17:
        if sieve17[i]: yield 30*i+17
    if mod30 > 19:
        if sieve19[i]: yield 30*i+19
    if mod30 > 23:
        if sieve23[i]: yield 30*i+23

Ps : Si vous avez des suggestions pour accélérer ce code, qu'il s'agisse de modifier l'ordre des opérations ou de pré-calculer quoi que ce soit, veuillez commenter.

Answer 5

Une amélioration de la vitesse que vous pouvez faire en utilisant bitstring est d'utiliser la méthode "set" lorsque vous excluez des multiples du nombre actuel.

La section vitale devient donc

for i in range(3, limit, 2):
    if flags[i]:
        yield i
        if i <= sub_limit:
            flags.set(1, range(i*3, limit, i*2))    

Sur ma machine, il fonctionne environ 3 fois plus vite que l'original.

J'ai également pensé à utiliser la chaîne de bits pour représenter uniquement les nombres impairs. Vous pourriez alors trouver les bits non définis en utilisant flags.findall([0]) qui renvoie un générateur. Je ne suis pas sûr que cela soit beaucoup plus rapide (trouver des modèles de bits n'est pas très facile à faire efficacement).

(Divulgation complète : j'ai écrit le module bitstring, donc j'ai une certaine fierté en jeu ici).

---

À titre de comparaison, j'ai également retiré les entrailles de la méthode bitstring pour qu'elle fonctionne de la même manière, mais sans vérification de la plage, etc. Je pense que cela donne une limite inférieure raisonnable pour du Python pur qui fonctionne pour un milliard d'éléments (sans changer l'algorithme, ce qui est une tricherie à mon avis !)

def prime_pure(limit=1000000):
    yield 2
    flags = bytearray((limit + 7) // 8)
    sub_limit = int(limit**0.5)
    for i in xrange(3, limit, 2):
        byte, bit = divmod(i, 8)
        if not flags[byte] & (128 >> bit):
            yield i
            if i <= sub_limit:
                for j in xrange(i*3, limit, i*2):
                    byte, bit = divmod(j, 8)
                    flags[byte] |= (128 >> bit)

Sur ma machine, cela fonctionne en environ 0,62 seconde pour un million d'éléments, ce qui signifie que cela représente environ un quart de la vitesse de la réponse par bitarray. Je pense que c'est tout à fait raisonnable pour du Python pur.