9

我目前正在编写一段代码，其中我已经确定我的两位数组的串联是瓶颈，并且正在讨论如何提高效率。

我的位数组建模如下

public BitArray(int size) { 
    int sizeBytes = size / 8 ;
    if (size % 8 !=0) sizeBytes++;
    this.array = new byte[sizeBytes];
    this.size = size ; 
}

其中 size 是以位为单位的大小。

有效连接两个位数组时的挑战是在连接一个大小为 7 的位数组与一个大小为 6 的位数组时需要发生的跨越。因此，不可能简单地做两个数组副本。

除了我目前已经实现的解决方案之外，我正在研究的解决方案如下：计算“跨区域”（例如，5 位数组的最后 3 位）。使用 system.array.copy 复制第一个数组，使用我的 setBit 函数从第二个数组手动设置 3 个“跨越位”。将第二个数组向左移动 3System.arraycopy()

目前，我手动设置了第二个数组的每个单独的位，如下所示。

问题在于，对于位移，该操作实际上非常昂贵，因为它必须为每个字节完成，然后必须再次发生跨越。

关于如何改进上述技术的想法？

这是当前表现不佳的代码：

public static BitArray concatenate(BitArray x1_, BitArray x2_) {
    if (x1_ == null) {
        System.out.println("x1 is null");
        int b = x2_.getArray().length;
        byte[] array = new byte[b];
        System.arraycopy(x2_.getArray(), 0, array, 0, b);
        BitArray res = new BitArray(array);
        res.setSize(x2_.getSize());
        return res;
    } else if (x2_ == null) { 
        System.out.println("x2 is null");
        int b = x1_.getArray().length;
        byte[] array = new byte[b];
        System.arraycopy(x1_.getArray(), 0, array, 0, b);
        BitArray res = new BitArray(array);
        res.setSize(x1_.getSize());
        return res;
    }

    int size1 = x1_.getSize();
    int size2 = x2_.getSize();
    int size = (x1_.getSize() + x2_.getSize()) / 8 ;
    if ((size1 + size2)%8!=0) size++;
    byte[] result = new byte[size];
    System.arraycopy(x1, 0, result, 0, x1.length);
    BitArray res = new BitArray(result);
    res.setSize(size1 + size2);
    for (int i = 0 ; i<size2 ; i++) {
        res.setBit(size1 + i, x2_.getBit(i) );
    }
    return res; 
}
4

2 回答 2

1

您的代码非常复杂且难以阅读。但是，有些事情可能需要时间：

  • 使用%运算符
  • getSize()在方法中多次调用- 为什么不使用size位数组的属性？

我认为使用字节/长的链表来表示你的BitArray连接会更快，因为你可以避免复制任何东西，只需更新一个指针。

concatenate您将在阵列上执行大量操作吗？如果是这样，我想我会使用 long 的链表来表示位数组。你的位阵列有多大？

于 2013-10-03T09:29:07.930 回答
0

我认为您可以在不复制数据的情况下生成一个新数组。像这样的东西：

class MyBitArray extends BitArray{

    private BitArray a;
    private BitArray b;

    public MyBitArray(BitArray a, BitArray b) throws IllegalArgumentException {
        super(0);
        this.a = a == null ? new BitArray(0) : a;
        this.b = b == null ? new BitArray(0) : b;
    }

    public boolean get(int i){
        if(i < a.length()){
            return a.get(i);
        }
        return b.get(i - a.length());
    }

    public int length(){
        return a.length() + b.length();
    }
}
于 2013-10-03T10:17:33.703 回答