11

エラトステネスのふるいを使用して num までのすべての素数を見つけるためにこの Java プログラムを作成していますが、コンパイルしようとすると、長い var を配列インデックスとして使用できないと表示され、int var が必要ですその場所。しかし、私は大きな数で作業するので、int は使用できません。私に何ができる?

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

7 に答える 7

15

そもそもあなたのコードがコンパイルされる理由がわかりません。

メンバーにアクセスするために配列リストで [] を使用することは想定されていません。arraylist は、配列に内部的に格納される単なるリストです。リスト取得操作を使用する必要があります (これはまだ O(1) です)。numlist[index] と書くことは、numlist にオブジェクトの配列があることを意味します。C++ のように [] 操作をオーバーライドすることはできません。

また、Java では int は 32 ビットです。2^32 より大きい長さの配列を持つことは (長いインデックスが必要になるため) ありそうになく、仕様で許可されているかどうかさえわかりません。

于 2009-01-19T23:46:35.213 に答える
13

long[] への 32 ビットの signed int インデックスを使用すると、16 GB の RAM をアドレス指定していることに注意してください。

ふるいを使って大きな素数を取得することに真剣に取り組んでいる場合は、現在の実装でいくつかのことを回避することはできません。

  • ボックス化された long の ArrayList
  • [] を Uri メンションのように使用する
  • 体系的にディスクにページングしない
于 2009-01-19T23:51:57.107 に答える
10

Java 仕様では、配列を最大で Integer.MAX_VALUE 要素に制限しています。aにはより多くの要素Listが含まれる場合がありますが (これは一般にsに当てはまります)、インデックスを使用して追加/取得/削除/設定することしかできません。Collectionint

その多くの要素のメモリがあると仮定すると (私はそうは思いません)、「連結された」配列で構成される独自のデータ構造を作成できます。get()andset()メソッドはインデックスを取得longし、対応する配列とintその配列内のインデックスを見つけます。

また、各数値を明示的に保存/削除するのではなく、ブール値を使用して各数値の状態を表すことをお勧めします。これは、(1) boolean は long よりもスペースをとらず、(2)ArrayList要素の削除中に ( で行われたように) 要素をシフトするとコストがかかる可能性があるため、より優れています。

于 2009-01-20T07:09:10.313 に答える
4

少なくとも Java 配列の理論上の最大サイズは Integer.MAX_VALUE です。これは、配列インデックスの型が仕様に従ってint であるためです。実際には、あなたの記憶に依存します。

したがって、アルゴリズムがそのような大きな配列を持つことに本当に依存している場合は、Java 配列ではうまくいきません。

配列のように機能する独自のコレクション クラスを作成できるすべてのスペースが必要になるとは思えませんが、それほど多くのメモリは必要ありません。アドレス空間の全体を崩壊させます(いわば)。もちろん、これにより、アルゴリズムから期待される実行時の動作が変わる可能性があります。

于 2009-01-19T23:59:55.203 に答える
4

Project Coin ( http://mail.openjdk.java.net/pipermail/coin-dev/2009-March/000869.html )を介して long-indexed 配列を Java に追加する提案がありましたが、何も受け入れられず、予定もされていません。

于 2011-04-15T13:52:43.453 に答える
2

簡単な解決策:numコード サンプルで が 100 を超えることはないことを考慮して、型を に変更するだけintです。

しかし、他の人がアドレス空間について言及した点も良い点です。

于 2009-01-20T00:11:34.773 に答える
0

jScience ライブラリにはFloat64Vectorという大きなベクターがあります。このクラスを使用したことはありませんが、ニーズに合うかもしれません。約束はできません。

編集: Zach Scrivena は、コメントで Float64Vector が int に寸法付けられていることを指摘しました。私は訂正します。

于 2009-01-20T01:16:11.650 に答える