java - 写 "compressed"数组提高IO性能？

Question

我有一个长度为 2.2 亿(固定)的 int 和 float 数组。现在，我想将这些数组存储/上传到/从内存和磁盘。目前，我正在使用 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 并穿插实际数据，我们可以只对数组进行一次传递，从而减少缓存未命中:

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 的倍数。如果不是，则按照您喜欢的方式写入数组的最后一个切片)

如果这也不能减少处理时间，则压缩不是可行的方法(我认为任何通用压缩算法都不会比上述算法更快)。