在1 MB RAM中排序100万个8位数字

Question

我有一台1 MB RAM的计算机,没有其他本地存储.我必须使用它通过TCP连接接受100万个8位十进制数,对它们进行排序,然后通过另一个TCP连接发送排序列表.

数字列表可能包含重复项,我不能丢弃.代码将放在ROM中,因此我不需要从1 MB中减去代码的大小.我已经有驱动以太网端口和处理TCP/IP连接的代码,它的状态数据需要2 KB,包括1 KB缓冲区,代码将通过该缓冲区读写数据.有这个问题的解决方案吗？

问答来源:
slashdot.org

cleaton.net

Answer 1

到目前为止,这里没有提到一个相当偷偷摸摸的伎俩.我们假设您没有额外的方法来存储数据,但这并不严格.

解决问题的一种方法是执行以下可怕的操作,在任何情况下都不应该尝试任何人:使用网络流量来存储数据.不,我不是指NAS.

您可以通过以下方式仅使用几个字节的RAM对数字进行排序:

• 先拿2个变量:COUNTER和VALUE.
• 首先将所有寄存器设置为0;
• 每次收到整数I,递增COUNTER并设置VALUE为max(VALUE, I);
• 然后将数据集为I的ICMP echo请求包发送给路由器.擦除我并重复.
• 每次收到返回的ICMP数据包时,只需提取整数并在另一个echo请求中再次将其发回.这会产生大量的ICMP请求,它们向前和向后扫描包含整数.

一旦COUNTER达到1000000,你把所有存储的ICMP请求的不断流中的价值观,VALUE现在包含的最大整数.选一些threshold T >> 1000000.设为COUNTER零.每次收到ICMP数据包时,COUNTER在另一个echo请求中递增并发送包含的整数I,除非I=VALUE在这种情况下将其传送到排序整数的目标.一旦COUNTER=T,递减VALUE通过1,复位COUNTER至零和重复.一旦VALUE达到零,你应该按照从最大到最小到目的地的顺序传输所有整数,并且只为这两个持久变量使用大约47位RAM(以及临时值所需的少量数量).

我知道这很可怕,我知道可能存在各种各样的实际问题,但我认为这可能会让你们中的一些人大笑或者至少让你们感到恐惧.

Answer 2

这是一些解决问题的工作C++代码.

证明满足内存约束:

编辑:没有证据证明作者在本文或他的博客中提供了最大内存要求.由于编码值所需的比特数取决于先前编码的值,因此这种证明可能是非平凡的.作者指出,他根据经验偶然发现的最大编码大小是1011732,并且1013000任意选择缓冲区大小.

typedef unsigned int u32;

namespace WorkArea
{
    static const u32 circularSize = 253250;
    u32 circular[circularSize] = { 0 };         // consumes 1013000 bytes

    static const u32 stageSize = 8000;
    u32 stage[stageSize];                       // consumes 32000 bytes

    ...

这两个阵列一起占用1045000字节的存储空间.这留下1048576 - 1045000 - 2×1024 = 1528字节用于剩余变量和堆栈空间.

它在我的Xeon W3520上运行大约23秒.假设程序名称为,则可以使用以下Python脚本验证程序是否正常工作sort1mb.exe.

from subprocess import *
import random

sequence = [random.randint(0, 99999999) for i in xrange(1000000)]

sorter = Popen('sort1mb.exe', stdin=PIPE, stdout=PIPE)
for value in sequence:
    sorter.stdin.write('%08d\n' % value)
sorter.stdin.close()

result = [int(line) for line in sorter.stdout]
print('OK!' if result == sorted(sequence) else 'Error!')

该算法的详细说明可在以下系列文章中找到:

• 1MB排序说明
• 算术编码和1MB排序问题
• 使用定点数学的算术编码

Answer 3

请使用算术编码查看第一个正确答案或更晚的答案.下面你可能会发现一些有趣的,但不是100%的防弹解决方案.

这是一项非常有趣的任务,这是另一种解决方案.我希望有人会发现结果有用(或至少有趣).

第1阶段:初始数据结构,粗略压缩方法,基本结果

让我们做一些简单的数学运算:我们有1M(1048576字节)的RAM最初可用于存储10 ^ 6 8位十进制数.[0; 99999999].因此,需要存储一个数字27位(假设将使用无符号数).因此,要存储原始流〜需要3.5M的RAM.有人已经说过这似乎不可行,但我会说如果输入"足够好",任务就可以解决.基本上,想法是压缩因子为0.29或更高,并以适当的方式进行排序.

让我们先解决压缩问题.已经有一些相关的测试:

http://www.theeggeadventure.com/wikimedia/index.php/Java_Data_Compression

"我进行了一项测试,使用各种形式的压缩来压缩一百万个连续的整数.结果如下:"

None     4000027
Deflate  2006803
Filtered 1391833
BZip2    427067
Lzma     255040

看起来LZMA(Lempel-Ziv-Markov链算法)是继续使用的不错选择.我准备了一个简单的PoC,但仍有一些细节要突出:

1. 内存有限,因此想法是预先设定数字并使用压缩桶(动态大小)作为临时存储
2. 使用预先排序的数据更容易实现更好的压缩因子,因此每个桶都有一个静态缓冲区(缓冲区中的数字要在LZMA之前排序)
3. 每个桶都有一个特定的范围,因此可以分别对每个桶进行最终排序
4. 可以正确设置存储桶的大小,因此将有足够的内存来解压缩存储的数据并分别对每个存储桶进行最终排序

请注意,附加代码是POC,它不能用作最终解决方案,它只是演示了使用几个较小的缓冲区以某种最佳方式(可能是压缩)存储预分类数字的想法.LZMA不是最终解决方案.它被用作向此PoC引入压缩的最快方式.

请参阅下面的PoC代码(请注意它只是一个演示,要编译它将需要LZMA-Java):

public class MemorySortDemo {

static final int NUM_COUNT = 1000000;
static final int NUM_MAX   = 100000000;

static final int BUCKETS      = 5;
static final int DICT_SIZE    = 16 * 1024; // LZMA dictionary size
static final int BUCKET_SIZE  = 1024;
static final int BUFFER_SIZE  = 10 * 1024;
static final int BUCKET_RANGE = NUM_MAX / BUCKETS;

static class Producer {
    private Random random = new Random();
    public int produce() { return random.nextInt(NUM_MAX); }
}

static class Bucket {
    public int size, pointer;
    public int[] buffer = new int[BUFFER_SIZE];

    public ByteArrayOutputStream tempOut = new ByteArrayOutputStream();
    public DataOutputStream tempDataOut = new DataOutputStream(tempOut);
    public ByteArrayOutputStream compressedOut = new ByteArrayOutputStream();

    public void submitBuffer() throws IOException {
        Arrays.sort(buffer, 0, pointer);

        for (int j = 0; j < pointer; j++) {
            tempDataOut.writeInt(buffer[j]);
            size++;
        }            
        pointer = 0;
    }

    public void write(int value) throws IOException {
        if (isBufferFull()) {
            submitBuffer();
        }
        buffer[pointer++] = value;
    }

    public boolean isBufferFull() {
        return pointer == BUFFER_SIZE;
    }

    public byte[] compressData() throws IOException {
        tempDataOut.close();
        return compress(tempOut.toByteArray());
    }        

    private byte[] compress(byte[] input) throws IOException {
        final BufferedInputStream in = new BufferedInputStream(new ByteArrayInputStream(input));
        final DataOutputStream out = new DataOutputStream(new BufferedOutputStream(compressedOut));

        final Encoder encoder = new Encoder();
        encoder.setEndMarkerMode(true);
        encoder.setNumFastBytes(0x20);
        encoder.setDictionarySize(DICT_SIZE);
        encoder.setMatchFinder(Encoder.EMatchFinderTypeBT4);

        ByteArrayOutputStream encoderPrperties = new ByteArrayOutputStream();
        encoder.writeCoderProperties(encoderPrperties);
        encoderPrperties.flush();
        encoderPrperties.close();

        encoder.code(in, out, -1, -1, null);
        out.flush();
        out.close();
        in.close();

        return encoderPrperties.toByteArray();
    }

    public int[] decompress(byte[] properties) throws IOException {
        InputStream in = new ByteArrayInputStream(compressedOut.toByteArray());
        ByteArrayOutputStream data = new ByteArrayOutputStream(10 * 1024);
        BufferedOutputStream out = new BufferedOutputStream(data);

        Decoder decoder = new Decoder();
        decoder.setDecoderProperties(properties);
        decoder.code(in, out, 4 * size);

        out.flush();
        out.close();
        in.close();

        DataInputStream input = new DataInputStream(new ByteArrayInputStream(data.toByteArray()));
        int[] array = new int[size];
        for (int k = 0; k < size; k++) {
            array[k] = input.readInt();
        }

        return array;
    }
}

static class Sorter {
    private Bucket[] bucket = new Bucket[BUCKETS];

    public void doSort(Producer p, Consumer c) throws IOException {

        for (int i = 0; i < bucket.length; i++) {  // allocate buckets
            bucket[i] = new Bucket();
        }

        for(int i=0; i< NUM_COUNT; i++) {         // produce some data
            int value = p.produce();
            int bucketId = value/BUCKET_RANGE;
            bucket[bucketId].write(value);
            c.register(value);
        }

        for (int i = 0; i < bucket.length; i++) { // submit non-empty buffers
            bucket[i].submitBuffer();
        }

        byte[] compressProperties = null;
        for (int i = 0; i < bucket.length; i++) { // compress the data
            compressProperties = bucket[i].compressData();
        }

        printStatistics();

        for (int i = 0; i < bucket.length; i++) { // decode & sort buckets one by one
            int[] array = bucket[i].decompress(compressProperties);
            Arrays.sort(array);

            for(int v : array) {
                c.consume(v);
            }
        }
        c.finalCheck();
    }

    public void printStatistics() {
        int size = 0;
        int sizeCompressed = 0;

        for (int i = 0; i < BUCKETS; i++) {
            int bucketSize = 4*bucket[i].size;
            size += bucketSize;
            sizeCompressed += bucket[i].compressedOut.size();

            System.out.println("  bucket[" + i
                    + "] contains: " + bucket[i].size
                    + " numbers, compressed size: " + bucket[i].compressedOut.size()
                    + String.format(" compression factor: %.2f", ((double)bucket[i].compressedOut.size())/bucketSize));
        }

        System.out.println(String.format("Data size: %.2fM",(double)size/(1014*1024))
                + String.format(" compressed %.2fM",(double)sizeCompressed/(1014*1024))
                + String.format(" compression factor %.2f",(double)sizeCompressed/size));
    }
}

static class Consumer {
    private Set<Integer> values = new HashSet<>();

    int v = -1;
    public void consume(int value) {
        if(v < 0) v = value;

        if(v > value) {
            throw new IllegalArgumentException("Current value is greater than previous: " + v + " > " + value);
        }else{
            v = value;
            values.remove(value);
        }
    }

    public void register(int value) {
        values.add(value);
    }

    public void finalCheck() {
        System.out.println(values.size() > 0 ? "NOT OK: " + values.size() : "OK!");
    }
}

public static void main(String[] args) throws IOException {
    Producer p = new Producer();
    Consumer c = new Consumer();
    Sorter sorter = new Sorter();

    sorter.doSort(p, c);
}
}

随机数字产生以下内容:

bucket[0] contains: 200357 numbers, compressed size: 353679 compression factor: 0.44
bucket[1] contains: 199465 numbers, compressed size: 352127 compression factor: 0.44
bucket[2] contains: 199682 numbers, compressed size: 352464 compression factor: 0.44
bucket[3] contains: 199949 numbers, compressed size: 352947 compression factor: 0.44
bucket[4] contains: 200547 numbers, compressed size: 353914 compression factor: 0.44
Data size: 3.85M compressed 1.70M compression factor 0.44

对于简单的升序(使用一个桶),它产生:

bucket[0] contains: 1000000 numbers, compressed size: 256700 compression factor: 0.06
Data size: 3.85M compressed 0.25M compression factor 0.06

编辑

结论:

1. 不要试图欺骗大自然
2. 使用更简单的压缩,内存占用更少
3. 真的需要一些额外的线索.常见的防弹解决方案似乎不可行.

阶段2:增强压缩,最终结论

如前一节中已经提到的,可以使用任何合适的压缩技术.因此,让我们摆脱LZMA,转而采用更简单,更好(如果可能)的方法.有许多好的解决方案,包括算术编码,基数树等.

无论如何,简单但有用的编码方案将比另一个外部库更具说明性,提供一些漂亮的算法.实际的解决方案非常简单:由于存在具有部分排序数据的存储桶,因此可以使用增量而不是数字.

随机输入测试显示略好的结果:

bucket[0] contains: 10103 numbers, compressed size: 13683 compression factor: 0.34
bucket[1] contains: 9885 numbers, compressed size: 13479 compression factor: 0.34
...
bucket[98] contains: 10026 numbers, compressed size: 13612 compression factor: 0.34
bucket[99] contains: 10058 numbers, compressed size: 13701 compression factor: 0.34
Data size: 3.85M compressed 1.31M compression factor 0.34

示例代码

  public static void encode(int[] buffer, int length, BinaryOut output) {
    short size = (short)(length & 0x7FFF);

    output.write(size);
    output.write(buffer[0]);

    for(int i=1; i< size; i++) {
        int next = buffer[i] - buffer[i-1];
        int bits = getBinarySize(next);

        int len = bits;

        if(bits > 24) {
          output.write(3, 2);
          len = bits - 24;
        }else if(bits > 16) {
          output.write(2, 2);
          len = bits-16;
        }else if(bits > 8) {
          output.write(1, 2);
          len = bits - 8;
        }else{
          output.write(0, 2);
        }

        if (len > 0) {
            if ((len % 2) > 0) {
                len = len / 2;
                output.write(len, 2);
                output.write(false);
            } else {
                len = len / 2 - 1;
                output.write(len, 2);
            }

            output.write(next, bits);
        }
    }
}

public static short decode(BinaryIn input, int[] buffer, int offset) {
    short length = input.readShort();
    int value = input.readInt();
    buffer[offset] = value;

    for (int i = 1; i < length; i++) {
        int flag = input.readInt(2);

        int bits;
        int next = 0;
        switch (flag) {
            case 0:
                bits = 2 * input.readInt(2) + 2;
                next = input.readInt(bits);
                break;
            case 1:
                bits = 8 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 2:
                bits = 16 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 3:
                bits = 24 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
        }

        buffer[offset + i] = buffer[offset + i - 1] + next;
    }

   return length;
}

请注意,这种方法:

1. 不消耗大量内存
2. 适用于溪流
3. 提供不那么糟糕的结果

完整的代码可以发现在这里,BinaryInput和BinaryOutput实现,可以发现这里

定论

没有最终结论:)有时,从元级别的角度来看,提升一级并审查任务是一个非常好的主意.

花一些时间完成这项任务很有趣.顺便说一下,下面有很多有趣的答案.感谢您的关注和愉快的编码.

Answer 4

只有1兆字节和1百万字节之间的差异才能实现解决方案.大约有2到电源8093729.5不同的方式来选1万,允许重复和顺序不重要的8位数字,所以只有1百万字节的RAM,机器没有足够的状态来表示一切准备.但是1M(TCP/IP少于2k)是1022*1024*8 = 8372224位,因此可以实现解决方案.

第1部分,初始解决方案

这种方法需要略高于1M,我将其改进以适应1M以后.

我将存储0到99999999范围内的紧凑排序列表作为7位数字的子列表序列.第一个子列表包含0到127之间的数字,第二个子列表包含128到255之间的数字等.100000000/128正好是781250,因此需要781250个这样的子列表.

每个子列表由一个2位子列表头和一个子列表主体组成.子列表主体每个子列表条目占用7位.子列表全部连接在一起,格式使得可以分辨一个子列表的结束位置和下一个子列表的开始位置.完全填充列表所需的总存储量为2*781250 + 7*1000000 = 8562500位,大约为1.021 M字节.

4个可能的子列表标题值为:

00清空子列表,后面没有任何内容.

01单例,子列表中只有一个条目,接下来的7位保留它.

10子列表至少包含2个不同的数字.条目以非递减顺序存储,除了最后一个条目小于或等于第一个条目.这允许识别子列表的结尾.例如,数字2,4,6将存储为(4,6,2).数字2,2,3,4,4将存储为(2,3,4,4,2).

11子列表包含2个或更多个单个数字的重复.接下来的7位给出了数字.然后得到零或多个值为1的7位条目,接着是值为0的7位条目.子列表主体的长度决定了重复次数.例如,数字12,12将存储为(12,0),数字12,12,12将存储为(12,1,0),12,12,12,12将存储为(12,1) ,1,0)等.

我从一个空列表开始,读取一堆数字并将它们存储为32位整数,对新数字进行排序(可能使用heapsort),然后将它们合并到一个新的紧凑排序列表中.重复直到没有更多数字要读取,然后再次走紧凑列表以生成输出.

下面的行表示列表合并操作开始之前的内存."O"是保存排序的32位整数的区域."X"是保存旧紧凑列表的区域."="符号是紧凑列表的扩展空间,"O"中的每个整数为7位."Z"是其他随机开销.

ZZZOOOOOOOOOOOOOOOOOOOOOOOOOO==========XXXXXXXXXXXXXXXXXXXXXXXXXX

合并例程开始读取最左边的"O"和最左边的"X",并开始在最左边的"="处写入.写指针不赶紧凑链表读指针,直到所有的新整数的合并,因为这两个指针提前为每个子表2位和第7位在旧紧凑列表中的每个条目,没有为足够的额外房间新数字的7位条目.

第2部分,将其塞进1M

要将上面的解决方案挤压到1M,我需要使紧凑列表格式更紧凑.我将摆脱其中一个子列表类型,因此只有3种不同的子列表标题值.然后我可以使用"00","01"和"1"作为子列表标题值并保存几位.子列表类型是:

空子列表,后面没有任何内容.

B Singleton,子列表中只有一个条目,接下来的7位保留它.

C子列表包含至少2个不同的数字.条目以非递减顺序存储,除了最后一个条目小于或等于第一个条目.这允许识别子列表的结尾.例如,数字2,4,6将存储为(4,6,2).数字2,2,3,4,4将存储为(2,3,4,4,2).

D子列表包含2个或更多个单个数字的重复.

我的3个子列表标题值将是"A","B"和"C",所以我需要一种方法来表示D类型的子列表.

假设我有C型子列表标题后跟3个条目,例如"C [17] [101] [58]".这不能是如上所述的有效C类子列表的一部分,因为第三个条目小于第二个条目但是多于第一条目.我可以使用这种类型的构造来表示D类子列表.在比特术语中,我有"C {00 ?????} {1 ??????} {01 ?????}"是一个不可能的C型子列表.我将使用它来表示由3个或更多个单个数字重复组成的子列表.前两个7位字对数字进行编码(下面的"N"位),然后是零个或多个{0100001}字,后跟{0100000}字.

For example, 3 repetitions: "C{00NNNNN}{1NN0000}{0100000}", 4 repetitions: "C{00NNNNN}{1NN0000}{0100001}{0100000}", and so on.

这只留下了只包含2个重复单个数字的列表.我将用另一个不可能的C型子列表模式代表那些:"C {0 ??????} {11 ?????} {10 ?????}".前两个单词中7位数字有足够的空间,但这种模式比它所代表的子列表更长,这使得事情变得更复杂.在端部的五个问题的标志可以被认为不是图案的一部分,所以我有:"C {0NNNNNN} {11N ????} 10"作为我的图案,用数被重复存储在"N "S.那是2位太长了.

我将不得不借用2位并从这种模式中的4个未使用的位中支付它们.读取时,在遇到"C {0NNNNNN} {11N00AB} 10",输出在"N"的数量的2个实例,覆盖"10"在与比特A和B的端部,并且通过2倒带读取指针位.这种算法的破坏性读取是可以的,因为每个紧凑列表只能走一次.

当写入的2次重复的单个数字的子列表,写"C {0NNNNNN} 11N00"和计数器设置借用位到2.在每次写入其中借位计数器是非零的,则递减为写入每一位,并当计数器达到零时写入"10".所以写入的下两位将进入插槽A和B,然后"10"将被放到最后.

使用由"00","01"和"1"表示的3个子列表标题值,我可以将"1"分配给最流行的子列表类型.我需要一个小表来将子列表头值映射到子列表类型,并且我需要每个子列表类型的出现计数器,以便我知道最佳子列表头映射是什么.

当所有子列表类型同样受欢迎时,出现完全填充的紧凑列表的最坏情况最小表示.在这种情况下,我为每3个子列表标题保存1位,因此列表大小为2*781250 + 7*1000000 - 781250/3 = 8302083.3位.舍入到32位字边界,即8302112位,或10​​37764字节.

1M减去TCP/IP状态和缓冲区的2k是1022*1024 = 1046528字节,留下8764字节.

但是更改子列表头映射的过程呢？在下面的存储器映射中,"Z"是随机开销,"="是自由空间,"X"是紧凑列表.

ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

从最左边的"X"开始阅读并开始写在最左边的"="并向右工作.当它完成后,紧凑列表将会更短一点,并且它将位于错误的内存末尾:

ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======

那么我需要将它分流到右边:

ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

在标头映射更改过程中,最多1/3的子列表标头将从1位更改为2位.在最坏的情况下,这些都将位于列表的首位,因此在开始之前我需要至少781250/3位的空闲存储空间,这使我回到了先前版本的紧凑列表的内存要求: (

为了解决这个问题,我将把781250子列表分成10个子列表组,每个子列表包含78125个子列表.每个组都有自己独立的子列表头映射.使用字母A到J为组:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

在子列表标题映射更改期间,每个子列表组都缩小或保持不变:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAA=====BBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABB=====CCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCC======DDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDD======EEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEE======FFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFF======GGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGG=======HHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHH=======IJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHI=======JJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ=======
ZZZ=======AAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

在映射更改期间,子列表组的最坏情况临时扩展是78125/3 = 26042位,低于4k.如果我允许4k加上1037764字节用于完全填充的紧凑列表,那么对于存储器映射中的"Z",我留下8764 - 4096 = 4668字节.

对于10个子列表头映射表,30个子列表头事件计数以及我需要的其他几个计数器,指针和小缓冲区,以及我在没有注意到的情况下使用的空间,如函数调用返回地址的堆栈空间和局部变量.

第3部分,运行需要多长时间？

对于空紧凑列表,1位列表标题将用于空子列表,列表的起始大小将为781250位.在最坏的情况下,对于每个添加的数字,列表增长8位,因此每个32位数字需要32 + 8 = 40位的可用空间放置在列表缓冲区的顶部,然后进行排序和合并.在最坏的情况下,更改子列表标头映射会导致空间使用量为2*781250 + 7*个条目 - 781250/3位.

一旦在列表中存在至少800000个数字,在每第五次合并之后改变子列表头部映射的策略,最坏的情况运行将涉及总共约30M的紧凑列表读取和写入活动.

资源:

http://nick.cleaton.net/ramsortsol.html

Answer 5

吉尔马诺夫的答案在其假设中是非常错误的.它开始根据一百万个连续整数的毫无意义的度量进行推测.这意味着没有差距.那些随机的差距,无论多么小,都会让它成为一个糟糕的主意.

亲自尝试一下.得到100万随机27​​位整数,对它们进行排序,用7-Zip,xz 压缩,无论你想要什么LZMA.结果超过1.5 MB.最重要的前提是压缩序列号.甚至delta编码也超过1.1 MB.不用担心这会使用超过100 MB的RAM进行压缩.因此,即使压缩整数也不适合这个问题,更不用说运行时RAM的使用.

让我感到很难过的是人们如何赞美漂亮的图形和合理化.

#include <stdint.h>
#include <stdlib.h>
#include <time.h>

int32_t ints[1000000]; // Random 27-bit integers

int cmpi32(const void *a, const void *b) {
    return ( *(int32_t *)a - *(int32_t *)b );
}

int main() {
    int32_t *pi = ints; // Pointer to input ints (REPLACE W/ read from net)

    // Fill pseudo-random integers of 27 bits
    srand(time(NULL));
    for (int i = 0; i < 1000000; i++)
        ints[i] = rand() & ((1<<27) - 1); // Random 32 bits masked to 27 bits

    qsort(ints, 1000000, sizeof (ints[0]), cmpi32); // Sort 1000000 int32s

    // Now delta encode, optional, store differences to previous int
    for (int i = 1, prev = ints[0]; i < 1000000; i++) {
        ints[i] -= prev;
        prev    += ints[i];
    }

    FILE *f = fopen("ints.bin", "w");
    fwrite(ints, 4, 1000000, f);
    fclose(f);
    exit(0);

}

现在使用LZMA压缩ints.bin ...

$ xz -f --keep ints.bin       # 100 MB RAM
$ 7z a ints.bin.7z ints.bin   # 130 MB RAM
$ ls -lh ints.bin*
    3.8M ints.bin
    1.1M ints.bin.7z
    1.2M ints.bin.xz

Answer 6

我认为考虑这个问题的一种方法是从组合学的角度来看:有多少可能的排序数字排序组合？如果我们给组合0,0,0,....,0代码0和0,0,0,...,1代码1,和99999999,99999999,... 99999999代码N,什么是N？换句话说,结果空间有多大？

好吧,考虑到这一点的一种方法是注意到这是在N×M网格中找到单调路径数量的问题的双射,其中N = 1,000,000且M = 100,000,000.换句话说,如果你的网格宽度为1,000,000,高度为100,000,000,那么从左下角到右上角的最短路径是多少？最短的路径当然要求你只要向右或向上移动(如果你要向下或向左移动,你将取消之前完成的进展).要查看这是否是我们的数字排序问题的双射,请遵守以下内容:

您可以将我们路径中的任何水平支路想象为我们的排序中的数字,其中支路的Y位置代表值.

因此,如果路径只是一直向右移动到最后,那么一直跳到顶部,这相当于排序0,0,0,...,0.如果它开始一直跳到顶部然后向右移动1,000,000次,那相当于99999999,99999999,...,99999999.它向右移动一次,然后向上移动一次,然后向右移动一次的路径,然后一次,等到最后(然后必然一直跳到顶部),相当于0,1,2,3,...,999999.

幸运的是,这个问题已经解决,这样的网格有(N + M)选择(M)路径:

(1,000,000 + 100,000,000)选择(100,000,000)〜= 2.27*10 ^ 2436455

N因此等于2.27*10 ^ 2436455,因此代码0代表0,0,0,...,0和代码2.27*10 ^ 2436455,一些变化代表99999999,99999999,...,99999999.

In order to store all the numbers from 0 to 2.27*10^2436455 you need lg2 (2.27*10^2436455) = 8.0937*10^6 bits.

1 megabyte = 8388608 bits > 8093700 bits

So it appears that we at least actually have enough room to store the result! Now of course the interesting bit is doing the sorting as the numbers stream in. Not sure the best approach to this is given we have 294908 bits remaining. I imagine an interesting technique would be to at each point assume that that is is the entire ordering, finding the code for that ordering, and then as you receive a new number going back and updating the previous code. Hand wave hand wave.

Answer 7

我在这里的建议很大程度上归功于Dan的解决方案

首先,我假设解决方案必须处理所有可能的输入列表.我认为流行的答案没有做出这个假设(IMO是一个巨大的错误).

众所周知,任何形式的无损压缩都会减小所有输入的大小.

所有流行的答案都假设他们能够有效地应用压缩,以便为他们提供额外的空间.事实上,一大块额外的空间足够大,可以以未压缩的形式保存部分完成的列表的某些部分,并允许它们执行排序操作.这只是一个不好的假设.

对于这样的解决方案,任何知道如何进行压缩的人都能够设计一些不能很好地压缩该方案的输入数据,并且"解决方案"很可能会因空间不足而中断.

相反,我采取数学方法.我们可能的输出是长度LEN的所有列表,包括0..MAX范围内的元素.LEN为1,000,000,MAX为100,000,000.

对于任意LEN和MAX,编码此状态所需的位数为:

Log2(MAX Multichoose LEN)

因此,对于我们的数字,一旦我们完成接收和排序,我们将至少需要Log2(100,000,000 MC 1,000,000)位来存储我们的结果,以便能够唯一地区分所有可能的输出.

这是〜= 988kb.所以我们实际上有足够的空间来保持我们的结果.从这个角度来看,这是可能的.

[现在存在更好的例子,删除了毫无意义的漫无边际......]

最好的答案就在这里.

另一个好的答案是在这里,基本上使用插入排序作为扩展列表一个元素的功能(缓冲一些元素和预先排序,允许一次插入多个元素,节省一点时间).使用一个很好的紧凑状态编码,七位增量的桶

Answer 8

假设这个任务是可能的.在输出之前,将存在百万个已排序数字的内存表示.有多少种不同的表示形式？由于可能有重复的数字,我们不能使用nCr(选择),但有一个名为multichoose的操作适用于多重集合.

• 有2.2e2436455种方法可以在0..99,999,999的范围内选择一百万个数字.
• 这需要8,093,730位来表示每种可能的组合,或1,011,717字节.

所以从理论上讲,如果你能想出一个合理的数字列表的理智(足够)表示,那么它是可能的.例如,疯狂的表示可能需要10MB的查找表或数千行代码.

但是,如果"1M RAM"意味着一百万字节,那么显然没有足够的空间.事实上,5%的内存使其在理论上成为可能,这一事实向我表明,该表示必须非常高效且可能并不理智.

Answer 9

(我原来的回答是错误的,抱歉数学不好,见下面的休息.)

这个怎么样？

前27位存储您看到的最低数字,然后与下一个数字的差异,编码如下:5位用于存储用于存储差异的位数,然后是差值.使用00000表示您再次看到该号码.

这是有效的,因为随着插入的数字越来越多,数字之间的平均差异会下降,因此在添加更多数字时使用较少的位来存储差异.我相信这被称为增量列表.

我能想到的最糟糕的情况是所有数字均匀间隔(100),例如假设0是第一个数字:

000000000000000000000000000 00111 1100100
                            ^^^^^^^^^^^^^
                            a million times

27 + 1,000,000 * (5+7) bits = ~ 427k

Reddit来救援!

如果您只需要对它们进行排序,那么这个问题就很容易了.需要122k(100万位)才能存储您看到的数字(如果看到0则为第0位,如果看到2300则为第2300位,等等).

您读取数字,将它们存储在位字段中,然后在保持计数的同时将位移出.

但是,你必须记住你见过多少.我受到上面的子列表答案的启发,想出了这个方案:

不使用一位,而是使用2位或27位:

• 00表示您没有看到该号码.
• 01意味着你曾经看过它
• 1意味着你看到它,接下来的26位是多少次的计数.

我认为这是有效的:如果没有重复,你有一个244k列表.在最坏的情况下,您会看到每个数字两次(如果您看到一个数字三次,它会缩短列表的其余部分),这意味着您已经多次看到50,000个,并且您已经看到了950,000个项目0或1次.

50,000*27 + 950,000*2 = 396.7k.

如果使用以下编码,则可以进一步改进:

0意味着你没有看到数字10意味着你曾经看过它11你是如何计算的

平均而言,这将导致280.7k的存储空间.

编辑:我周日早上的数学错了.

最糟糕的情况是我们两次看到500,000个数字,所以数学变为:

500,000*27 + 500,000*2 = 1.77M

备用编码导致平均存储空间

500,000*27 + 500,000 = 1.70M

:(

Answer 10

所有可能的输入都有一个解决这个问题的方法.作弊.

1. 通过TCP读取m值,其中m接近可以在内存中排序的最大值,可能是n/4.
2. 对250,000(左右)数字进行排序并输出.
3. 重复其他3个季度.
4. 让接收器合并它在处理它时收到的4个数字列表.(它比使用单个列表慢得多.)

Answer 11

我会试一下Radix Tree.如果可以将数据存储在树中,则可以执行有序遍历来传输数据.

我不确定你能把它装到1MB,但我认为值得一试.

Answer 12

你用的是什么类型的电脑？它可能没有任何其他"正常"本地存储,但它有没有视频RAM,例如？每像素1百万像素×32位(比如说)非常接近您所需的数据输入大小.

(我主要要求记住旧的Acorn RISC PC,如果您选择低分辨率或低色深度屏幕模式,它可以"借用"VRAM来扩展可用的系统RAM!).这在只有几MB普通RAM的机器上非常有用.

Answer 13

基数树表示将接近处理此问题,因为基数树利用"前缀压缩".但是很难想象一个基数树表示可以代表一个字节中的单个节点 - 两个可能是极限.

但是,无论数据如何表示,一旦它被排序,它可以以前缀压缩形式存储,其中数字10,11和12将由例如001b,001b,001b表示,表示增量为1从前一个号码.那么,10101b可能代表5,1101001b的增量,增量为9,等等.

Answer 14

在10 ^ 8的范围内有10 ^ 6个值,因此平均每百个代码点有一个值.存储从第N个点到第(N + 1)个的距离.重复值跳过0.这意味着跳过需要平均不到7位才能存储,因此其中有数百万将很高兴地适应我们的800万位存储.

需要将这些跳过编码为比特流,例如通过霍夫曼编码.插入是通过迭代比特流并在新值之后重写.通过迭代并写出隐含值来输出.实际上,它可能希望完成,例如,10 ^ 4个列表,每个列表覆盖10 ^ 4个代码点(平均值为100个值).

通过假设跳过的长度上的泊松分布(均值=方差= 100),可以先验地建立用于随机数据的良好霍夫曼树,但是可以在输入上保持真实的统计数据并用于生成用于处理的最优树.病理病例.

Answer 15

我有一台带有1M RAM的计算机,没有其他本地存储

另一种欺骗方式:您可以使用非本地(联网)存储(您的问题不排除这一点)并调用可以使用简单的基于磁盘的mergesort的网络服务(或者只是足够的RAM来排序内存,因为您只需要接受1M的数字),而不需要已经给出的(无可否认的非常巧妙)解决方案.

这可能是作弊,但目前尚不清楚你是在寻找现实世界问题的解决方案,还是一个引起规则弯曲的谜题......如果是后者,那么简单的作弊可能比复杂的结果更好但"真正的"解决方案(正如其他人所指出的那样,只适用于可压缩输入).

Answer 16

Google的（坏）方法，来自 HN 线程。存储 RLE 风格的计数。

您的初始数据结构是“99999999:0”（全零，没有看到任何数字），然后假设您看到数字 3,866,344，因此您的数据结构变为“3866343:0,1:1,96133654:0”可以看到数字总是在零位数和“1”位数之间交替，因此您可以假设奇数代表 0 位，偶数代表 1 位。这变成 (3866343,1,96133654)

他们的问题似乎不包括重复项，但假设他们使用“0:1”表示重复项。

大问题 #1：插入 1M 整数需要很长时间。

大问题#2：像所有普通的 delta 编码解决方案一样，某些发行版无法以这种方式覆盖。例如，距离为 0:99 的 1m 整数（例如，每个整数 +99）。现在认为相同但随机距离在0:99 范围内。（注：99999999/1000000 = 99.99）

谷歌的方法既不值得（缓慢）又不正确。但为了他们的辩护，他们的问题可能略有不同。

Answer 17

我认为解决方案是结合视频编码技术,即离散余弦变换.在数字视频中,而不是将视频的亮度或颜色改变为常规值,例如110 112 115 116,每个都从最后一个中减去(类似于游程长度编码).110 112 115 116变为110 2 3 1.值2 3 1比原件需要更少的位.

因此,假设我们在输入值到达套接字时创建一个输入值列表.我们存储在每个元素中,而不是值,而是存储在它之前的元素的偏移量.我们按照我们的方式排序,因此抵消只会是积极的.但是偏移量可以是8位十进制数,这适合3个字节.每个元素不能是3个字节,所以我们需要打包这些.我们可以使用每个字节的最高位作为"继续位",表示下一个字节是数字的一部分,每个字节的低7位需要组合.零对重复有效.

当列表填满时,数字应该更加接近,这意味着平均只有1个字节用于确定到下一个值的距离.如果方便的话,7位值和1位偏移量,但是对于"继续"值,可能存在需要少于8位的最佳位置.

无论如何,我做了一些实验.我使用随机数生成器,我可以将一百万个排序的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);
    }
}