我有一台有1mb内存的电脑，没有其他本地存储。我必须使用它通过TCP连接接受100万个8位十进制数字，对它们进行排序，然后通过另一个TCP连接发送排序的列表。
数字列表可能包含重复的，我不能丢弃。代码将放在ROM中，所以我不需要从1 MB中减去我的代码的大小。我已经有了驱动以太网端口和处理TCP/IP连接的代码，它需要2 KB的状态数据，包括1 KB的缓冲区，代码将通过它读取和写入数据。这个问题有解决办法吗?
问答来源:
slashdot.org
cleaton.net
当前回答
(我原来的答案是错误的，对不起，数学不好，见下面的休息。)
这个怎么样?
前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位代替1位:
00表示你没有看到这个数字。 01表示你看过一次 1表示你看过，接下来的26位是看了多少次。
我认为这是可行的:如果没有重复，你就有一个244k的列表。 在最坏的情况下，你看到每个数字两次(如果你看到一个数字三次，它会缩短列表的其余部分)，这意味着你不止一次看到了50,000个，你0次或1次看到了950,000个项目。
50,000 * 27 + 950,000 * 2 = 396.7k.
如果你使用以下编码，你可以做进一步的改进:
0表示你没有看到这个数字 10表示你看过一次 11是你计数的方式
这将导致平均280.7k的存储空间。
编辑:我周日早上的数学算错了。
最坏的情况是，我们两次看到50万个数字，所以数学就变成了:
500,000 *27 + 500,000 *2 = 1.77M
交替编码导致平均存储为
500,000 * 27 + 500,000 = 1.70M
: (
其他回答
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
谷歌的(坏)方法，从HN线程。存储rle风格的计数。
你的初始数据结构是“99999999:0”(都是零，没有看到任何数字)，然后假设你看到了数字3,866,344，那么你的数据结构就变成了“3866343:0,1:1,96133654:0”，你可以看到数字总是在零位数和1位数之间交替，所以你可以假设奇数代表0位，偶数代表1位。这就变成了(3866343,1,96133654)
他们的问题似乎不包括副本，但让我们假设他们使用“0:1”来表示副本。
大问题#1:1M个整数的插入将花费很长时间。
大问题#2:像所有的普通增量编码解决方案一样，一些分布不能用这种方式覆盖。例如，1m整数，距离为0:99(例如，每个整数+99)。现在考虑相同的情况，但随机距离在0:99的范围内。(注:99999999/1000000 = 99.99)
谷歌的方法既不值得(缓慢)，也不正确。但要为他们辩护，他们的问题可能略有不同。
请参阅第一个正确答案或后面带有算术编码的答案。下面你可能会发现一些有趣的，但不是100%防弹的解决方案。
这是一个非常有趣的任务，这里有另一个解决方案。我希望有人会觉得这个结果有用(或者至少有趣)。
阶段1:初始数据结构，粗略压缩方法，基本结果
Let's do some simple math: we have 1M (1048576 bytes) of RAM initially available to store 10^6 8 digit decimal numbers. [0;99999999]. So to store one number 27 bits are needed (taking the assumption that unsigned numbers will be used). Thus, to store a raw stream ~3.5M of RAM will be needed. Somebody already said it doesn't seem to be feasible, but I would say the task can be solved if the input is "good enough". Basically, the idea is to compress the input data with compression factor 0.29 or higher and do sorting in a proper manner.
让我们先解决压缩问题。有一些相关的测试已经可用:
http://www.theeggeadventure.com/wikimedia/index.php/Java_Data_Compression
“我运行了一个测试，压缩100万个连续整数使用 各种形式的压缩。结果如下:
None 4000027
Deflate 2006803
Filtered 1391833
BZip2 427067
Lzma 255040
看起来LZMA (Lempel-Ziv-Markov链算法)是一个很好的选择。我准备了一个简单的PoC，但仍有一些细节需要强调:
Memory is limited so the idea is to presort numbers and use compressed buckets (dynamic size) as temporary storage It is easier to achieve a better compression factor with presorted data, so there is a static buffer for each bucket (numbers from the buffer are to be sorted before LZMA) Each bucket holds a specific range, so the final sort can be done for each bucket separately Bucket's size can be properly set, so there will be enough memory to decompress stored data and do the final sort for each bucket separately
请注意，所附的代码是一个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
EDIT
结论:
不要试图欺骗大自然 使用更简单的压缩和更低的内存占用 确实需要一些额外的线索。普通的防弹方案似乎并不可行。
第二阶段:强化压缩，最终结论
正如在前一节中已经提到的，任何合适的压缩技术都可以使用。因此，让我们摒弃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;
}
请注意，这种方法:
不消耗大量内存 使用流 提供了不那么坏的结果
完整的代码可以在这里找到，BinaryInput和BinaryOutput实现可以在这里找到
最终结论
没有最终结论:)有时候，从元级别的角度来回顾一下任务，这确实是个好主意。
花点时间完成这个任务很有趣。顺便说一下，下面有很多有趣的答案。感谢您的关注和愉快的编码。
我有一台有1M内存的电脑，没有其他本地存储
另一种作弊方法:你可以使用非本地(网络)存储代替(你的问题不排除这一点)，调用一个网络服务，它可以使用直接的基于磁盘的归并排序(或者只需要足够的RAM来在内存中排序，因为你只需要接受1M的数字)，而不需要(公认非常巧妙的)已经给出的解决方案。
这可能是作弊，但不清楚你是在寻找一个现实问题的解决方案，还是一个让人扭曲规则的谜题……如果是后者，那么简单的欺骗可能比复杂但“真实”的解决方案(正如其他人指出的那样，后者只能用于可压缩输入)得到更好的结果。
你试过转换成十六进制吗?
我可以看到前后文件大小都有了很大的减小;然后，用自由空间分步计算。也许，再次转换为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
