3

HidingList元の各要素のビューを実装するクラスが必要Listです。ビューに含める必要があるかどうかは少しわかります。簡単な解決策は a を使用することですが、リストが大きくなった場合BitSetに実装する簡単で効率的な方法はわかりません。hidingList.get(int index)何かのようなもの

public T get(int index) {
    int realIndex = bitSet.nextSetBit(0);
    for (int i=0; i<index; ++i) {
        realIndex = bitSet.nextSetBit(realIndex+1);
    }
    return delegate.get(realIndex);
}

はあまり効率的ではないようで、 のようなメソッドが見当たりませんbitSet.cardinality(int from, int to)。たぶん、グアバかどこかに必要なものがすでにあるのでしょうか？

4

3 に答える 3

0

さまざまな構造の効率は、アクセスパターンに大きく依存します。たとえば、可視性が変更された回数と比較して、非表示リストのインデックス付き読み取りの頻度はどれくらいですか？

平均して（可視性の変更が比較的まれであるか、バッチ処理できると仮定して）-私の提案は、非表示の要素が削除された元のリストのコピーである新しいリストを作成することです。理由：

  • 全体をO（n）時間で構築できます。これは、アイテムごとにO（1）だけです。
  • 新しいリストは直接インデックスアクセスをサポートするため、O（1）アクセスを維持できます。ビットセットのスキャンはO（n）であり、大きなリストでのインデックス付きアクセスには恐ろしいものになります。
  • あなたはそれを不変にすることができます。不変のものは良いです。

それ以外の場合、各リストアイテムの表示を任意の時間にオンまたはオフに切り替えられるようにするには、カスタムデータ構造を実装する必要があります。二分木を使用すると、非表示、再表示、およびインデックス付きルックアップのO（log n）パフォーマンスを得ることができます。しかし、私はこれに対する既存の実装を知りません-それは少し珍しい要件です！

于 2012-09-20T14:25:03.997 に答える
0

二分探索を使用してInteger.bitCount、ビット数で少なくとも対数時間の複雑さを達成することができます (ソリューションが O(n) の場合)。まず、全ビットの半分を 0 にします。1 の数を取得するために使用Integer.bitCountします (この操作は通常、マシン命令にマップされるため、非常に高速です)。取得した数値がインデックスよりも大きい場合は、半分のバイトのみを 0 に、小さい場合はさらに null を除外します (通常のバイナリ検索)。これにより、対数のステップ数で位置を見つけることができます。

たとえば、2 バイトの数値でインデックス 4 (つまり、5 番目の要素) を探しています。0010 1010 1110 1001

最初のステップ: 0010 1010 1110 1001b = 8 > 5、全バイトの半分を null にする

2 番目のステップ: 0010 1010 0000 0000b = 3 < 5、4 バイトのみを null にする

3 番目のステップ: 0010 1010 1110 0000b = 6 > 5、さらに 2 バイトを null にする

4 番目のステップ: 0010 1010 1100 0000b = 5 == 5 なので、答えは残りの 2 バイトになければなりません。もう1つヌルアウト→b=4→検索位置は10バイト目である必要があります。

それでも、インデックス リストを維持する方が高速ですが、より多くのメモリが必要になります。組み込み設定でない限り、メモリはそれほど大きな問題ではないため、このソリューションを使用する必要があります。

于 2012-09-20T13:45:13.337 に答える
0

効率的 (つまり、平均で O(N) よりも優れている) にしたいget(int)場合は、ビットマップを整数の配列に置き換えることができます。ここで、インデックスはビュー リストへのインデックスを表し、インデックスの値はのインデックスを表します。元のリストの要素。

ただし、元のリスト (またはそのようなもの) に書き込みたい場合を除きset(int, T)、ビューではなく新しいリストを作成する方がよいでしょう。

于 2012-09-20T13:36:19.060 に答える