1

Java では、配列 ( ) よりもサイズが大きい BitSet があり100000 > 2000ます。配列には、範囲 の正の整数が含まれています[1; 100000]。指定された配列とビットセットを交差させたい。明らかに、交差点は配列のサイズよりも小さいサイズになるので、配列として保存したいと思います。以下の私のコード：

BitSet b = new BitSet(100000);
int[] a = new int[2000];
// fill in b with some bits and a with positive integers in range from [1; 100000]

// intersect array a and bitset b and keep result in separate array
int[] intersection = new int[a.length];
int c = 0, i = 0, j = b.nextSetBit(0);
while (i < a.length && j >= 0) {
    if (a[i] < j) i++;
    else if (a[i] > j) j = b.nextSetBit(j+1);
    else {
        intersection[c] = j;
        i++; j = b.nextSetBit(j+1); c++;
    }
}

// usually intersection is less than a array in size so cut it
int[] zip = new int[c];
System.arraycopy(intersection, 0, zip, 0, c);

上記のものよりもタイムコードを速くすることは可能ですか?

EDIT配列aは、たとえば、ソートされますa = { 2, 115, 116, 2034, 26748 }。

4

1 に答える 1

3

bこれは間違いなく簡単で、インデックスが にある要素にのみアクセスするため、より高速であると思いますa。b次の設定ビットを探すためにすべてをスキャンするわけではありません。

  public static int[] intersect(BitSet b, int[] a){
    int[] rawResult = new int[a.length];
    int c = 0;
    for(int i : a){
      if(b.get(i)){
        rawResult[c] = i;
        c++;
      }
    }
    int[] result = new int[c];
    System.arraycopy(rawResult, 0, result, 0, c);
    return result;
  }
于 2013-05-08T06:56:42.740 に答える