Versuchen Sie, das Eratostenes-Sieb mithilfe der Java-Standardbibliothek zu implementieren

Einführung

Normalerweise entwickle ich Softwarepakete, aber vor kurzem habe ich einen Wettbewerbsprofi gestartet. Es war völlig anders als die übliche Art, Code zu schreiben, daher war ich sehr verwirrt (ich löste das Problem und dachte, dass ich nicht getötet werden würde, wenn ich solchen Code schreibe), und ich fragte mich, was passieren würde, wenn ich dies wie gewohnt implementieren würde.

In einem solchen Fall findet das Eratostenes-Sieb von @ nkojima die Primzahl (https://qiita.com/nkojima/items/c20686f7b126809ee6e1) und das Eratostenes-Sieb von Java findet die Primzahl (Teil 2). ](Https://qiita.com/nkojima/items/199b9ba2d6ac3c694d17) dachte ich, es wäre ein gutes Thema, also habe ich versucht, die Lesbarkeit mithilfe der Standardbibliothek zu verbessern.

Zu diesem Zeitpunkt werde ich versuchen, die Sammlung ordnungsgemäß zu verwenden.

Code

[Java] Finden von Primzahlen mit einem Erratostinesieb (Teil 2) Ich habe es in> `geändert und implementiert.

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;
	}

	//Erstellen Sie eine Suchliste von 2 bis 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;
	}

	//Sieben Sie Vielfache des ersten Werts in der Suchliste aus der Suchliste
	//Führen Sie die obigen Schritte aus, bis der Startwert der Suchliste die Quadratwurzel von maxNumber erreicht.
	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)) {//★★★ Der Teil, der bestimmt, ob es sich um ein Sieb handelt oder nicht ★★★
				//Da das Quadrat des ersten Wertes bereits gescreent wurde
				for(int j = firstNum * firstNum; j <= maxNumber; j += firstNum) {
					targets.remove(Integer.valueOf(j));//★★★ Siebteil ★★★
				}
			}
		}
	}

}

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;
	}

	//Erstellen Sie eine numerische Liste von 2 bis 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;
	}

	//Sieben Sie Vielfache des ersten Werts in der Suchliste aus der Suchliste
	//Führen Sie die obigen Schritte aus, bis der Startwert der Suchliste die Quadratwurzel von maxNumber erreicht.
	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)) {//★★★ Der Teil, der bestimmt, ob es sich um ein Sieb handelt oder nicht ★★★
				//Da das Quadrat des ersten Wertes bereits gescreent wurde
				for(int j = firstNum * firstNum; j <= maxNumber; j += firstNum) {
					targets.remove(j);//★★★ Siebteil ★★★
				}
			}
		}
	}
}

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;
	}

	//Erstellen Sie eine boolesche Suchliste von 0 bis maxNumber
	//Beginnen Sie bei 0, um den Index als Anzahl der Suchziele festzulegen
	//Bestimmen Sie, ob es sich um eine Primzahl mit Booleschem Wert handelt
	private List<Boolean> createSearchTargets(int maxNumber) {
		List<Boolean> targets = new ArrayList<>(maxNumber + 1);
		targets.add(false);//Weil 0 keine Primzahl ist
		targets.add(false);//Weil 1 keine Primzahl ist
		for(int i = MIN_PRIME_NUMBER; i <= maxNumber; i++) {
			targets.add(true);
		}
		return targets;
	}

	//Sieben Sie Vielfache des ersten Werts in der Suchliste aus der Suchliste
	//Führen Sie die obigen Schritte aus, bis der Startwert der Suchliste die Quadratwurzel von maxNumber erreicht.
	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)) {//★★★ Der Teil, der bestimmt, ob es sich um ein Sieb handelt oder nicht ★★★
				//Da das Quadrat des ersten Wertes bereits gescreent wurde
				for(int j = firstNum * firstNum; j <= maxNumber; j += firstNum) {
					targets.set(j, false);//★★★ Siebteil ★★★
				}
			}
		}
	}

	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;
	}
}

Geschwindigkeitsübersicht

Es ist eine Zusammenfassung der Ausführungszeit (durchschnittlich 5 Ausführungen). "ArrayList " ist die schnellste und "ArrayList" kommt nicht in Frage. Keine der Implementierungen, die Arrays verwenden, wird wahr. .. ..

Ursache für den Geschwindigkeitsunterschied

• Der Teil, der bestimmt, ob es sich um ein Siebteil handelt oder nicht. - Auf das Element wird an jedem Teil des Siebteils zugegriffen. Die Zugriffsmethode ist zu diesem Zeitpunkt wie folgt. --Implementierung von ArrayList: Suche in der Reihenfolge von der Vorderseite des Arrays → Lineare Suche-Implementierung von HashSet: Zugriff auf das Zielobjekt mit einer Hash-Tabelle → Direktzugriff über Hash-Tabelle
• Implementierung von ArrayList : Zugriff auf ein Array über den Index → Direktzugriff

Immerhin ist die berechnete Reihenfolge ArrayList ist $ O (n ^ 2 loglogn) $, HashSet und ArrayList <Boolean> sind $ O (nloglogn) $ (Betrachtet man die Ausführungsergebnisse, so scheint dies bei dieser Implementierung nicht der Fall zu sein. .) Ich glaube, es ist. (Der loglogn-Teil wurde gegoogelt. [Dieser Artikel](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 Es gibt auch% 81% 84-on-loglogn).)

Das Array ist schneller als "ArrayList " und "ArrayList " als "HashSet", da beim Zugriff auf das Element keine Hashwertberechnung erfolgt und keine Operation zum Erweitern des Arrays erfolgt. Wahrscheinlich, weil es keine anderen zusätzlichen Operationen gibt.

Zusammenfassung

Als ich es tatsächlich versuchte, fühlte ich mich wie folgt.

--Wenn in der Praxis verwendet, ist die Geschwindigkeit etwas langsamer, aber die Lesbarkeit ist wichtig. Implementieren Sie daher Set.

• Wenn Geschwindigkeit wichtig ist, schreiben Sie einen Kommentar und implementieren Sie das Array. --ArrayList <Boolean> Machen Sie es zu einem Array, wenn Sie es verwenden (Kommentare sind trotzdem erforderlich)

Es ist interessant, viele Algorithmen zu sehen, die ich noch nie gesehen habe, wenn ich einen Wettkampfprofi mache. Ungefähr zu dieser Zeit möchte ich mein Geschäft gut nutzen.

Schließlich

――Wenn ich eine Datenstruktur vom Typ Sammlung ausgewählt habe, habe ich sie so implementiert, als wäre sie ein Set zum Entfernen von Duplikaten und eine Liste, wenn es Duplikate gibt. Ich bin froh, dass ich es jetzt bemerkt habe, nur weil es die Geschwindigkeit nicht so sehr beeinflusst hat, dass es zufällig ein Problem war. ――Danke an @nkojima für den wunderbaren Beitrag, ich konnte hart lernen. Vielen Dank. ――Ich denke, es gibt viele Orte, an denen Sie nicht genug gelernt haben, aber wenn etwas nicht stimmt, möchte ich, dass Sie Masakari sanft werfen.