Ich habe eine Methode, die eine obere Grenze hat und eine Liste von Primzahlen bis zu dieser Grenze zurückgibt.
%Vor%Ich entschied später, dass ich wirklich nur Nachschläge auf der Liste machen musste, oft nur die Frage "Is This Prime". Da ich mich mit allen Primzahlen unter Millionenwerten befasste, erkannte ich, dass HashSet die Struktur war, die ich verwenden sollte. Sicherlich war das Nachschlagen mit dem Ergebnis der Methode schneller, aber die Methode selbst war langsamer .
Ich glaube, der Grund dafür ist, dass HashSet vor dem Hinzufügen nach Duplikaten sucht, während eine Liste sie am Ende einfach verschiebt. Was mich überrascht hat und was die Frage und den Titel hervorbrachte, ist der Grund, warum ich mit einer Liste anfange und sie zum Erstellen von HashSet verwende:
%Vor%ist schneller als die Verwendung eines internen Hashsets, das einen Aufruf wie folgt ermöglicht:
%Vor%Wenn die Verlangsamung in der Duplikatsprüfung ist, sollte sie die gleiche Menge an Überprüfungen machen, egal was passiert, oder? Dies ist wahrscheinlich, wo mein Verständnis mich versagt.
Hier sind die Zeiten, die ich für Primzahlen unter einer Million bekomme.
Wenn der Grund dafür einfach erklärt werden kann, würde ich es gerne hören. Ich nehme an, dass zumindest das, was ich suche, ausreicht, um zu wissen, ob ich mit einer Liste oder einem HashSet anfangen sollte, wenn das Endergebnis ein großer HashSet von Items sein wird.
Ich habe den Hauptteil der Primzahlmethode unten hinzugefügt, aber beachte, dass die gesamte Interaktion mit der Datenstruktur (Code-weise) zwischen den beiden identisch ist. Ich glaube nicht, wie ich Daten zur Struktur hinzufüge, sollte die Anomalie beeinflussen.
%Vor%Bearbeiten: Auf Wunsch füge ich den Code für die Hash-Methode hinzu. Wenn es fast identisch aussieht, ist es das.
%Vor%Auf Anfrage ist auch der Code (hässlich hackisch), mit dem ich die Ausführungszeit getestet habe:
%Vor%//////////////////////////
%Vor% In AllPrimesUnder nummerieren Sie die Primzahl mehrmals (einmal für jeden Hauptkandidaten). Das Aufzählen eines List ist schneller als das Aufzählen eines HashSet , weil das interne Array des HashSet spärlicher ist.
Ich sehe den Code für AllPrimesUnder_Hash nicht rate , dass dies die Hauptursache ist.
Ich bin nicht davon überzeugt, dass die Größenänderung einer Liste von ein paar tausend Elementen 20ms verbrauchen könnte. Das Kopieren von Speicher mit memcpy (was intern geschieht) ist eine der Operationen mit dem höchsten Durchsatz, die Sie ausführen können. Sie können zehn Gigabyte pro Sekunde pro Kern kopieren.
Der Grund dafür ist, dass, wenn HashSet mit einer Sammlung initialisiert wird, die Größe der Sammlung verwendet werden kann, um die Kapazität festzulegen. Beim Hinzufügen von Werten zu einem leeren HashSet muss die Kapazität von Zeit zu Zeit erhöht werden, und das ist eine O (n) -Operation.
Aus irgendeinem Grund nimmt% code_de% nicht die Kapazität als Parameter im Konstruktor wie HashSet .
Wenn Sie Ihren Algorithmus betrachten, vermute ich, dass der reine Hash langsamer ist, weil es ein Hash ist, keine geordnete Liste. Wenn Sie eine geordnete Liste verwenden, testen Sie die Teilbarkeit gegen 2, 3, 5, 7 usw. in der Reihenfolge, so dass die kleineren Teiler (die üblicherweise Teiler sind) zuerst getestet werden. Wenn Sie einen Hash verwenden, ist die Reihenfolge willkürlich. Sie können also durch 23 teilbar machen, bevor Sie durch 3 teilbar machen.
Übrigens sollten Sie testnumber + = 2 verwenden und 2 von Ihrer Liste der Primzahlen ausschließen, indem Sie 2 einfügen, wenn Sie mit Ihrer Schleife fertig sind.
Noch besser: Sieb von Eratosthenes ist normalerweise eine schnellere Methode, um alle Primzahlen für relativ kleine Zahlen zu berechnen. Oder noch besser, berechnen Sie Ihre niedrigen Primzahlen vor und laden Sie sie von der Festplatte
BEARBEITEN - HINZUGEFÜGT
Nicht das, was ich anfangs erwartet habe (ein Hash ist nicht in Ordnung), aber es sieht in MoveNext () einfach so aus wie ein Overhead - und so funktioniert foreach intern
Vergleichen Sie den Unterschied in den MoveNext () - Funktionen, die Sie millionenfach in der innersten Schleife aufrufen werden.
%Vor%