Bit Arrays Java的高效串联

Question

我目前正在编写一段代码,我已经确定我的两位数组的串联是瓶颈,并就如何提高它的效率进行辩论.

我的Bit数组建模如下

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位).使用systemBit函数从system.array.copy手动设置第二个数组中的3个"跨越位"复制第一个数组.将第二个数组向左移动3做一个System.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; 
}

Answer 1

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

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

我认为使用字节/长整数的链接列表来表示您的BitArray连接速度会快得多，因为您可以避免复制任何内容，只需更新指针即可。

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