你试过转换成十六进制吗?

我可以看到前后文件大小都有了很大的减小;然后，用自由空间分步计算。也许，再次转换为dec, order，十六进制，另一个块，转换为dec, order…

对不起. .我不知道是否可行

# for i in {1..10000};do echo $(od -N1 -An -i /dev/urandom) ; done > 10000numbers
# for i in $(cat 10000numbers ); do printf '%x\n' $i; done > 10000numbers_hex
# ls -lah total 100K
drwxr-xr-x  2 diego diego 4,0K oct 22 22:32 .
drwx------ 39 diego diego  12K oct 22 22:31 ..
-rw-r--r--  1 diego diego  29K oct 22 22:33 10000numbers_hex
-rw-r--r--  1 diego diego  35K oct 22 22:31 10000numbers

我们有1 MB - 3 KB RAM = 2^23 - 3*2^13位= 8388608 - 24576 = 8364032位可用。

我们给出10^8范围内的10^6个数。这给出了~100 < 2^7 = 128的平均差距

让我们首先考虑一个比较简单的问题，即当所有间距都< 128时，数字间距相当均匀。这很简单。只存储第一个数字和7位空白:

(27位)+ 10^6个7位间隔数=需要7000027位

注意重复的数字间隔为0。

但如果间隔大于127呢?

好吧，让我们直接表示小于127的间隙大小，但是127的间隙大小后面跟着一个连续的8位编码来表示实际的间隙长度:

 10xxxxxx xxxxxxxx                       = 127 .. 16,383
 110xxxxx xxxxxxxx xxxxxxxx              = 16384 .. 2,097,151

etc.

注意这个数字表示描述了它自己的长度，所以我们知道下一个间隙数何时开始。

对于小于127的小间隙，仍然需要7000027位。

可能有高达(10^8)/(2^7)= 781250个23位的间隙数，需要额外的16* 781250 = 12500,000位，这是太多了。我们需要一个更紧凑和缓慢增加的差距表示。

平均差距大小是100，所以如果我们把它们重新排序 [100, 99, 101, 98, 102，…]， 2, 198, 1, 199, 0, 200, 201, 202，…] 然后用密集的二进制斐波那契基编码索引它，没有对零(例如，11011=8+5+2+1=16)，数字用“00”分隔，然后我认为我们可以保持足够短的差距表示，但它需要更多的分析。

If the numbers are evenly distributed we can use Counting sort. We should keep the number of times that each number is repeated in an array. Available space is: 1 MB - 3 KB = 1045504 B or 8364032 bits Number of bits per number= 8364032/1000000 = 8 Therefore, we can store the number of times each number is repeated to the maximum of 2^8-1=255. Using this approach we have an extra 364032 bits unused that can be used to handle cases where a number is repeated more than 255 times. For example we can say a number 255 indicates a repetition greater than or equal to 255. In this case we should store a sequence of numbers+repetitions. We can handle 7745 special cases as shown bellow:

364032/(表示每个数字所需的位数+表示100万所需的位数)= 364032 / (27+20)=7745

我认为解决方案是结合视频编码的技术，即离散余弦变换。在数字视频中，不是将视频的亮度或颜色的变化记录为常规值，如110 112 115 116，而是从最后一个中减去每一个(类似于运行长度编码)。110 112 115 116变成110 2 3 1。这些值，2,3 1比原始值需要更少的比特。

So lets say we create a list of the input values as they arrive on the socket. We are storing in each element, not the value, but the offset of the one before it. We sort as we go, so the offsets are only going to be positive. But the offset could be 8 decimal digits wide which this fits in 3 bytes. Each element can't be 3 bytes, so we need to pack these. We could use the top bit of each byte as a "continue bit", indicating that the next byte is part of the number and the lower 7 bits of each byte need to be combined. zero is valid for duplicates.

当列表填满时，数字之间的距离应该越来越近，这意味着平均只有1个字节用于确定到下一个值的距离。7位值和1位偏移(如果方便的话)，但可能存在一个“继续”值需要少于8位的最佳点。

总之，我做了一些实验。我使用随机数生成器，我可以将100万个排序过的8位十进制数字放入大约1279000字节。每个数字之间的平均间隔始终是99…

public class Test {
    public static void main(String[] args) throws IOException {
        // 1 million values
        int[] values = new int[1000000];

        // create random values up to 8 digits lrong
        Random random = new Random();
        for (int x=0;x<values.length;x++) {
            values[x] = random.nextInt(100000000);
        }
        Arrays.sort(values);

        ByteArrayOutputStream baos = new ByteArrayOutputStream();

        int av = 0;    
        writeCompact(baos, values[0]);     // first value
        for (int x=1;x<values.length;x++) {
            int v = values[x] - values[x-1];  // difference
            av += v;
            System.out.println(values[x] + " diff " + v);
            writeCompact(baos, v);
        }

        System.out.println("Average offset " + (av/values.length));
        System.out.println("Fits in " + baos.toByteArray().length);
    }

    public static void writeCompact(OutputStream os, long value) throws IOException {
        do {
            int b = (int) value & 0x7f;
            value = (value & 0x7fffffffffffffffl) >> 7;
            os.write(value == 0 ? b : (b | 0x80));
        } while (value != 0);
    }
}

你用的是哪种电脑?它可能没有任何其他“正常”的本地存储，但它是否有视频RAM，例如?100万像素x每像素32位(比如说)非常接近你所需的数据输入大小。

(我主要是问旧的Acorn RISC PC的内存，如果你选择低分辨率或低颜色深度的屏幕模式，它可以“借用”VRAM来扩展可用的系统RAM !)这在只有几MB普通RAM的机器上非常有用。

你最多要数到99,999,999，并在沿途标明1,000,000个站点。因此，可以使用位流进行解释，即1表示递增计数器，0表示输出数字。如果流中的前8位是00110010，到目前为止我们将有0,0,2,2,3。

Log (99,999,999 + 1,000,000) / Log(2) = 26.59。你的内存中有2^28位。你只需要用一半!