写"压缩"数组以提高IO性能？

Question

我有一个int和float数组,每个长度为2.2亿(固定).现在,我想将这些数组存储/上传到内存和磁盘.目前,我正在使用Java NIO的FileChannel和MappedByteBuffer来解决这个问题.它工作正常,但是将数组存储/上传到内存到磁盘需要大约5秒钟(挂钟时间).现在,我想让它更快.

在这里,我应该提到大多数数组元素都是0(接近52%).

喜欢:

int arr1 [] = { 0 , 0 , 6 , 7 , 1, 0 , 0 ...}

任何人都可以帮助我,有没有很好的方法来提高速度,不存储或加载那些0.这可以通过使用Arrays.fill(array,0)来补偿.

Answer 1

以下方法需要磁盘上的n/8 + nz*4字节,其中n是数组的大小,nz是非零条目的数量.对于52%的零条目,您将存储大小减少52% - 3%= 49%.

你可以这样做:

void write(int[] array) {
    BitSet zeroes = new BitSet();
    for (int i = 0; i < array.length; i++)
        zeroes.set(i, array[i] == 0);
    write(zeroes); // one bit per index
    for (int i = 0; i < array.length; i++)
        if (array[i] != 0)
            write(array[y]);
}

int[] read() {
    BitSet zeroes = readBitSet();
    array = new int[zeroes.length];
    for (int i = 0; i < zeroes.length; i++) {
        if (zeroes.get(i)) {
            // nothing to do (array[i] was initialized to 0)
        } else {
            array[i] = readInt();
        }
    }
}

编辑:你说这稍微慢一点意味着磁盘不是瓶颈.您可以通过在构造bitset时编写bitset来调整上述方法,因此在将bitset写入磁盘之前不必将bitset写入内存.此外,通过在实际数据中逐字逐字地写入bitset,我们只能对数组进行一次传递,从而减少了缓存未命中:

void write(int[] array) {
    writeInt(array.length);
    int ni;
    for (int i = 0; i < array.length; i = ni) {
        ni = i + 32;
        int zeroesMap = 0;
        for (j = i + 31; j >= i; j--) {
            zeroesMap <<= 1;
            if (array[j] == 0) {
                zeroesMap |= 1;
            }
        }
        writeInt(zeroesMap);
        for (j = i; j < ni; j++)
            if (array[j] != 0) {
                writeInt(array[j]);
            }
        }
    }
}

int[] read() {
    int[] array = new int[readInt()];
    int ni;
    for (int i = 0; i < array.length; i = ni) {
        ni = i + 32;
        zeroesMap = readInt();
        for (j = i; j < ni; j++) {
            if (zeroesMap & 1 == 1) {
                // nothing to do (array[i] was initialized to 0)
            } else {
                array[j] = readInt();
            }
            zeroesMap >>= 1;
        }
    }
    return array;
}

(前面的代码假定array.length是32的倍数.如果不是,请以您喜欢的任何方式写入数组的最后一个切片)

如果这也没有减少处理时间,压缩就不是要走的路(我不认为任何通用压缩算法会比上面更快).