我有一台有1mb内存的电脑,没有其他本地存储。我必须使用它通过TCP连接接受100万个8位十进制数字,对它们进行排序,然后通过另一个TCP连接发送排序的列表。

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

问答来源:

slashdot.org

cleaton.net


当前回答

我将利用TCP的重传行为。

让TCP组件创建一个大的接收窗口。 收到一定数量的包,但没有发送ACK。 处理这些传递,创建一些(前缀)压缩数据结构 对最后一个不再需要的数据包发送重复的ack /等待重传超时 转到2 所有数据包被接受

这假设了桶或多次传递的某种好处。

可能是通过对批次/桶进行排序并合并它们。->根树

使用这种技术接受并排序前80%,然后读取后20%,验证后20%不包含将落在最低数字的前20%的数字。然后发送最低的20%的数字,从内存中删除,接受剩下的20%的新数字并合并。**

其他回答

我认为解决方案是结合视频编码的技术,即离散余弦变换。在数字视频中,不是将视频的亮度或颜色的变化记录为常规值,如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);
    }
}

如果数字的范围是有限的(只能有2个8位数,或者只有10个不同的8位数),那么你可以编写一个优化的排序算法。但如果你想对所有可能的8位数进行排序,这在内存那么少的情况下是不可能的。

你最多要数到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位。你只需要用一半!

假设这个任务是可能的。在输出之前,内存中会有一个百万个排序数字的表示。有多少种不同的表示法?由于可能有重复的数字,我们不能使用nCr(选择),但有一种叫做multichoose的操作,它适用于多集。

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

所以理论上是可能的,如果你能想出一个合理(足够)的数字排序表。例如,一个疯狂的表示可能需要一个10MB的查找表或数千行代码。

但是,如果“1M RAM”意味着100万个字节,那么显然没有足够的空间。事实上,多5%的内存使它在理论上成为可能,这对我来说意味着表示必须非常有效,可能是不理智的。

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