"Le Véritable Crible d'Eratosthène" en Python - pourquoi est-heapq plus lent que le dict?

Suivant M. O'Neill grand papier, j'ai essayé d'implémenter quelques versions paresseuses, infinies du tamis D'Eratosthène en Python. J'ai été surpris de constater que la version en tas, que le journal prétend devoir courir plus vite, était en fait deux fois plus lente pour moi.

Le livre contient deux exemples, l'un basé sur une dict, que j'ai traduit (à partir de Haskell) donc:

from itertools import count
def dict_sieve():
    yield 2
    yield 3
    candidates = count(5, 2)
    composites = {9:{3}}  # map composites to their prime factors

    for candidate in candidates:
        try:
            factors = composites.pop(candidate)
        except KeyError:  # if it's not in the dict, it's prime
            yield candidate
            composites[candidate**2] = {candidate}  # Euler's optimization: start from prime**2
        else:
            for prime in factors:  # go through the prime factors and increment their keys
                try:
                    composites[candidate+prime*2].add(prime)  # use prime*2 because we are ignoring evens
                except KeyError:
                    composites[candidate+prime*2] = {prime}

Le deuxième exemple dans le document démontre l'utilisation d'une priorité file d'attente comme structure de données. Il utilise aussi paresseux listes, plutôt qu'une simple incrémentation, je n'ai pas fait dans l'intérêt d'un test juste. (De plus, j'utilisais des exemples deitertools.count pour mon paresseux listes et je l'ai trouvé à courir un peu plus lent).

from itertools import count
from heapq import heappush, heapreplace
def heap_sieve():
    yield 2
    yield 3
    candidates = count(5,2)
    composites = [(9, 3)]  # a priority queue of composite/factor pairs, keyed by composite

    for candidate in candidates:
        prime_flag = True
        while composites[0][0] == candidate:  # loop because there may be duplicates
            prime_flag = False  # signal to the if statement below
            composite, prime = composites[0]
            heapreplace(composites, (composite + prime*2, prime))

        if prime_flag:
            yield candidate
            heappush(composites, (candidate**2, candidate))

j'ai programmé les deux, avec un "désireux" version, non reproduite ici, ce qui produit une liste de tous les nombres premiers en dessous d'une limite:

In [44]: from itertools import islice

In [45]: %timeit list(islice(dict_sieve(), 100000))
    ...: %timeit list(islice(heap_sieve(), 100000))
    ...: %timeit eager_sieve(1299710)  # 1299709 is the 100,000th prime
    ...: 
1 loops, best of 3: 2.12 s per loop
1 loops, best of 3: 4.94 s per loop
1 loops, best of 3: 677 ms per loop

il n'est pas surprenant que la version 'eager' soit beaucoup plus rapide - c'est essentiellement un compromis entre l'utilisation de la mémoire, de l'inconvénient d'avoir à spécifier une limite supérieure, et de temps PROCESSEUR. Cependant, J' trouver surprenant que le heapq version est beaucoup plus lent, quand le papier prétend d'être plus efficace. Est-ce un problème avec mon application? Ou est-ce simplement que, comme nous le savons tous, les dicts sont super-rapide (et heapq est relativement lent)?