Essayez d'implémenter le tamis Eratostenes en utilisant la bibliothèque standard de Java

introduction

Je développe généralement des logiciels packagés, mais j'ai récemment commencé un pro de la concurrence. C'était complètement différent de la façon habituelle d'écrire du code, donc j'étais très confus (je résolvais le problème en pensant que je ne serais pas tué si j'écrivais un tel code), et je me demandais ce qui se passerait si j'implémentais cela comme d'habitude.

Dans un tel cas, le tamis [Java] Eratostenes de @ nkojima trouve le nombre premier et le tamis [Java] Eratostenes trouve le nombre premier (partie 2) , j'ai pensé que ce serait un bon sujet, j'ai donc essayé d'améliorer la lisibilité en utilisant la bibliothèque standard.

À ce stade, j'essaierai d'utiliser correctement la collection.

code

[Java] Recherche de nombres premiers avec un tamis d'erratostines (2), reportez-vous à ʻArrayList, HashSet`, ʻArrayList <Boolean Je l'ai changé en> ʻet je l'ai implémenté.

ListImplement.java

package practise.algorithm.eratosthenes.qiita;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class ListImplement {
	private static final int MIN_PRIME_NUMBER = 2;

	public static void main(String[] args) {
		new ListImplement().execute();
	}

	private void execute() {
		Scanner sc = new Scanner(System.in);
		int maxNumber = sc.nextInt();

		List<Integer> primeNumbers = enumeratePrimeNumbers(maxNumber);

		System.out.println(primeNumbers.toString());
	}

	private List<Integer> enumeratePrimeNumbers(int maxNumber) {
		List<Integer> targets = createSearchTargets(maxNumber);

		sieve(targets, maxNumber);

		return targets;
	}

	//Créer une liste de recherche de 2 à maxNumber
	private List<Integer> createSearchTargets(int maxNumber) {
		List<Integer> targets = new ArrayList<>(maxNumber);
		for(int i = MIN_PRIME_NUMBER; i <= maxNumber; i++) {
			targets.add(i);
		}
		return targets;
	}

	//Filtrer les multiples de la première valeur dans la liste de recherche à partir de la liste de recherche
	//Faites ce qui précède jusqu'à ce que la valeur de début de la liste de recherche atteigne la racine carrée de maxNumber.
	private void sieve(List<Integer> targets, int maxNumber) {
		int sqrt = (int)  Math.sqrt(maxNumber);
		for(int i = MIN_PRIME_NUMBER; i <= sqrt; i++) {
			int firstNum = i;
			if(targets.contains(firstNum)) {//★★★ La partie qui détermine s'il s'agit d'un tamis ou non ★★★
				//Puisque le carré de la première valeur a déjà été filtré
				for(int j = firstNum * firstNum; j <= maxNumber; j += firstNum) {
					targets.remove(Integer.valueOf(j));//★★★ Pièce de tamisage ★★★
				}
			}
		}
	}

}

SetImplement.java

package practise.algorithm.eratosthenes.qiita;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class SetImplement {
	private static final int MIN_PRIME_NUMBER = 2;

	public static void main(String[] args) {
		new SetImplement().execute();
	}

	private void execute() {
		Scanner sc = new Scanner(System.in);
		int maxNumber = sc.nextInt();

		Set<Integer> primeNumbers = enumeratePrimeNumbers(maxNumber);

		System.out.println(primeNumbers.toString());
	}

	private Set<Integer> enumeratePrimeNumbers(int maxNumber) {
		Set<Integer> targets = createSearchTargets(maxNumber);

		sieve(targets, maxNumber);

		return targets;
	}

	//Faire une liste numérique de 2 à maxNumber
	private Set<Integer> createSearchTargets(int maxNumber) {
		Set<Integer> targets = new HashSet<>(maxNumber);
		for(int i = MIN_PRIME_NUMBER; i <= maxNumber; i++) {
			targets.add(i);
		}
		return targets;
	}

	//Filtrer les multiples de la première valeur dans la liste de recherche à partir de la liste de recherche
	//Faites ce qui précède jusqu'à ce que la valeur de début de la liste de recherche atteigne la racine carrée de maxNumber.
	private void sieve(Set<Integer> targets, int maxNumber) {
		int sqrt = (int)  Math.sqrt(maxNumber);
		for(int i = MIN_PRIME_NUMBER; i <= sqrt; i++) {
			int firstNum = i;
			if(targets.contains(firstNum)) {//★★★ La partie qui détermine s'il s'agit d'un tamis ou non ★★★
				//Puisque le carré de la première valeur a déjà été filtré
				for(int j = firstNum * firstNum; j <= maxNumber; j += firstNum) {
					targets.remove(j);//★★★ Pièce de tamisage ★★★
				}
			}
		}
	}
}

BooleanArrayListImplement.java

package practise.algorithm.eratosthenes.qiita;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BooleanArrayListImplement {
	private static final int MIN_PRIME_NUMBER = 2;

	public static void main(String[] args) {
		new BooleanArrayListImplement().execute();
	}

	private void execute() {
		Scanner sc = new Scanner(System.in);
		int maxNumber = sc.nextInt();

		List<Integer> primeNumbers = enumeratePrimeNumbers(maxNumber);

		System.out.println(primeNumbers.toString());
	}

	private List<Integer> enumeratePrimeNumbers(int maxNumber) {
		List<Boolean> targets = createSearchTargets(maxNumber);

		List<Integer> primeNumbers = extracePrimeNumbers(targets);

		return primeNumbers;
	}

	//Créer une liste de recherche booléenne de 0 à maxNumber
	//Commencez à partir de 0 pour définir l'index comme le nombre de cibles de recherche
	//Que ce soit un nombre premier ou non est jugé par booléen
	private List<Boolean> createSearchTargets(int maxNumber) {
		List<Boolean> targets = new ArrayList<>(maxNumber + 1);
		targets.add(false);//Parce que 0 n'est pas un nombre premier
		targets.add(false);//Parce que 1 n'est pas un nombre premier
		for(int i = MIN_PRIME_NUMBER; i <= maxNumber; i++) {
			targets.add(true);
		}
		return targets;
	}

	//Filtrer les multiples de la première valeur de la liste de recherche dans la liste de recherche
	//Faites ce qui précède jusqu'à ce que la valeur de début de la liste de recherche atteigne la racine carrée de maxNumber.
	private List<Integer> extracePrimeNumbers(List<Boolean> targets) {
		int maxNumber = targets.size() - 1;

		sieve(targets, maxNumber);

		List<Integer> primeNumbers = convertToNumList(targets);

		return primeNumbers;
	}

	private void sieve(List<Boolean> targets, int maxNumber) {
		int sqrt = (int)  Math.sqrt(maxNumber);
		for(int i = MIN_PRIME_NUMBER; i <= sqrt; i++) {
			int firstNum = i;
			if(targets.get(i)) {//★★★ La partie qui détermine s'il s'agit d'un tamis ou non ★★★
				//Puisque le carré de la première valeur a déjà été filtré
				for(int j = firstNum * firstNum; j <= maxNumber; j += firstNum) {
					targets.set(j, false);//★★★ Pièce de tamisage ★★★
				}
			}
		}
	}

	private List<Integer> convertToNumList(List<Boolean> targets) {
		List<Integer> numbers = new ArrayList<>();
		for(int i = 0; i < targets.size(); i++) {
			if(targets.get(i)) {
				numbers.add(i);
			}
		}
		return numbers;
	}
}

Résumé de la vitesse

Il s'agit d'un résumé du temps d'exécution (moyenne de 5 exécutions). ʻArrayList est le plus rapide, et ʻArrayList est hors de question. Aucune des implémentations utilisant des tableaux ne se réalisera. .. ..

Cause de la différence de vitesse

J'ai écrit une note ★ dans le code, mais je pense que les deux points suivants sont les principaux facteurs.

-La partie qui détermine s'il s'agit d'un tamis --Partie de tamisage

Les éléments sont accessibles à chaque endroit, et la méthode d'accès à ce moment est la suivante.

• Implémentation de ʻArrayList`: Recherche à partir de l'avant du tableau → Recherche linéaire
• Implémentation de HashSet: Accéder à l'objet cible avec une table de hachage → Accès aléatoire via table de hachage
• Implémentation de ʻArrayList `: Accéder au tableau par index → Accès aléatoire

Après tout, l'ordre calculé est ʻArrayListest $ O (n ^ 2 loglogn) $,HashSet et ʻArrayList <Boolean> sont $ O (nloglogn) $ (En regardant les résultats de l'exécution, je ne pense pas que ce soit le cas avec cette implémentation. .) Je pense que c'est. (La partie loglogn a été recherchée sur Google. [Cet article](https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0#%E4%BE%8B-14-%E3%82%A8%E3%83%A9 % E3% 83% 88% E3% 82% B9% E3% 83% 86% E3% 83% 8D% E3% 82% B9% E3% 81% AE% E3% 81% B5% E3% 82% 8B% E3 Il y a aussi% 81% 84-on-loglogn).)

Les tableaux sont plus rapides que ʻArrayList et ʻArrayList <Boolean> que HashSet car il n'y a pas de calcul de valeur de hachage lors de l'accès à l'élément, et il n'y a aucune opération pour étendre le tableau. Probablement parce qu'il n'y a pas d'autres opérations supplémentaires.

Résumé

Quand je l'ai essayé, je me suis senti comme suit.

• Lorsqu'elle est utilisée dans la pratique, la vitesse sera un peu plus lente, mais la lisibilité sera importante, alors mettez en œuvre Set. --Lorsque la vitesse est importante, écrivez un commentaire et implémentez le tableau. --ʻArrayList ʻSi vous l'utilisez, faites-en un tableau (les commentaires sont obligatoires de toute façon)

C'est intéressant de voir beaucoup d'algorithmes que je n'ai jamais vus auparavant quand je fais un pro de la compétition. C'est à cette époque que je souhaite faire bon usage de mon entreprise.

finalement

――Lors de la sélection d'une structure de données de type collection, je l'ai implémentée comme s'il s'agissait d'un ensemble pour éliminer les doublons et d'une liste s'il y avait des doublons. Je suis content de l'avoir remarqué maintenant, simplement parce que cela n'a pas tellement affecté la vitesse que cela s'est avéré être un problème. «Merci à @nkojima pour avoir rédigé un merveilleux article, j'ai pu étudier dur. Je vous remercie. «Je pense qu'il y a beaucoup d'endroits où vous n'avez pas assez étudié, mais s'il y a quelque chose qui ne va pas, j'aimerais que vous jetiez doucement Masakari.