Problème de contrainte de mémoire du crible d'Eratosthène
Je suis actuellement en train de mettre en œuvre une version du crible d'Eratosthène pour un problème de Kattis, cependant, je rencontre des contraintes de mémoire que mon implémentation ne parvient pas à surpasser.
Voici un lien vers le énoncé du problème. En bref, le problème veut que je retourne d'abord le nombre de nombres premiers inférieur ou égal à n et ensuite résoudre pour un certain nombre de requêtes si un nombre i est premier ou non. Il y a une contrainte d'utilisation de mémoire de 50 Mo ainsi que l'utilisation uniquement des bibliothèques standard de python (pas de numpy, etc.). La contrainte de mémoire est là où je suis bloqué.
Voici mon code jusqu'à présent:
import sys
def sieve_of_eratosthenes(xs, n):
count = len(xs) + 1
p = 3 # Commencer à trois
index = 0
while p*p < n:
for i in range(index + p, len(xs), p):
if xs[i]:
xs[i] = 0
count -= 1
temp_index = index
for i in range(index + 1, len(xs)):
if xs[i]:
p = xs[i]
temp_index += 1
break
temp_index += 1
index = temp_index
return count
def isPrime(xs, a):
if a == 1:
return False
if a == 2:
return True
if not (a & 1):
return False
return bool(xs[(a >> 1) - 1])
def main():
n, q = map(int, sys.stdin.readline().split(' '))
odds = [num for num in range(2, n+1) if (num & 1)]
print(sieve_of_eratosthenes(odds, n))
for _ in range(q):
query = int(input())
if isPrime(odds, query):
print('1')
else:
print('0')
if __name__ == "__main__":
main()J'ai apporté certaines améliorations jusqu'à présent, comme le fait de ne conserver qu'une liste de tous les nombres impairs, ce qui divise par deux l'utilisation de la mémoire. Je suis également certain que le code fonctionne comme prévu lors du calcul des nombres premiers (sans obtenir de mauvaise réponse). Ma question maintenant est, comment puis-je rendre mon code encore plus efficace en termes de mémoire? Devrais-je utiliser d'autres structures de données? Remplacer ma liste d'entiers par des booléens? Bitarray?
Tout conseil est grandement apprécié!
ÉDITION
Après quelques ajustements au code en python, je me suis heurté à un mur où mon implémentation d'un crible segmenté ne parvenait pas à respecter les exigences en matière de mémoire.
À la place, j'ai choisi de mettre en œuvre la solution en Java, ce qui a nécessité très peu d'efforts. Voici le code:
public int sieveOfEratosthenes(int n){
sieve = new BitSet((n+1) / 2);
int count = (n + 1) / 2;
for (int i=3; i*i <= n; i += 2){
if (isComposite(i)) {
continue;
}
// Incrémenter de deux, en sautant tous les nombres pairs
for (int c = i * i; c <= n; c += 2 * i){
if(!isComposite(c)){
setComposite(c);
count--;
}
}
}
return count;
}
public boolean isComposite(int k) {
return sieve.get((k - 3) / 2); // Puisque nous ne gardons pas trace des nombres pairs
}
public void setComposite(int k) {
sieve.set((k - 3) / 2); // Puisque nous ne gardons pas trace des nombres pairs
}
public boolean isPrime(int a) {
if (a < 3)
return a > 1;
if (a == 2)
return true;
if ((a & 1) == 1)
return !isComposite(a);
else
return false;
}
public void run() throws Exception{
BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
String[] line = scan.readLine().split(" ");
int n = Integer.parseInt(line[0]); int q = Integer.parseInt(line[1]);
System.out.println(sieveOfEratosthenes(n));
for (int i=0; i < q; i++){
line = scan.readLine().split(" ");
System.out.println( isPrime(Integer.parseInt(line[0])) ? '1' : '0');
}
}Personnellement, je n'ai pas trouvé de moyen de mettre en œuvre cette solution BitSet en Python (en n'utilisant que la bibliothèque standard).
Si quelqu'un trouve une mise en œuvre intéressante du problème en python, en utilisant un crible segmenté, bitarray ou autre chose, je serais intéressé de voir la solution.
