1

在 Java 中，我有一个比数组 ( 100000 > 2000) 更大的 BitSet。数组包含来自 range 的正整数[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 回答