java - 在 Java 中序列化 Longs 数组的最紧凑方法

Question

我有很多长数组 long[] 我需要将它们序列化并将它们保存到磁盘以供以后读取，注意每个数组都必须不时修改，但是写入是不频繁而读取频繁。 通常我的应用程序只需要同时加载到内存中的一小部分。 在将阵列存储回磁盘之前，可以在内存中批量编辑每个阵列。 每个数组都有数百到一百万个元素。 在我的应用程序中，将所需数组加载到内存中的速度非常快非常重要。

在我的例子中，每个数组中的 long 值平均而言彼此非常接近，即一个值与下一个值之间的差异 - 如果在单个数组中排序 - 小于整数。

采用类trie结构的解决方案as presented here似乎不适用于我的情况，因为在该解决方案中，数组值是已知的并且永远不会改变。

This solution here告诉我使用 ByteBuffer 和 LongBuffer 来加速 I/O，但我的想法是也以最紧凑的方式存储这样的数组以加速通过减少我需要阅读的内容的大小，将它们加载到主内存中所需的时间。 直觉是存储排序后的值并存储一个值与下一个值之间的差值，平均而言，该差值在整数范围内，因此占用的空间更少。 但由于这并不总是正确的，我仍然无法将所有值都存储为整数，因此这个方向似乎不太乐观。 我是否遗漏了一些明显的东西？

在 I/O 时间内，实现此目标的最有效方法是什么？

---

编辑 通常，将性能视为单独的 I/O 时间，而不考虑磁盘空间，this question有更好的答案。

Answer 1

您仍然可以通过以下添加将数组元素编码为整数:

    // The first int is the array length
    buf.putInt(array.length);

    long prev = 0;
    for (long next : array) {
        if (next - prev <= Integer.MAX_VALUE) {
            // Delta is small. Change the sign and encode as int.
            buf.putInt((int) (prev - next));
        } else {
            // Delta does not fit in 31 bits. Encode two parts of long.
            buf.putInt((int) (next >>> 32));
            buf.putInt((int) next);
        }
        prev = next;
    }

请注意，31 位增量将被编码为负 int。在解码期间，最高(符号)位将判断该值是增量值还是原始 63 位 long。在后一种情况下，您读取下一个 int 并从两个 int 组成一个 63 位 long:

    // The first int is the array length
    long[] array = new long[buf.getInt()];

    long next = 0;
    for (int i = 0; i < array.length; i++) {
        int delta = buf.getInt();
        if (delta <= 0) {
            // Negative sign means the value is encoded as int delta.
            next -= delta;
        } else {
            // Positive sign means the value is encoded as raw long.
            // Read the second (lower) part of long and combine it with the higher part.
            next = (long) delta << 32 | (buf.getInt() & 0xffffffffL);
        }
        array[i] = next;
    }

如果数组中的所有值都是正数，则此方法有效。如果既有正值也有负值，将它们拆分成两个数组。

---

顺便说一句，如果相邻值接近，像 GZIP(或像 LZ4 这样更快的替代方案)这样的流式压缩也能很好地工作。参见 GZIPOutputStream .