在1 MB的RAM中的数字数字
我有一台带有1 MB RAM的计算机，没有其他本地存储。 我必须使用它通过TCP连接接受100万个8位十进制数字，对它们进行排序，然后通过另一个TCP连接发送排序列表。
数字列表可能包含重复，我不能放弃。 代码将被放置在ROM中，所以我不需要从1 MB中减去我的代码的大小。 我已经有了驱动以太网端口和处理TCP / IP连接的代码，并且它需要2 KB的状态数据，包括1 KB缓冲区，通过该缓冲区，代码将读取和写入数据。 有没有解决这个问题的方法？
问题和答案的来源：
slashdot.org
cleaton.net
这里有一些可以解决问题的工作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秒。 假设程序名为sort1mb.exe ，您可以使用以下Python脚本验证程序是否工作。
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('%08dn' % value)
sorter.stdin.close()
result = [int(line) for line in sorter.stdout]
print('OK!' if result == sorted(sequence) else 'Error!')
该算法的详细说明可以在以下系列文章中找到：
有一个相当偷偷摸摸的技巧到目前为止还没有提到。 我们假设你没有额外的数据存储方式，但这并不是真的。
解决您的问题的一个方法是执行以下可怕的事情，在任何情况下都不应该由任何人尝试：使用网络流量来存储数据。 不，我不是说NAS。
您可以按照以下方式仅用几个字节的RAM对数字排序：
COUNTER和VALUE 。 0 ; I ，增加COUNTER并将VALUE设置为max(VALUE, I) ; 一旦COUNTER达到1000000 ，就会将所有值存储在不断的ICMP请求流中，而VALUE现在包含最大整数。 选择一些threshold T >> 1000000 。 将COUNTER设置为零。 每次收到一个ICMP数据包时，增加COUNTER并将所包含的整数I发送回另一个回应请求中，除非I=VALUE ，在这种情况下，将其传送到排序整数的目标。 一旦COUNTER=T ，将VALUE减1 ，将COUNTER重置为零并重复。 一旦VALUE达到零，你应该已经按照从最大到最小到目的地的顺序传送所有整数，并且只使用大约47位RAM作为两个持久变量（以及临时值所需的任何小数量）。
我知道这太可怕了，我知道可能有各种各样的实际问题，但我认为这可能会让你们中的一些人发笑，或者至少吓到你。
请参阅第一个正确答案或后面的算术编码答案。 下面你可能会发现一些有趣的，但不是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，但仍有一些细节需要强调：
请注意，附加代码是一个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
编辑
结论：
阶段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;
}
请注意，这种方法：
完整的代码可以在这里找到，BinaryInput和BinaryOutput实现可以在这里找到
定论
没有最后的结论:)有时候，从一个元层次的角度来看，把一个层级升级并审查这个任务是个好主意。
花一些时间完成这项任务很有趣。 顺便说一句，下面有很多有趣的答案。 感谢您的关注和快乐编纂。
链接地址: http://www.djcxy.com/p/61375.html上一篇: digit numbers in 1 MB of RAM
下一篇: Difference between classification and clustering in data mining?