Accélérer la division et la concaténation des chaînes de caractères

Question

J'essaie de résoudre Projet Problème d'Euler #35

Le nombre 197 est appelé nombre premier circulaire parce que toutes les rotations des chiffres le composent : 197, 971 et 719, sont elles-mêmes premières.

Combien y a-t-il de nombres premiers circulaires inférieurs à un million ?

Voici ma solution :

import numpy as np

def problem(n=100):

    circulars = np.array([], np.int32)

    p = np.array(sieveOfAtkin(n), np.int32)
    for prime in p:
        prime_str = str(prime)
        is_circular = True
        for i in xrange(len(prime_str)):
            m = int(prime_str[i:]+prime_str[:i])
            if not m in p:
                is_circular = False

        if is_circular:
            circulars = np.append(circulars, [prime])

    return len(circulars)

Malheureusement, la boucle for est très lente ! Une idée sur la façon d'accélérer le processus ? Je pense que la concaténation de la chaîne est le goulot d'étranglement, mais je n'en suis pas tout à fait sûr ! :)

---

Des idées ? :)

Answer 1

1. Utilisez un ensemble pour les tests d'appartenance au lieu d'un tableau. La recherche de hachage sera O(1) au lieu de O(n). C'est le goulot d'étranglement le plus important.

2. Sortez de la boucle dès que vous voyez qu'il ne s'agit pas d'une amorce circulaire au lieu d'essayer les autres rotations. Il s'agit là d'un autre goulot d'étranglement.

---

Ici, j'ai isolé le test de circularité dans une fonction pour permettre à la liste d'être construite avec une compréhension de liste. Le fait de l'avoir dans une fonction lui permet de renvoyer False dès que nous saurons qu'elle n'est pas circulaire. Une autre solution consisterait à le faire dans un for et break alors que nous savons qu'elle n'est pas circulaire. Ensuite, nous ajoutons à la liste dans la section else clause. D'une manière générale, les compilations de listes sont plus rapides que l'ajout dans une boucle. Ce n'est peut-être pas le cas ici, car cela ajoute une surcharge d'appels de fonction. Si vous vous souciez vraiment de la vitesse, il vaudrait la peine d'établir le profil des deux options.

primes = set(primes_to_one_million_however_you_want_to_get_them)

def is_circular(prime, primes=primes):
   prime_str = str(prime)
   # With thanks to Sven Marnach's comments
   return all(int(prime_str[i:]+prime_str[:i]) in primes 
              for i in xrange(len(prime_str)))

circular_primes = [p for p in primes if is_circular(p)]

J'ai également utilisé l'astuce consistant à passer un global comme argument par défaut à la fonction is_circular fonction. Cela signifie qu'il est possible d'y accéder à l'intérieur de la fonction en tant que variable locale au lieu d'une variable globale, ce qui est plus rapide.

Voici une façon de le coder en utilisant un else dans une boucle pour se débarrasser de ce drapeau hideux et améliorer l'efficacité.

circular = []
for p in primes:
   prime_str = str(prime)
   for i in xrange(len(prime_str)):
       if int(prime_str[i:]+prime_str[:i]) not in primes:
            break
   else:
       circular.append(p)