Mit einem langen als Arraylist-Index in Java

StackOverflow https://stackoverflow.com/questions/459643

  •  19-08-2019
  •  | 
  •  

Frage

Ich schreibe dieses Java-Programm, um alle Primzahlen bis zu num mit dem Sieb des Eratosthenes zu finden, aber wenn ich zu kompilieren versuchen, heißt es mich nicht lange var als Array-Index verwenden kann, und erwartet eine int var an seinem Platz. Aber ich werde mit großen Zahlen arbeiten, so kann ich nicht int verwenden. Was kann ich tun? 

import java.util.*;
import java.lang.*;

public class t3{
    public static void main(String[] args){
        long num = 100;

        //declaring list and filling it with numbers
        ArrayList<Long> numlist = new ArrayList<Long>();
        for(long x=2 ; x<num ; x++){
            numlist.add(new Long(x));
        }

        //sieve or eratosthenes
        for(long x=0 ; x<Math.sqrt(num) ; x++){
            for(long y=x+1 ; y<numlist.size() ; y++){
                if(numlist[y]%numlist[x] == 0){
                    numlist.remove(y);
                }
            }
        }

        //print list
        for(Object item : numlist){
            System.out.println((Long)item);
        }
    }
}
War es hilfreich?

Lösung

Ich bin mir nicht sicher, warum Sie den Code beginnen würde kompilieren.

Sie sind nicht [] in einer Array-Liste für den Zugriff Mitglieder verwenden soll. Eine Arraylist ist lediglich eine Liste, die intern in einem Array gespeichert ist. Sie haben die Liste get-Operation verwenden (was immer noch O (1) wäre). Schreiben numlist [index] bedeutet, dass Sie ein Array von Objekten in numlist haben. Sie können den [] Betrieb als in C ++ nicht außer Kraft setzen.

Darüber hinaus ist ein int 32 Bit in Java. ein Array mit einer Länge von mehr als 2 ^ 32 (so würden Sie lange Indizes müssen) ist unwahrscheinlich, und ich bin nicht einmal sicher, ob die Spezifikation erlaubt es.

Andere Tipps

Erkenne, dass mit einem 32-Bit signed int Index auf eine lange [] Sie Adressierung 16 GB RAM.

Wenn Sie wirklich ernsthaft über die mit dem Sieb zu großen Primzahlen immer, du gehst zu bekommen nicht weg mit ein paar Dinge in Ihrem aktuellen impl:

  • Arraylist von boxed longs
  • mit [] wie Uri erwähnt
  • Nicht systematisch auf die Festplatte Paging

Die Java-Spezifikation höchstens Arrays begrenzt Integer.MAX_VALUE Elemente. Während ein List enthält möglicherweise (dies gilt für Collections in allgemeine ), können Sie nur hinzufügen / get / entfernen / set sie einen int Index.

Angenommen, Sie den Speicher für so viele Elemente haben (sehr unwahrscheinlich, glaube ich), könnten Sie Ihre eigene Datenstruktur, bestehend aus „verketteten“ Arrays schreiben. Die get() und set() Verfahren würde einen long Index nehmen und innerhalb dieses Arrays den entsprechenden Array und int Index herauszufinden.

Auch würde ich vorschlagen, booleans mit dem Zustand jeder Zahl darzustellen, anstelle des Speicherns / jede Nummer explizit zu entfernen. Dies wäre besser, weil (1) booleans nimmt weniger Platz als Long-Positionen, und (2) Schaltelemente (wie in ArrayList getan) während Elemente Entfernung kann teuer werden.

Mindestens die theoretische maximale Größe von Java-Arrays ist Integer.MAX_VALUE. Dies liegt daran, dass der Typ des Array-Index ist nach dem spec einen int. In Wirklichkeit hängt es von Ihrem Gedächtnis though.

Also, wenn Ihr Algorithmus hängt wirklich davon ab, die eine so große Array, das Sie mit Java-Arrays aus Glück sind.

Wie ich bezweifle, dass Sie den ganzen Raum benötigen Sie Ihre eigene Sammlung Klasse schreiben könnte, die wie ein Array wirkt aber nicht so viel Speicher benötigen. Es würde die Löcher in dem Adressraum kollabiert (sozusagen). Natürlich könnte dies das Laufzeitverhalten Sie aus dem Algorithmus erwarten ändern.

Es gibt Vorschläge, über Projekt-Münze ( http://mail.openjdk.java.net/pipermail/coin-dev/2009-March/000869.html ), obwohl nichts angenommen oder geplant ist.

Die einfache Lösung: Die num Berücksichtigung ist nie größer als 100 in Ihrem Codeb., nur ändern, um int es geben.

Aber die Punkte andere über Adressraum erwähnt haben, sind auch gute Punkte.

die jScience Bibliothek verfügt über einen großen Vektor namens Float64Vector . Während ich nie diese Klasse verwendet haben, könnte es Ihre Bedürfnisse anzupassen. Keine Versprechungen.

EDIT: Zach Scrivena wies in den Kommentaren darauf hin, dass die Float64Vector zu Ints dimensioniert ist. Ich stehe korrigiert.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top