Wie Array von Größe größer als Integer max zu erstellen

Question

Ich habe versucht, alle Primzahlen vor 600851475143 zu bekommen. Ich verwendete Sieb von Eratosthenes für diese. Dies erfordert, dass ich ein boolesches Array dieser riesigen Größe erstelle. Schlechte Idee, Sie können nicht genügend Arbeitsspeicher haben. Jeder andere Weg. Ich versuchte, eine Zeichenkette zu verwenden, jeden Index mit Werten 0 & 1 verwendend, um wahr oder falsch darzustellen. aber die Methode indexOf gibt auch int zurück.

Als nächstes verwende ich 2d-Array für mein Problem. Gibt es noch eine andere Möglichkeit, ein so großes Array zu speichern?

Answer 1

Verwenden Sie BitSet. Sie können dann ein beliebiges Indexelement Bit setzen. 600851475143 ist 2^39 und nimmt somit nur 39 Bits intern (tatsächlich wird es in Wirklichkeit 64 Bits belegen, da es lange verwendet).

Sie können infact bewegen bis 2^63, die für die meisten Zwecke

Answer 2

I hatte ein ähnliches Problem ist massiv und i verwenden Satz ein Bit (im Allgemeinen 1 oder 0 für eingestellt den Versatz um gewünscht) und i recomend Verwendung es EWAHCompressedBitmap wird auch Ihre Bit

EDIT

gesetzt komprimieren Als Alan die BitSet sagte 70GB Speicherplatz belegen, aber Sie noch etwas anderes tun können: mehrere BitSets (aufeinanderfolgende haben, so dass Sie die absolute Position berechnen kann,) und laden Sie im Speicher nur das BitSet, das Sie in diesem Moment so etwas wie eine Lazy Load benötigen, in diesem Fall haben Sie die Kontrolle über den verwendeten Speicher.

Answer 3

Die Speicheranforderung für 600801475143 booleans ist bestenfalls 70 GB. Dies ist nicht möglich. Sie müssen entweder die von Stephan vorgeschlagene Komprimierung verwenden oder einen anderen Algorithmus zum Berechnen der Primzahlen verwenden.

Answer 4

Es ist nicht wirklich praktisch, sich für jede Zahl zu merken, wenn es für eine so große Menge eine Primzahl war oder nicht (das Sieb ist ein sehr langsamer Ansatz für große Zahlen im Allgemeinen).

Von dieser link erhalten Sie eine Idee, wie viele Primzahlen kleiner als X erwartet werden. Für Ihre 600 Milliarden Reichweite können Sie erwarten, dass etwa 20 Milliarden Primzahlen in diesem Bereich existieren. Speichern sie so lange [] würde etwa 160 GB Speicher erfordern ... dass deutlich mehr als die vorgeschlagenen 70 GB für die Speicherung eines einzelnen Bits für jede Nummer, die Hälfte, wenn Sie gerade Zahlen ausschließen (2 ist die einzige gerade Primzahl).

Für einen Desktop-Computer 35 GB im Speicher möglicherweise ein bisschen viel, aber eine gute Arbeitsstation kann so viel RAM haben. Ich würde ein zweidimensionales Array mit Bitverschiebung/Maskierung versuchen.

Ich würde immer noch erwarten, dass Ihr Sieb-Code eine erhebliche Menge an Zeit (etwas von Tagen bis Jahren) laufen. Ich schlage vor, Sie untersuchen fortgeschrittenere Prime-Nachweismethoden als Sieb.

Answer 5

Sie können die interne sun.misc.Unsafe-API von HotSpot verwenden, um ein größeres Array zuzuweisen. I wrote a blogpost how to simulate an array with it Es handelt sich jedoch nicht um eine offizielle Java API, daher handelt es sich um einen Hack.