0

double の非常にまばらなベクトルを操作するには、効率的な Java 構造が必要です。つまり、基本的な読み取り/書き込み操作です。HashMap に実装しましたが、アクセスが遅すぎます。別のデータ構造を使用する必要がありますか? おすすめの無料ライブラリを教えてください。

平和的なアドバイスを探しています:)

どうもありがとう、

マリー

4

4 に答える 4

3

HashMap行く方法です。遅くてはいけません。プロファイラーでコードを実行して、常にどこに行くのかを確認し、それに応じて最適化します。コードを最適化するためのヒントが必要な場合は、ここに例を投稿して、特定の問題を解決できるようにしてください。

[編集] インデックスのサイズに応じて、Integer.valueOf(int)ボックス化のためにオブジェクトをキャッシュするなどの手法を使用できます。ただし、これは、多数のマップを作成し、インデックスがある程度制限された範囲にある場合にのみ機能します。

または、 commons-langIntHashMapから試すことができます。使い方は少し難しいですが (パッケージ プライベートです)、コードをコピーすることはできます。

最後に、ケースに最適化された値ルックアップを使用して、int ベースの HashMap の独自の実装を使用できます。

于 2009-12-10T12:59:16.417 に答える
1

データセットの大きさはどれくらいですか？Integer.MAX_VALUEよりはるかに大きいですか？問題は、HashSetが配列に支えられていることです。衝突するとパフォーマンスが低下します。おそらく、遅すぎるのはハッシュマップのメカニズムではなく、複数の衝突があるという事実です。おそらく、最初に（たとえば）別のハッシュ関数を使用してデータを分割し、次にデータの各パーティションを独自のハッシュマップに格納した場合、より幸運が得られます。

于 2009-12-10T13:33:53.703 に答える
0

私の Hapax プロジェクトからスパース ベクトルをコピーして貼り付けることができます: ch.akuhn.matrix.SparseVector

PS：マップの使用が遅すぎる理由を理解していない他のすべての回答とコメントに。マップはすべてのインデックスを Integer オブジェクトにボックス化するため、低速です!

ここに示すスパース ベクトルは、読み取りアクセスと値の追加では高速ですが、ランダムなインデックスへの配置では高速ではありません。これは、最初にスプラーズ ベクトルを作成するが、値をインデックスの昇順で配置し、後でほとんどの読み取りにマップを使用するシナリオに最適です。

スパース ベクトル クラスの重要なメソッドは次のとおりです。

// ...

public class SparseVector {

    /*default*/ int[] keys;
    /*default*/ int size, used;
    /*default*/ double[] values;

    public SparseVector(int size, int capacity) {
        assert size >= 0;
        assert capacity >= 0;
        this.size = size;
        this.keys = new int[capacity];
        this.values = new double[capacity];
    }

    public double get(int key) {
        if (key < 0 || key >= size) throw new IndexOutOfBoundsException(Integer.toString(key));
        int spot = Arrays.binarySearch(keys, 0, used, key);
        return spot < 0 ? 0 : values[spot];
    }

    public boolean isUsed(int key) {
        return 0 <= Arrays.binarySearch(keys, 0, used, key);
    }

    public double put(int key, double value) {
        if (key < 0 || key >= size) throw new IndexOutOfBoundsException(Integer.toString(key));
        int spot = Arrays.binarySearch(keys, 0, used, key);
        if (spot >= 0) return values[spot] = (float) value;
        else return update(-1 - spot, key, value);
    }

    public void resizeTo(int newSize) {
        if (newSize < this.size) throw new UnsupportedOperationException();
        this.size = newSize;
    }

    public int size() {
        return size;
    }

    private double update(int spot, int key, double value) {
        // grow if reaching end of capacity
        if (used == keys.length) {
            int capacity = (keys.length * 3) / 2 + 1;
            keys = Arrays.copyOf(keys, capacity);
            values = Arrays.copyOf(values, capacity);
        }
        // shift values if not appending
        if (spot < used) {
            System.arraycopy(keys, spot, keys, spot + 1, used - spot);
            System.arraycopy(values, spot, values, spot + 1, used - spot);
        }
        used++;
        keys[spot] = key;
        return values[spot] = (float) value;
    }

    public int used() {
        return used;
    }

    public void trim() {
        keys = Arrays.copyOf(keys, used);
        values = Arrays.copyOf(values, used);
    }

}
于 2009-12-10T13:11:49.423 に答える
0

1D スパース配列の場合、通常は map が適しています。ライブラリが多次元の場合にのみ使用する必要があります。

マップと配列のアクセス時間を比較すると、

   map.get(99);
   array[99];

マップはかなり遅くなります。どのライブラリにも同じ問題があります。

そのまばらな配列はすべてですか？時間をスペースと交換します。

于 2009-12-10T13:13:05.740 に答える