javaでArrayListインデックスとしてlongを使用する

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

  •  19-08-2019
  •  | 
  •  

質問

エラトステネスのふるいを使用して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);
        }
    }
}
役に立ちましたか？

解決

コードが最初からコンパイルされる理由がわかりません。

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

さらに、intはJavaでは32ビットです。長さが2 ^ 32を超える配列（長いインデックスが必要になる）が存在する可能性は低く、仕様で許可されているかどうかさえわかりません。

他のヒント

long []への32ビットの符号付きintインデックスを使用して、16GBのRAMをアドレス指定していることを認識してください。

ふるいで大きなプライムに到達することに真剣に取り組んでいる場合、現在の実装でいくつかのことを逃すことはありません：

  • ボックス化されたlongのArrayList
  • Uriの言及のように[]を使用する
  • 体系的にディスクにページングしない

Java仕様は配列を最大でInteger.MAX_VALUE要素。 Listにはその他の要素が含まれる場合があります（Collection s 一般的に）、 intインデックスを使用して追加/取得/削除/設定します。

多くの要素のメモリがあると仮定すると（非常に考えにくい）、<！> quot; concatenated <！> quot;で構成される独自のデータ構造を記述できます。配列。 get()およびset()メソッドはlongインデックスを取得し、対応する配列とその配列内のArrayListインデックスを見つけます。

また、各番号を明示的に保存/削除するのではなく、ブール値を使用して各番号の状態を表すことをお勧めします。これは、（1）ブール値がlongよりも少ないスペースを使用し、（2）要素の削除中に要素を移動する（<=>で行われるように）コストがかかる可能性があるためです。

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

だから、もしあなたのアルゴリズムが本当にそのような大きな配列を持つことに依存しているなら、Java配列では運が悪い。

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

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

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

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

編集： Zach Scrivenaは、Float64Vectorがintにディメンション化されているというコメントで指摘しました。私は訂正しました。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top