3

興味深い課題があります。「ビン」にあるデータへのアクセスを制御する必要があります。数十万の「ビン」が存在する可能性があります。各ビンへのアクセスは個別に制御されますが、制限は重複する可能性があり、おそらく重複する可能性があります。各ビンにビットマスク内の位置 (1、2、3、4 など) を割り当てることを考えています。

次に、ユーザーがシステムにログインすると、ユーザーのセキュリティ属性を調べて、ユーザーが表示できるビンを決定します。その情報を使用して、このユーザーのビットマスクを作成します。「設定」ビットは、ユーザーが表示できるビンの識別子に対応します。したがって、ビン 1、3、4 が見える場合、ビット マスクは 1101 になります。

したがって、ユーザーがデータを検索すると、返された行のビン インデックスを見て、そのビットがビットマスクに設定されているかどうかを確認できます。彼のビットマスクにそのビットが設定されている場合、その行を表示させます。BigIntegerビットマスクをJavaに格納する予定です。

私の質問は次のとおりです。インデックス番号が Integer.MAX_INT よりも大きくならないと仮定すると、BigIntegerビットマスクは数十万のビット位置に合わせてスケーリングされますか? BigInteger.isBitSet(n)n が巨大になる可能性がある場合 (例: 874,837) 、実行するのに永遠にかかるでしょうか? そのようなものを作成するのに永遠にかかるでしょうBigIntegerか?

2 つ目: 別のアプローチがある場合は、ぜひお聞かせください。

4

4 に答える 4

4

頻繁に変更しない限り、BigInteger は高速であるはずです。

より明白な選択肢は、この種のもののために設計されたBitSetです。ビットを検索する場合、パフォーマンスは似ていると思います。作成/変更には、BitSet を使用する方が効率的です。

注: PaulG は、その違いは「印象的」であり、BitSet の方が高速であるとコメントしています。

于 2012-09-19T15:57:20.443 に答える
2

Java には、このためのより便利な というクラスがありBitSetます。

ループでビットが設定されているかどうかを確認する必要はありません。マスクを作成し、 bitwise を使用しand、結果が空でないかどうかを確認して、アクセスを許可するか拒否するかを決定できます。

BitSet resourceAccessMask = ...
BitSet userAllowedAccessMask = ...
BitSet test = (BitSet)resourceAccessMask.clone();
test.and(userAllowedAccessMask);
if (!test.isEmpty()) {
    System.out.println("access granted");
} else {
    System.out.println("access denied");
}

以前の会社でも同様の状況でこのクラスを使用しましたが、パフォーマンスは目的にかなうものでした。

于 2012-09-19T15:58:02.850 に答える
1

このために独自のJavaインターフェースを定義することができます。最初は、Javaを使用してBitSetそのインターフェースを実装します。

パフォーマンスの問題が発生した場合、または後で使用する必要がある場合は、残りのコードを変更せずに、常に別の実装（たとえば、キャッシュまたは同様の改善を使用する実装）を提供できます。必要なインターフェースについてよく考え、long念のためにインデックスを選択してください。後で実装で範囲外かどうかをいつでも確認できます（または最初に「アクセスなし」を返すだけです）index > Integer.MAX_VALUE。

BigIntegerクラスはその特定の目的のために作成されていないため、使用することはあまり良い考えではありません。クラスを変更する唯一の方法は、完全に新しいコピーを作成することです。メモリの使用に関しては効率的です。内部で64ビット長の配列を使用します（現時点では、もちろん変更される可能性があります）。

于 2012-09-19T16:14:40.187 に答える
0

(BitSet を使用する以外に) 検討する価値があることの 1 つは、異なる粒度を使用することです。したがって、各ビットが複数の実際のビットを「保護」する短いビット セットを使用します。この方法では、ユーザーごとに数百万ビットの RAM を用意する必要はありません。

これを実現する簡単な方法は、n/32 のように小さなビットを設定して、次のようにすることです。

boolean isSet(int n) {
    return guardingBits.isSet(n / 32) && realBits.isSet(n);
}

これにより、実際のビットがほとんどゼロである場合に、実際のビットのロードを回避できる可能性が高くなります。このアプローチを変更して、予想されるビット セットに一致させることができます。ほぼすべてのビットが設定されていると予想される場合は、保護するすべてのビットが設定されている場合、この保護ビットを使用して 1 を格納できます。したがって、ゼロの可能性があるビットをチェックするだけで済みます。

また、これは始まりでさえあるかもしれません。使用法と要件によっては、ビッグ ビット フィールドの一部のみをメモリに保持する B ツリーまたはページ分割されたバージョンを使用することをお勧めします。

于 2013-12-09T22:26:23.153 に答える