在 Java 中存储大量数字

Question

我正在尝试存储一组范围从 0 到 ~600 亿的数字，其中该组从空开始并逐渐变得更密集，直到它包含该范围内的每个数字。该集合不必能够删除数字。目前我的方法是将该集合表示为一个非常长的布尔数组并将该数组存储在一个文本文件中。我为此做了一个 class，并测试了 RandomAccessFile 和 FileChannel，数字范围限制在 0 到 20 亿之间，但在这两种情况下，class 在添加和查询数字时要慢得多比使用常规布尔数组。这是我的 class:

的当前状态

import java.io.*;
import java.nio.ByteBuffer;
import java.nio.channels.*;
import java.util.*;
public class FileSet {
    private static final int BLOCK=10_000_000;
    private final long U;
    private final String fname;
    private final FileChannel file;
    public FileSet(long u, String fn) throws IOException {
        U=u;
        fname=fn;
        BufferedOutputStream out=new BufferedOutputStream(new FileOutputStream(fname));
        long n=u/8+1;
        for (long rep=0; rep<n/BLOCK; rep++) out.write(new byte[BLOCK]);
        out.write(new byte[(int)(n%BLOCK)]);
        out.close();
        file=new RandomAccessFile(fn,"rw").getChannel();
    }
    public void add(long v) throws IOException {
        if (v<0||v>=U) throw new RuntimeException(v+" out of range [0,"+U+")");
        file.position(v/8);
        ByteBuffer b=ByteBuffer.allocate(1); file.read(b);
        file.position(v/8);
        file.write(ByteBuffer.wrap(new byte[] {(byte)(b.get(0)|(1<<(v%8)))}));
    }
    public boolean has(long v) throws IOException {
        if (v<0||v>=U) return false;
        file.position(v/8);
        ByteBuffer b=ByteBuffer.allocate(1); file.read(b);
        return ((b.get(0)>>(v%8))&1)!=0;
    }
    public static void main(String[] args) throws IOException {
        long U=2000_000_000;
        SplittableRandom rnd=new SplittableRandom(1);
        List<long[]> actions=new ArrayList<>();
        for (int i=0; i<1000000; i++) actions.add(new long[] {rnd.nextInt(2),rnd.nextLong(U)});

        StringBuilder ret=new StringBuilder(); {
            System.out.println("boolean[]:");
            long st=System.currentTimeMillis();
            boolean[] b=new boolean[(int)U];
            System.out.println("init time="+(System.currentTimeMillis()-st));
            st=System.currentTimeMillis();
            for (long[] act:actions)
                if (act[0]==0) b[(int)act[1]]=true;
                else ret.append(b[(int)act[1]]?"1":"0");
            System.out.println("query time="+(System.currentTimeMillis()-st));
        }

        StringBuilder ret2=new StringBuilder(); {
            System.out.println("FileSet:");
            long st=System.currentTimeMillis();
            FileSet fs=new FileSet(U,"FileSet/"+U+"div8.txt");
            System.out.println("init time="+(System.currentTimeMillis()-st));
            st=System.currentTimeMillis();
            for (long[] act:actions) {
                if (act[0]==0) fs.add(act[1]);
                else ret2.append(fs.has(act[1])?"1":"0");
            }
            System.out.println("query time="+(System.currentTimeMillis()-st));
            fs.file.close();
        }
        if (!ret.toString().equals(ret2.toString())) System.out.println("MISMATCH");
    }
}

和输出：

boolean[]:
init time=1248
query time=148
FileSet:
init time=269
query time=3014

此外，当范围从 20 亿增加到 100 亿时，查询的总运行时间会有很大的跳跃，尽管理论上总运行时间应该大致保持不变持续的。当我单独使用 class 时（因为布尔数组不再适用于这么大的范围），查询时间从 ~3 秒变为 ~50 秒。当我将范围增加到 600 亿时，时间增加到约 240 秒。我的问题是：是否有更快的方法来访问和修改任意索引处的超大文件？是否有一种完全不同的方法来存储比我当前方法更快的大整数集？

Answer 1

Boolean 数组是一种非常低效的信息存储方式，因为每个布尔值占用 8 位。您应该改用 BitSet。但是 BitSets 也有 20 亿的限制，因为它使用原始 int 值作为参数（并且 Integer.MAX_VALUE 限制了内部 long 数组的大小）。

一个 space 跨越 20 亿个条目的高效内存替代方案是创建您自己的 BitSet 包装器，将数据拆分为子集并为您建立索引：

public class LongBitSet {
    // TODO: Initialize array and add error checking.
    private final BitSet bitSets = new BitSet[64];
    public void set(long index) {
        bitSets[(int) (index / Integer.MAX_VALUE)]
            .set((int) (index % Integer.MAX_VALUE));
    }
}

但还有其他选择。如果你有一个非常密集的数据，使用运行长度编码将是增加内存容量的一种廉价方法。但这可能会涉及 B 树结构，以提高访问效率。这些只是指针。做出正确答案的很多因素完全取决于您实际使用数据结构的方式。

Answer 2

事实证明，最简单的解决方案是使用 64 位 JVM 并在终端中使用标志增加 Java 堆 space 运行我的 Java 程序喜欢 -Xmx10g。然后我可以简单地使用一个 longs 的数组来隐式存储整个集合。

在 Java 中存储大量数字

Storing a very large set of numbers in Java

java

io

nio

set