Il ya environ un an, je travaillais à cette région pour la libc++ mise en œuvre de la
non ordonnée (hash) les conteneurs pour le C++11. Je pensais que je voudrais partager
mes expériences ici. Cette expérience prend en charge marcog accepté de répondre à une
raisonnable définition de "force brute".
Cela signifie que même une simple force brute va se faire assez vite en plus
circonstances, en prenant en O(ln(p)*sqrt(p)) en moyenne.
J'ai développé plusieurs implémentations de size_t next_prime(size_t n) où la
spec de cette fonction est:
Retourne: Le plus petit que le premier est supérieur ou égal à n.
Chaque mise en œuvre d' next_prime est accompagné par une fonction d'assistance is_prime. is_prime doit être considéré comme un privé détail de l'implémentation; ne doit pas être appelée directement par le client. Chacune de ces implémentations de cours a été testé pour la correction, mais aussi
testé avec le test de performances suivants:
int main()
{
typedef std::chrono::high_resolution_clock Clock;
typedef std::chrono::duration<double, std::milli> ms;
Clock::time_point t0 = Clock::now();
std::size_t n = 100000000;
std::size_t e = 100000;
for (std::size_t i = 0; i < e; ++i)
n = next_prime(n+1);
Clock::time_point t1 = Clock::now();
std::cout << e/ms(t1-t0).count() << " primes/millisecond\n";
return n;
}
Je tiens à souligner que c'est un test de performance, et ne reflète pas typique
d'utilisation, qui ressemblerait plus à:
// Overflow checking not shown for clarity purposes
n = next_prime(2*n + 1);
Tous les tests de performance ont été compilés avec:
clang++ -stdlib=libc++ -O3 main.cpp
Mise en œuvre 1
Il y a sept implémentations. Le but pour l'affichage de la première
la mise en œuvre est de démontrer que si vous ne parvenez pas à arrêter le test, le candidat
le premier x pour les facteurs à l' sqrt(x) alors vous n'avez pas à même d'atteindre un
la mise en œuvre qui pourraient être classés comme la force brute. Cette mise en œuvre est
brutalement lent.
bool
is_prime(std::size_t x)
{
if (x < 2)
return false;
for (std::size_t i = 2; i < x; ++i)
{
if (x % i == 0)
return false;
}
return true;
}
std::size_t
next_prime(std::size_t x)
{
for (; !is_prime(x); ++x)
;
return x;
}
Pour cette mise en œuvre seulement je devais e à 100 au lieu de 100000, juste pour
obtenir un temps d'exécution raisonnable:
0.0015282 primes/millisecond
Mise en œuvre 2
Cette mise en œuvre est le plus lent de la force brute de mise en œuvre et le
seule différence par rapport à la mise en œuvre 1 est qu'il s'arrête de test pour primeness
lorsque le facteur dépasse sqrt(x).
bool
is_prime(std::size_t x)
{
if (x < 2)
return false;
for (std::size_t i = 2; true; ++i)
{
std::size_t q = x / i;
if (q < i)
return true;
if (x % i == 0)
return false;
}
return true;
}
std::size_t
next_prime(std::size_t x)
{
for (; !is_prime(x); ++x)
;
return x;
}
Notez que sqrt(x) n'est pas calculée directement, mais déduite par l' q < i. Cette
de la vitesse par un facteur de milliers:
5.98576 primes/millisecond
et valide marcog de prédiction:
... c'est bien dans les limites de
la plupart des problèmes en prenant sur l'ordre de
un millième de seconde sur la plupart du matériel moderne.
La mise en œuvre 3
On peut presque le double de la vitesse (au moins sur le matériel que j'utilise) par
éviter l'utilisation de l' % opérateur:
bool
is_prime(std::size_t x)
{
if (x < 2)
return false;
for (std::size_t i = 2; true; ++i)
{
std::size_t q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
}
return true;
}
std::size_t
next_prime(std::size_t x)
{
for (; !is_prime(x); ++x)
;
return x;
}
11.0512 primes/millisecond
Mise en œuvre 4
Jusqu'à présent, je n'ai même pas utilisé la connaissance commune que le 2 est le seul à même le premier.
Cette application intègre des connaissances, près de doubler la vitesse
nouveau:
bool
is_prime(std::size_t x)
{
for (std::size_t i = 3; true; i += 2)
{
std::size_t q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
}
return true;
}
std::size_t
next_prime(std::size_t x)
{
if (x <= 2)
return 2;
if (!(x & 1))
++x;
for (; !is_prime(x); x += 2)
;
return x;
}
21.9846 primes/millisecond
Mise en œuvre 4 est probablement ce que la plupart des gens ont à l'esprit lorsqu'ils pensent à
"force brute".
La mise en œuvre 5
À l'aide de la formule suivante, vous pouvez choisir facilement tous les numéros qui sont
divisible ni par 2, ni 3:
6 * k + {1, 5}
où k >= 1. La suite de la mise en œuvre utilise cette formule, mais mis en œuvre
avec un mignon xor truc:
bool
is_prime(std::size_t x)
{
std::size_t o = 4;
for (std::size_t i = 5; true; i += o)
{
std::size_t q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
o ^= 6;
}
return true;
}
std::size_t
next_prime(std::size_t x)
{
switch (x)
{
case 0:
case 1:
case 2:
return 2;
case 3:
return 3;
case 4:
case 5:
return 5;
}
std::size_t k = x / 6;
std::size_t i = x - 6 * k;
std::size_t o = i < 2 ? 1 : 5;
x = 6 * k + o;
for (i = (3 + o) / 2; !is_prime(x); x += i)
i ^= 6;
return x;
}
Cela signifie que l'algorithme doit vérifier seulement 1/3 de l'
entiers pour primeness au lieu de 1/2 des nombres et le test de performance
affiche la vitesse attendue en hausse de près de 50%:
32.6167 primes/millisecond
La mise en œuvre 6
Cette application est une extension logique de la mise en œuvre 5: Il utilise le
formule suivante pour calculer tous les nombres qui ne sont pas divisibles par 2, 3 et 5:
30 * k + {1, 7, 11, 13, 17, 19, 23, 29}
Il a également déroule la boucle interne au sein de is_prime, et crée une liste de "petit
les nombres premiers", qui est utile pour traiter avec les numéros de moins de 30.
static const std::size_t small_primes[] =
{
2,
3,
5,
7,
11,
13,
17,
19,
23,
29
};
static const std::size_t indices[] =
{
1,
7,
11,
13,
17,
19,
23,
29
};
bool
is_prime(std::size_t x)
{
const size_t N = sizeof(small_primes) / sizeof(small_primes[0]);
for (std::size_t i = 3; i < N; ++i)
{
const std::size_t p = small_primes[i];
const std::size_t q = x / p;
if (q < p)
return true;
if (x == q * p)
return false;
}
for (std::size_t i = 31; true;)
{
std::size_t q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 6;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 4;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 2;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 4;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 2;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 4;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 6;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 2;
}
return true;
}
std::size_t
next_prime(std::size_t n)
{
const size_t L = 30;
const size_t N = sizeof(small_primes) / sizeof(small_primes[0]);
// If n is small enough, search in small_primes
if (n <= small_primes[N-1])
return *std::lower_bound(small_primes, small_primes + N, n);
// Else n > largest small_primes
// Start searching list of potential primes: L * k0 + indices[in]
const size_t M = sizeof(indices) / sizeof(indices[0]);
// Select first potential prime >= n
// Known a-priori n >= L
size_t k0 = n / L;
size_t in = std::lower_bound(indices, indices + M, n - k0 * L) - indices;
n = L * k0 + indices[in];
while (!is_prime(n))
{
if (++in == M)
{
++k0;
in = 0;
}
n = L * k0 + indices[in];
}
return n;
}
C'est sans doute aller au-delà des "force brute" et c'est bon pour stimuler la
la vitesse de l'autre de 27,5% à la:
41.6026 primes/millisecond
La mise en œuvre 7
C'est pratique pour jouer la partie pour une itération, le développement d'une
formule pour les nombres non divisible par 2, 3, 5 et 7:
210 * k + {1, 11, ...},
Le code source n'est pas montré ici, mais il est très similaire à la mise en œuvre 6.
C'est la mise en œuvre, j'ai choisi d'utiliser effectivement pour les contenants non ordonnée
de la libc++, et que le code source est open source (qui se trouve sur le lien).
Cette dernière itération est bon pour un autre de 14,6% boost de vitesse pour:
47.685 primes/millisecond
L'utilisation de cet algorithme assure que les clients de la libc++'s tables de hachage pouvez choisir
un premier ils décident qui est le plus bénéfique à leur situation, et de la performance
pour cette application est tout à fait acceptable.
