1MB RAM에서 1 백만 개의 8 자리 숫자 정렬
1MB의 RAM이 있고 다른 로컬 저장소가없는 컴퓨터가 있습니다. TCP 연결을 통해 1 백만 개의 8 자리 십진수를 받아들이고 정렬 한 다음 다른 TCP 연결을 통해 정렬 된 목록을 보내야합니다.
번호 목록에는 중복이 포함될 수 있으므로 삭제해서는 안됩니다. 코드는 ROM에 배치되므로 1MB에서 코드 크기를 뺄 필요가 없습니다. 이더넷 포트를 구동하고 TCP / IP 연결을 처리하는 코드가 이미 있으며, 상태 데이터에 2KB가 필요합니다. 여기에는 코드가 데이터를 읽고 쓰는 데 사용하는 1KB 버퍼가 포함됩니다. 이 문제에 대한 해결책이 있습니까?
질문 및 답변 출처 :
지금까지 여기에 언급되지 않은 다소 교활한 속임수가 있습니다. 데이터를 저장할 수있는 추가 방법이 없다고 가정하지만 이는 엄격히 사실이 아닙니다.
문제를 해결하는 한 가지 방법은 다음과 같은 끔찍한 작업을 수행하는 것입니다. 어떤 상황에서도 누구도 시도해서는 안됩니다. 네트워크 트래픽을 사용하여 데이터를 저장합니다. 그리고 아니요, NAS를 의미하는 것이 아닙니다.
다음과 같은 방법으로 몇 바이트의 RAM만으로 숫자를 정렬 할 수 있습니다.
- 먼저 2 개의 변수를 취하십시오 :
COUNTER및VALUE. - 먼저 모든 레지스터를
0; - 정수를받을 때마다
I증분COUNTER하고로 설정VALUE합니다max(VALUE, I). - 그런 다음 I로 설정된 데이터와 함께 ICMP 에코 요청 패킷을 라우터에 보냅니다. I를 지우고 반복하십시오.
- 반환 된 ICMP 패킷을받을 때마다 정수를 추출하고 다른 에코 요청으로 다시 보냅니다. 이로 인해 정수를 포함하는 앞뒤로 이동하는 엄청난 수의 ICMP 요청이 생성됩니다.
에 COUNTER도달하면 1000000모든 값이 ICMP 요청의 끊임없는 스트림에 저장되고 VALUE이제 최대 정수가 포함됩니다. 일부를 선택하십시오 threshold T >> 1000000. COUNTER0으로 설정 합니다. ICMP 패킷을받을 때마다 COUNTER포함 된 정수를 증분 하고 다른 에코 요청에서 다시 보냅니다. I=VALUE이 경우 정렬 된 정수를 위해 대상으로 전송 하지 않습니다 . 일단 COUNTER=T, 감소 VALUE하고 0으로 1재설정 COUNTER하고 반복합니다. 일단 VALUE0에 도달하면 목적지에 큰 수에서 작은 수의 순서로 모든 정수를 전달해야하고, 오직 두 개의 영속 변수 (작은 어떤 양의 임시 값에 필요한)에 대한 RAM의 약 47 비트를 사용하고 있습니다.
나는 이것이 끔찍하다는 것을 알고 있으며 모든 종류의 실제적인 문제가있을 수 있다는 것을 알고 있지만, 나는 그것이 여러분 중 일부를 웃게하거나 적어도 여러분을 겁나게 할 것이라고 생각했습니다.
문제를 해결하는 몇 가지 작동하는 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!')
알고리즘에 대한 자세한 설명은 다음 일련의 게시물에서 찾을 수 있습니다.
첫 번째 정답 또는 산술 인코딩으로 나중 답변을 참조하십시오 . 아래에서 재미를 찾을 수 있지만 100 % 방탄 솔루션은 아닙니다.
이것은 매우 흥미로운 작업이며 여기에 또 다른 해결책이 있습니다. 누군가가 그 결과가 유용하거나 적어도 흥미 롭다고 생각하기를 바랍니다.
1 단계 : 초기 데이터 구조, 대략적인 압축 방식, 기본 결과
몇 가지 간단한 수학을 해봅시다. 처음에는 10 ^ 6 8 자리 십진수를 저장하는 데 사용할 수있는 1M (1048576 바이트)의 RAM이 있습니다. [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를 준비했지만 여전히 강조해야 할 몇 가지 세부 사항이 있습니다.
- 메모리가 제한되어 있으므로 숫자를 사전 정렬하고 압축 된 버킷 (동적 크기)을 임시 저장소로 사용하는 것이 아이디어입니다.
- 사전 정렬 된 데이터로 더 나은 압축 계수를 얻는 것이 더 쉽기 때문에 각 버킷에 대한 정적 버퍼가 있습니다 (버퍼의 숫자는 LZMA 전에 정렬됩니다).
- 각 버킷에는 특정 범위가 있으므로 각 버킷에 대해 개별적으로 최종 정렬을 수행 할 수 있습니다.
- 버킷의 크기를 올바르게 설정할 수 있으므로 저장된 데이터의 압축을 풀고 각 버킷에 대해 개별적으로 최종 정렬을 수행하기에 충분한 메모리가 있습니다.
첨부 된 코드는 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 구현은 여기 에서 찾을 수 있습니다.
최종 결론
최종 결론이 없습니다. :) 때때로 한 단계 위로 올라가 메타 수준의 관점 에서 작업을 검토하는 것이 정말 좋은 생각 입니다.
이 작업에 시간을 보내는 것이 즐거웠습니다. BTW, 아래에 흥미로운 답변이 많이 있습니다. 관심과 즐거운 코딩에 감사드립니다.
솔루션은 1 메가 바이트와 1 백만 바이트의 차이 때문에 가능합니다. 중복이 허용되고 중요하지 않은 순서로 1 백만 개의 8 자리 숫자를 선택하는 약 2의 제곱 8093729.5 다른 방법이 있으므로 RAM이 1 백만 바이트에 불과한 머신은 모든 가능성을 나타낼 수있는 상태가 충분하지 않습니다. 그러나 1M (TCP / IP의 경우 2k 미만)은 1022 * 1024 * 8 = 8372224 비트이므로 솔루션이 가능합니다.
1 부, 초기 솔루션
이 접근 방식은 1M 이상이 필요합니다. 나중에 1M에 맞게 수정하겠습니다.
7 비트 숫자의 하위 목록 시퀀스로 0에서 99999999 범위의 숫자로 구성된 간결한 정렬 목록을 저장할 것입니다. 첫 번째 하위 목록은 0에서 127까지의 숫자를 보유하고 두 번째 하위 목록은 128에서 255까지의 숫자를 보유합니다. 100000000/128은 정확히 781250이므로 781250 이러한 하위 목록이 필요합니다.
각 하위 목록은 2 비트 하위 목록 헤더와 하위 목록 본문으로 구성됩니다. 하위 목록 본문은 하위 목록 항목 당 7 비트를 차지합니다. 하위 목록은 모두 함께 연결되며 형식을 통해 하나의 하위 목록이 끝나고 다음이 시작되는 위치를 알 수 있습니다. 완전히 채워진 목록에 필요한 총 스토리지는 2 * 781250 + 7 * 1000000 = 8562500 비트이며 약 1.021MB입니다.
가능한 4 개의 하위 목록 헤더 값은 다음과 같습니다.
00 빈 하위 목록, 뒤에 아무것도 없습니다.
01 Singleton, 하위 목록에 항목이 하나만 있고 다음 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 개 이상 나오고 값이 0 인 7 비트 항목이 나옵니다. 하위 목록 본문의 길이에 따라 반복 횟수가 결정됩니다. 예를 들어 숫자 12,12는 (12,0), 숫자 12,12,12는 (12,1,0), 12,12,12,12는 (12,1)으로 저장됩니다. , 1,0) 등등.
빈 목록으로 시작하여 여러 숫자를 읽고 32 비트 정수로 저장하고 새 숫자를 제자리에 정렬 한 다음 (아마도 힙 정렬을 사용하여) 새로운 압축 정렬 목록으로 병합합니다. 읽을 숫자가 더 이상 없을 때까지 반복 한 다음 압축 목록을 한 번 더 살펴보고 출력을 생성합니다.
아래 줄은 목록 병합 작업이 시작되기 직전의 메모리를 나타냅니다. "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 [17] [101] [58]"과 같이 3 개의 항목이 뒤에 오는 C 유형 하위 목록 헤더가 있다고 가정합니다. 세 번째 항목은 두 번째 항목보다 작지만 첫 번째 항목보다 많기 때문에 위에서 설명한대로 유효한 C 유형 하위 목록의 일부가 될 수 없습니다. 이 유형의 구성을 사용하여 D 유형 하위 목록을 나타낼 수 있습니다. 간단히 말해서 "C {00 ?????} {1 ??????} {01 ?????}"가있는 곳은 불가능한 C 유형 하위 목록입니다. 나는 이것을 사용하여 단일 숫자의 3 개 이상의 반복으로 구성된 하위 목록을 나타낼 것입니다. 처음 두 개의 7 비트 단어는 숫자 (아래의 "N"비트)를 인코딩하고 0 개 이상의 {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 "에스. 2 비트가 너무 깁니다.
2 비트를 빌려서이 패턴에서 사용하지 않은 4 비트를 갚아야합니다. 읽을 때 "C {0NNNNNN} {11N00AB} 10"이 발견되면 "N"에있는 숫자의 인스턴스 2 개를 출력하고 끝에있는 "10"을 비트 A와 B로 덮어 쓴 다음 읽기 포인터를 2만큼 되감습니다. 비트. 각 압축 목록은 한 번만 실행되므로이 알고리즘에서는 파괴적인 읽기가 괜찮습니다.
단일 숫자의 2 회 반복의 하위 목록을 작성할 때 "C {0NNNNNN} 11N00"을 작성하고 빌린 비트 카운터를 2로 설정합니다. 빌린 비트 카운터가 0이 아닌 모든 쓰기에서 기록 된 각 비트에 대해 감소합니다. 카운터가 0에 도달하면 "10"이 기록됩니다. 따라서 기록 된 다음 2 비트는 슬롯 A와 B로 이동하고 "10"은 끝으로 떨어집니다.
"00", "01"및 "1"로 표시되는 3 개의 하위 목록 헤더 값을 사용하여 가장 인기있는 하위 목록 유형에 "1"을 할당 할 수 있습니다. 하위 목록 헤더 값을 하위 목록 유형에 매핑하려면 작은 테이블이 필요하고, 최상의 하위 목록 헤더 매핑이 무엇인지 알 수 있도록 각 하위 목록 유형에 대한 발생 카운터가 필요합니다.
완전히 채워진 압축 목록의 최악의 경우 최소 표현은 모든 하위 목록 유형이 똑같이 인기가있을 때 발생합니다. 이 경우 3 개의 하위 목록 헤더마다 1 비트를 저장하므로 목록 크기는 2 * 781250 + 7 * 1000000-781250/3 = 8302083.3 비트입니다. 32 비트 워드 경계, 즉 8302112 비트 또는 1037764 바이트로 반올림합니다.
1M에서 TCP / IP 상태 및 버퍼의 2k를 뺀 값은 1022 * 1024 = 1046528 바이트이므로 8764 바이트를 사용할 수 있습니다.
그러나 하위 목록 헤더 매핑을 변경하는 프로세스는 어떻습니까? 아래 메모리 맵에서 "Z"는 임의의 오버 헤드, "="는 여유 공간, "X"는 압축 목록입니다.
ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
맨 왼쪽 "X"에서 읽기를 시작하고 맨 왼쪽 "="에서 쓰기를 시작하고 오른쪽으로 작업하십시오. 완료되면 압축 목록이 약간 짧아지고 잘못된 메모리 끝에있게됩니다.
ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======
따라서 오른쪽으로 분류해야합니다.
ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
헤더 매핑 변경 프로세스에서 하위 목록 헤더의 최대 1/3이 1 비트에서 2 비트로 변경됩니다. 최악의 경우이 모든 것이 목록의 선두에 있기 때문에 시작하기 전에 최소 781250/3 비트의 여유 저장 공간이 필요합니다. 그러면 이전 버전의 압축 목록의 메모리 요구 사항으로 돌아갑니다. (
이를 해결하기 위해 781250 하위 목록을 각각 78125 하위 목록의 10 개의 하위 목록 그룹으로 분할합니다. 각 그룹에는 자체 독립적 인 하위 목록 헤더 매핑이 있습니다. 그룹에 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
매핑 변경 중 하위 목록 그룹의 최악의 경우 임시 확장은 4k 미만인 78125/3 = 26042 비트입니다. 완전히 채워진 압축 목록에 대해 4k와 1037764 바이트를 허용하면 메모리 맵의 "Z"에 대해 8764-4096 = 4668 바이트가 남습니다.
10 개의 하위 목록 헤더 매핑 테이블, 30 개의 하위 목록 헤더 발생 횟수 및 필요한 기타 몇 개의 카운터, 포인터 및 작은 버퍼, 함수 호출 반환 주소를위한 스택 공간과 같이 눈치 채지 못한 채 사용한 공간에 충분합니다. 지역 변수.
파트 3, 실행하는 데 얼마나 걸립니까?
빈 압축 목록을 사용하면 1 비트 목록 헤더가 빈 하위 목록에 사용되며 목록의 시작 크기는 781250 비트가됩니다. 최악의 경우 목록은 추가 된 각 숫자에 대해 8 비트가 증가하므로 32 비트 숫자 각각을 목록 버퍼의 맨 위에 배치 한 다음 정렬하고 병합하려면 32 + 8 = 40 비트의 여유 공간이 필요합니다. 최악의 경우 하위 목록 헤더 매핑을 변경하면 공간 사용량이 2 * 781250 + 7 * entries-781250/3 비트가됩니다.
목록에 최소 800,000 개의 숫자가있는 경우 5 번째 병합 후 하위 목록 헤더 매핑을 변경하는 정책을 사용하면 최악의 경우 총 약 30M의 압축 목록 읽기 및 쓰기 작업이 포함됩니다.
출처:
http://nick.cleaton.net/ramsortsol.html
Gilmanov의 대답은 가정에서 매우 잘못되었습니다. 그것은 백만 개의 연속적인 정수 의 무의미한 척도로 추측을 시작합니다 . 이는 간격이 없음을 의미합니다. 이러한 임의의 간격은 작지만 실제로는 좋지 않습니다.
직접 시도해보십시오. 1 백만 개의 무작위 27 비트 정수를 가져 와서 정렬하고 , 원하는 LZMA에 관계없이 7-Zip , xz 로 압축 합니다. 결과는 1.5MB가 넘습니다. 전제는 연속 숫자의 압축입니다. 심지어 델타 인코딩 그입니다 이상 1.1 MB . 압축을 위해 100MB 이상의 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
나는 이것에 대해 생각하는 한 가지 방법은 조합 론적 관점에서 생각합니다. 정렬 된 숫자 순서의 가능한 조합이 몇 개일까요? 조합 0,0,0, ...., 0에 코드 0, 0,0,0, ..., 1 코드 1, 99999999, 99999999, ... 99999999 코드 N, N은 무엇입니까? 즉, 결과 공간은 얼마나 큽니까?
음, 이것에 대해 생각하는 한 가지 방법은 이것이 N x 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) Choose (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를 나타냅니다.
0에서 2.27 * 10 ^ 2436455까지의 모든 숫자를 저장하려면 lg2 (2.27 * 10 ^ 2436455) = 8.0937 * 10 ^ 6 비트가 필요합니다.
1 메가 바이트 = 8388608 비트> 8093700 비트
따라서 적어도 실제로 결과를 저장할 충분한 공간이있는 것 같습니다! 당연히 흥미로운 부분은 숫자가 들어 오면서 정렬을하는 것입니다. 이것에 대한 최선의 접근 방식이 우리에게 남아있는 294908 비트가 주어진다는 것은 확실하지 않습니다. 흥미로운 기술은 각 지점에서 이것이 전체 주문이라고 가정하고 해당 주문에 대한 코드를 찾은 다음 이전 코드로 돌아가서 새 번호를 수신하면되는 것입니다. 손 파 손 파입니다.
여기서 내 제안은 Dan의 솔루션에 많은 빚을지고 있습니다.
먼저 솔루션이 가능한 모든 입력 목록을 처리해야한다고 가정 합니다. 나는 대중적인 답변이 이러한 가정을하지 않는다고 생각합니다 (IMO는 큰 실수입니다).
어떤 형태의 무손실 압축도 모든 입력의 크기를 줄이는 것으로 알려져 있습니다.
모든 인기있는 답변은 추가 공간을 허용 할만큼 효과적으로 압축을 적용 할 수 있다고 가정합니다. 사실, 부분적으로 완성 된 목록의 일부를 압축되지 않은 형식으로 보관하고 정렬 작업을 수행 할 수있을만큼 충분한 추가 공간 청크입니다. 이것은 잘못된 가정입니다.
이러한 솔루션의 경우 압축을 수행하는 방법에 대한 지식이있는 사람은이 체계에 대해 잘 압축되지 않는 일부 입력 데이터를 설계 할 수 있으며 "솔루션"은 공간 부족으로 인해 중단 될 가능성이 큽니다.
대신 나는 수학적 접근 방식을 취합니다. 가능한 출력은 0..MAX 범위의 요소로 구성된 LEN 길이 목록입니다. 여기서 LEN은 1,000,000이고 MAX는 100,000,000입니다.
임의의 LEN 및 MAX의 경우이 상태를 인코딩하는 데 필요한 비트 양은 다음과 같습니다.
Log2 (MAX 다중 선택 LEN)
따라서 숫자의 경우 수신 및 정렬이 완료되면 가능한 모든 출력을 고유하게 구별 할 수있는 방식으로 결과를 저장하려면 최소한 Log2 (100,000,000 MC 1,000,000) 비트가 필요합니다.
이것은 ~ = 988kb 입니다. 그래서 우리는 결과를 담을 충분한 공간이 있습니다. 이 관점에서 가능합니다.
[더 나은 예제가 존재하므로 이제 무의미한 울림을 삭제했습니다 ...]
최고의 답변 은 여기에 있습니다 .
또 다른 좋은 대답 은 여기 에 기본적으로 삽입 정렬을 하나의 요소로 목록을 확장하는 기능으로 사용합니다 (몇 가지 요소와 사전 정렬을 버퍼링하여 한 번에 둘 이상의 삽입을 허용하고 시간을 절약합니다). 7 비트 델타의 버킷 인 멋진 압축 상태 인코딩도 사용합니다.
이 작업이 가능하다고 가정합니다. 출력 직전에 백만 개의 정렬 된 숫자가 메모리에 표시됩니다. 그러한 표현이 얼마나 많이 있습니까? 반복되는 숫자가있을 수 있으므로 nCr (선택)을 사용할 수 없지만 multiset에서 작동하는 multichoose라는 작업이 있습니다 .
- 있다 2.2e2436455 범위 0..99,999,999에 만 개 번호를 선택하는 방법.
- 가능한 모든 조합을 나타내 려면 8,093,730 비트 또는 1,011,717 바이트가 필요합니다.
따라서 이론적으로는 정렬 된 숫자 목록의 정상 (충분한) 표현을 생각 해낼 수 있다면 가능할 수 있습니다. 예를 들어, 미친 표현에는 10MB 조회 테이블 또는 수천 줄의 코드가 필요할 수 있습니다.
그러나 "1M RAM"이 100 만 바이트를 의미한다면 분명히 충분한 공간이없는 것입니다. 5 % 더 많은 메모리가 이론적으로 가능하다는 사실은 표현이 매우 효율적이어야하고 아마도 정상적이지 않아야한다는 것을 나에게 시사합니다.
(내 원래 대답은 잘못되었습니다. 수학이 잘못되어 죄송합니다. 휴식 시간 아래를 참조하십시오.)
이것은 어떤가요?
처음 27 비트는 사용자가 본 가장 낮은 숫자를 저장 한 다음, 다음 숫자와의 차이를 다음과 같이 인코딩하여 저장합니다. 차이를 저장하는 데 사용되는 비트 수를 저장하는 5 비트, 그 다음 차이를 저장합니다. 00000을 사용하여 해당 번호를 다시 봤음을 나타냅니다.
이것은 더 많은 숫자가 삽입 될수록 숫자 간의 평균 차이가 줄어들 기 때문에 더 많은 숫자를 추가 할 때 차이를 저장하는 데 더 적은 비트를 사용하기 때문에 작동합니다. 나는 이것이 델타 목록이라고 믿는다.
내가 생각할 수있는 최악의 경우는 모든 숫자가 균등 한 간격 (100 씩)입니다. 예를 들어 0이 첫 번째 숫자라고 가정합니다.
000000000000000000000000000 00111 1100100
^^^^^^^^^^^^^
a million times
27 + 1,000,000 * (5+7) bits = ~ 427k
Reddit을 구출하세요!
정렬 만했다면이 문제는 쉬울 것입니다. 본 숫자를 저장하려면 122k (1 백만 비트)가 필요합니다 (0이 표시되면 0 번째 비트가 표시되고 2300이 표시되면 2300 번째 비트가 표시되는 등).
숫자를 읽고 비트 필드에 저장 한 다음 카운트를 유지하면서 비트를 이동합니다.
그러나 얼마나 많은 것을 보았는지 기억해야합니다. 나는 위의 하위 목록 답변에서 영감을 얻어이 계획을 제시했습니다.
1 비트를 사용하는 대신 2 비트 또는 27 비트를 사용하십시오.
- 00은 번호를 보지 못했음을 의미합니다.
- 01은 한 번 본 것을 의미합니다.
- 1은 당신이 그것을 본 것을 의미하고 다음 26 비트는 몇 번의 횟수입니다.
나는 이것이 효과가 있다고 생각합니다. 중복이 없으면 244k 목록이 있습니다. 최악의 경우 각 숫자가 두 번 표시됩니다 (한 숫자가 세 번 표시되면 나머지 목록이 줄어 듭니다). 즉, 50,000 개를 두 번 이상 보았고 950,000 개의 항목을 0 번 또는 한 번 확인했음을 의미합니다.
50,000 * 27 + 950,000 * 2 = 396.7k.
다음 인코딩을 사용하면 추가로 개선 할 수 있습니다.
0은 숫자를 보지 못했음을 의미합니다. 10은 한 번 본 것을 의미합니다.
평균적으로 280.7k의 스토리지가 생성됩니다.
편집 : 일요일 아침 수학이 잘못되었습니다.
최악의 경우 500,000 개의 숫자가 두 번 표시되므로 수학은 다음과 같습니다.
500,000 * 27 + 500,000 * 2 = 1.77M
대체 인코딩은 평균 저장
500,000 * 27 + 500,000 = 1.70M
: (
가능한 모든 입력에 대해이 문제에 대한 하나의 해결책이 있습니다. 사기.
- TCP를 통해 m 값을 읽습니다. 여기서 m은 메모리에서 정렬 할 수있는 최대 값 (n / 4)에 가깝습니다.
- 250,000 개 (또는 그 이상)의 숫자를 정렬하고 출력합니다.
- 다른 3 분기에 대해 반복합니다.
- 수신자가 수신 한 4 개의 번호 목록을 처리하면서 병합하도록합니다. (단일 목록을 사용하는 것보다 훨씬 느리지 않습니다.)
나는 기수 나무를 시도 할 것 입니다. 데이터를 트리에 저장할 수 있다면 순서대로 트래버스를 수행하여 데이터를 전송할 수 있습니다.
이것을 1MB에 넣을 수 있을지 모르겠지만 시도해 볼 가치가 있다고 생각합니다.
어떤 종류의 컴퓨터를 사용하고 있습니까? 다른 "정상적인"로컬 스토리지는 없지만 비디오 RAM이 있습니까? 1 메가 픽셀 x 픽셀 당 32 비트 (예 :)는 필요한 데이터 입력 크기에 매우 가깝습니다.
(저는 해상도가 낮거나 색 심도가 낮은 화면 모드를 선택한 경우 사용 가능한 시스템 RAM을 확장하기 위해 VRAM을 '빌려줄'수 있는 오래된 Acorn RISC PC 를 기억 합니다.) 이것은 정상적인 RAM이 몇 MB 밖에없는 컴퓨터에서 유용했습니다.
기수 트리가 "접두사 압축"을 이용하기 때문에 기수 트리 표현이이 문제를 처리하는 데 가깝습니다. 그러나 1 바이트에서 단일 노드를 나타낼 수있는 기수 트리 표현을 생각하기는 어렵습니다. 2 개는 아마도 한계에 관한 것입니다.
그러나 데이터가 표시되는 방식에 관계없이 일단 정렬되면 접두사 압축 형식으로 저장할 수 있습니다. 여기서 숫자 10, 11 및 12는 001b, 001b, 001b로 표시되며 1의 증분을 나타냅니다. 이전 번호에서. 아마도 10101b는 5의 증분, 1101001b는 9의 증분 등을 나타냅니다.
10 ^ 8 범위에는 10 ^ 6 개의 값이 있으므로 평균적으로 100 개의 코드 포인트 당 하나의 값이 있습니다. N 번째 지점에서 (N + 1) 번째 지점까지의 거리를 저장합니다. 중복 값의 스킵은 0입니다. 이는 스킵이 저장하는 데 평균 7 비트 미만이 필요하다는 것을 의미하므로 그중 백만 개가 800 만 비트 스토리지에 만족할 것입니다.
이러한 스킵은 Huffman 인코딩과 같이 비트 스트림으로 인코딩되어야합니다. 삽입은 비트 스트림을 반복하고 새 값 다음에 다시 작성하는 것입니다. 묵시적인 값을 반복하고 기록하여 출력합니다. 실용성을 위해 아마도 각각 10 ^ 4 개의 코드 포인트 (및 평균 100 개의 값)를 포함하는 10 ^ 4 목록으로 수행되기를 원할 것입니다.
무작위 데이터에 대한 좋은 Huffman 트리는 건너 뛰기 길이에 대한 Poisson 분포 (평균 = 분산 = 100)를 가정하여 선험적으로 구축 할 수 있지만 실제 통계는 입력에 보관하고 처리 할 최적의 트리를 생성하는 데 사용할 수 있습니다. 병리학 적 사례.
RAM이 1M이고 다른 로컬 저장소가없는 컴퓨터가 있습니다.
속이는 또 다른 방법 : 로컬이 아닌 (네트워크로 연결된) 스토리지를 대신 사용하고 (질문이이를 배제하지 않음) 간단한 디스크 기반 병합 정렬 (또는 메모리 내 정렬에 충분한 RAM 만 사용할 수있는 네트워크 서비스)을 호출 할 수 있습니다. 이미 제공된 (매우 독창적 인) 솔루션 없이도 1M 번호 만 허용하면됩니다.
이것은 속임수 일 수 있지만 실제 문제에 대한 해결책을 찾고 있는지 아니면 규칙을 변경하도록 유도하는 퍼즐을 찾고 있는지 확실하지 않습니다. 후자의 경우 단순한 치트가 복잡한 것보다 더 나은 결과를 얻을 수 있습니다. 그러나 "진짜"솔루션 (다른 사람들이 지적했듯이 압축 가능한 입력에 대해서만 작동 할 수 있음).
해결책은 비디오 인코딩 기술, 즉 이산 코사인 변환을 결합하는 것이라고 생각합니다. 디지털 비디오에서는 110112115116과 같은 일반 값으로 비디오의 밝기 또는 색상 변경을 기록하는 대신 마지막 값에서 각각을 뺍니다 (런 길이 인코딩과 유사). 110 112 115 116은 110 2 3 1이됩니다. 값 2 3 1은 원본보다 적은 비트를 필요로합니다.
따라서 소켓에 도착할 때 입력 값 목록을 생성한다고 가정 해 보겠습니다. 우리는 값이 아닌 각 요소에 저장하고 있으며 그 이전 요소의 오프셋을 저장합니다. 이동하면서 정렬하므로 오프셋은 양수일뿐입니다. 그러나 오프셋은 3 바이트에 맞는 8 자리 십진수가 될 수 있습니다. 각 요소는 3 바이트가 될 수 없으므로이를 포장해야합니다. 다음 바이트가 숫자의 일부이고 각 바이트의 하위 7 비트를 결합해야 함을 나타내는 "연속 비트"로 각 바이트의 맨 위 비트를 사용할 수 있습니다. 0은 중복에 유효합니다.
목록이 가득 차면 숫자가 서로 가까워 져야합니다. 즉, 다음 값까지의 거리를 결정하는 데 평균 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);
}
}
우리는 모든 숫자를 얻기 전에 정렬 된 순서로 숫자를 보내기 위해 네트워킹 스택을 가지고 놀 수 있습니다. 1M의 데이터를 보내면 TCP / IP는 데이터를 1500 바이트 패킷으로 나누어 대상으로 스트리밍합니다. 각 패킷에는 시퀀스 번호가 부여됩니다.
우리는 이것을 손으로 할 수 있습니다. RAM을 채우기 직전에 우리가 가진 것을 정렬하고 목록을 대상으로 보낼 수 있지만 각 번호 주위에 시퀀스에 구멍을 남깁니다. 그런 다음 시퀀스의 구멍을 사용하여 동일한 방식으로 숫자의 2nd 1/2을 처리합니다.
맨 끝에있는 네트워킹 스택은 결과 데이터 스트림을 응용 프로그램에 전달하기 전에 순서대로 조합합니다.
병합 정렬을 수행하기 위해 네트워크를 사용하고 있습니다. 이것은 전체 해킹이지만 이전에 나열된 다른 네트워킹 해킹에서 영감을 얻었습니다.
HN 스레드에서 Google 의 (나쁜) 접근 방식. RLE 스타일 카운트를 저장합니다.
초기 데이터 구조는 '99999999 : 0'(모두 0, 숫자가 표시되지 않음)이고 숫자 3,866,344를 볼 수 있으므로 데이터 구조는 '3866343 : 0,1 : 1,96133654 : 0'이됩니다. 숫자가 항상 0 비트 수와 '1'비트 수를 번갈아 표시하므로 홀수는 0 비트를 나타내고 짝수는 1 비트를 나타낸다고 가정 할 수 있습니다. 이것은 (3866343,1,96133654)가됩니다
그들의 문제는 중복을 다루지 않는 것 같지만 중복에 "0 : 1"을 사용한다고 가정 해 봅시다.
큰 문제 # 1 : 1M 정수에 대한 삽입은 오랜 시간이 걸립니다 .
큰 문제 # 2 : 모든 일반 델타 인코딩 솔루션과 마찬가지로 일부 배포판은이 방법으로 다룰 수 없습니다. 예를 들어, 거리가 0:99 인 1m 정수 (예 : 각각 +99). 이제 동일하지만 0:99 범위 에서 임의의 거리 로 생각하십시오 . (참고 : 99999999/1000000 = 99.99)
Google의 접근 방식은 가치가없고 (느리고) 부정확합니다. 그러나 그들의 방어에있어서 그들의 문제는 약간 다를 수 있습니다.
정렬 된 배열을 나타 내기 위해 첫 번째 요소와 인접한 요소 간의 차이를 저장할 수 있습니다. 이런 식으로 우리는 최대 10 ^ 8까지 합할 수있는 10 ^ 6 요소를 인코딩하는 데 관심이 있습니다. 이것을 D 라고합시다 . D 의 요소를 인코딩하려면 Huffman 코드를 사용할 수 있습니다 . Huffman 코드의 사전은 이동 중에 생성 할 수 있으며 정렬 된 배열에 새 항목이 삽입 될 때마다 배열이 업데이트됩니다 (삽입 정렬). 새 항목으로 인해 사전이 변경되면 새 인코딩과 일치하도록 전체 배열을 업데이트해야합니다.
D의 각 요소를 인코딩하기위한 평균 비트 수는 각 고유 요소의 수가 같으면 최대화됩니다. D의 요소 d1 , d2 , ..., dN 이 각각 F 번 나타납니다 . 이 경우 (최악의 경우 입력 시퀀스에 0과 10 ^ 8이 모두 있음)
SUM (1 <= I <= N ) F . di = 10 ^ 8
어디
sum (1 <= i <= N ) F = 10 ^ 6 또는 F = 10 ^ 6 / N 이고 정규화 된 주파수는 p = F / 10 ^ = 1 / N입니다.
평균 비트 수는 -log2 (1 / P ) = log2 ( N )입니다. 이러한 상황에서 우리는 N 을 최대화하는 케이스를 찾아야합니다 . 이것은 0에서 시작 하는 di에 대한 연속적인 숫자가 있거나 di = i -1이므로 발생합니다.
10 ^ 8 = SUM (1 <= I <= N ) F . di = sum (1 <= i <= N ) (10 ^ 6 / N ) (i-1) = (10 ^ 6 / N ) N ( N -1) / 2
즉
N <= 201.이 경우 평균 비트 수는 log2 (201) = 7.6511입니다. 즉, 정렬 된 배열을 저장하려면 입력 요소 당 약 1 바이트가 필요합니다. 이것은 일반적으로 D 가 201 개 이상의 요소를 가질 수 없다는 것을 의미하지는 않습니다 . D의 요소 가 균등하게 분포되어 있으면 고유 값이 201 개를 넘을 수 없습니다.
TCP의 재전송 동작을 이용합니다.
- TCP 구성 요소가 큰 수신 창을 만들도록합니다.
- ACK를 보내지 않고 일정량의 패킷을받습니다.
- 패스에서 처리하여 일부 (접두사) 압축 데이터 구조 생성
- 더 이상 필요하지 않은 마지막 패킷에 대해 중복 확인 전송 / 재전송 시간 초과 대기
- 고토 2
- 모든 패킷이 수락되었습니다.
이것은 버킷 또는 다중 패스의 이점을 가정합니다.
아마도 배치 / 버킷을 정렬하고 병합하는 것입니다. -> 기수 나무
이 기술을 사용하여 처음 80 %를 수락하고 정렬 한 다음 마지막 20 %를 읽고 마지막 20 %에 가장 낮은 숫자의 처음 20 %에 해당하는 숫자가 없는지 확인합니다. 그런 다음 20 % 가장 낮은 숫자를 보내고 메모리에서 제거하고 새 숫자의 나머지 20 %를 수락하고 병합합니다. **
입력 스트림이 몇 번 수신 될 수 있다면 훨씬 쉬울 것입니다 (아이디어 및 시간 성능 문제에 대한 정보 없음).
그런 다음 소수 값을 셀 수 있습니다. 계산 된 값을 사용하면 출력 스트림을 쉽게 만들 수 있습니다. 값을 세어 압축하십시오. 입력 스트림의 내용에 따라 다릅니다.
입력 스트림이 몇 번 수신 될 수 있다면 훨씬 쉬울 것입니다 (아이디어 및 시간 성능 문제에 대한 정보 없음). 그런 다음 소수 값을 셀 수 있습니다. 계산 된 값을 사용하면 출력 스트림을 쉽게 만들 수 있습니다. 값을 세어 압축하십시오. 입력 스트림의 내용에 따라 다릅니다.
여기서 정렬은 두 번째 문제입니다. 다른 사람들이 말했듯이 정수를 저장하는 것은 어렵고 숫자 당 27 비트가 필요하기 때문에 모든 입력 에서 작동 할 수 없습니다 .
내 생각은 다음과 같습니다. 연속 된 (정렬 된) 정수 사이의 차이 만 저장하십시오. 그런 다음 입력 번호 당 2 개의 추가 비트가있는 압축 방식을 사용하여 번호가 저장되는 비트 수를 인코딩합니다. 다음과 같은 것 :
00 -> 5 bits
01 -> 11 bits
10 -> 19 bits
11 -> 27 bits
주어진 메모리 제약 내에서 가능한 많은 입력 목록을 저장할 수 있어야합니다. 최대 입력 수에서 작동하도록 압축 방식을 선택하는 방법에 대한 수학은 저를 넘어선 것입니다.
이를 기반으로 충분한 정수 압축 체계 를 찾기 위해 입력 에 대한 도메인 별 지식 을 활용할 수 있기를 바랍니다 .
그런 다음 데이터를 수신 할 때 정렬 된 목록에서 삽입 정렬을 수행합니다.
이제 실제 솔루션을 목표로하고 있으며, 1MB의 RAM만으로 8 자리 범위의 모든 가능한 입력 사례를 다룹니다. 참고 : 진행중인 작업, 내일 계속됩니다. 정렬 된 정수의 델타에 대한 산술 코딩을 사용하면 정렬 된 정수 1M의 최악의 경우 항목 당 약 7 비트 비용이 발생합니다 (99999999/1000000은 99이고 log2 (99)는 거의 7 비트이므로).
그러나 7 비트 또는 8 비트가되도록 정렬 된 1m 정수가 필요합니다! 짧은 시리즈는 더 큰 델타를 가지므로 요소 당 더 많은 비트를 갖게됩니다.
나는 가능한 한 많은 것을 가져다가 (거의) 제자리에서 압축하기 위해 노력하고 있습니다. 250K에 가까운 int의 첫 번째 배치에는 기껏해야 각각 약 9 비트가 필요합니다. 따라서 결과는 약 275KB가 소요됩니다. 남은 여유 메모리로 몇 번 반복하십시오. 그런 다음 압축 된 청크를 decompress-merge-in-place-compress. 이것은 매우 어렵지만 가능합니다. 나는 생각한다.
병합 된 목록은 정수 대상 당 7 비트에 점점 더 가까워집니다. 그러나 병합 루프를 몇 번 반복할지 모르겠습니다. 아마도 3.
그러나 산술 코딩 구현이 부정확하면 불가능할 수 있습니다. 이 문제가 가능하다면 극도로 빡빡 할 것입니다.
자원 봉사자?
숫자 간의 차이를 순서대로 저장하고 인코딩을 사용하여 이러한 순서 번호를 압축하면됩니다. 2 ^ 23 비트가 있습니다. 우리는 그것을 6 비트 청크로 나누고, 마지막 비트는 숫자가 또 다른 6 비트 (5 비트 + 청크 확장)로 확장되는지 여부를 나타냅니다.
따라서 000010은 1이고 000100은 2입니다. 000001100000은 128입니다. 이제 우리는 10,000,000까지의 숫자 순서 차이를 나타내는 최악의 캐스트를 고려합니다. 2 ^ 5보다 큰 10,000,000 / 2 ^ 5 차이, 2 ^ 10보다 큰 10,000,000 / 2 ^ 10 차이, 2 ^ 15보다 큰 10,000,000 / 2 ^ 15 차이 등이있을 수 있습니다.
그래서 우리는 시퀀스를 표현하는 데 필요한 비트 수를 추가합니다. 1,000,000 * 6 + roundup (10,000,000 / 2 ^ 5) * 6 + roundup (10,000,000 / 2 ^ 10) * 6 + roundup (10,000,000 / 2 ^ 15) * 6 + roundup (10,000,000 / 2 ^ 20) * 4 = 7935479.
2 ^ 24 = 8388608. 8388608> 7935479이므로 쉽게 충분한 메모리가 있어야합니다. 새 숫자를 삽입 할 때 위치의 합계를 저장하기 위해 약간의 메모리가 필요할 것입니다. 그런 다음 시퀀스를 살펴보고 새 번호를 삽입 할 위치를 찾고 필요한 경우 다음 차이를 줄인 다음 모든 것을 오른쪽으로 이동합니다.
이 숫자에 대해 아무것도 모르는 경우 다음 제약 조건에 의해 제한됩니다.
- 정렬하기 전에 모든 숫자를로드해야합니다.
- 숫자 세트는 압축 할 수 없습니다.
이러한 가정이 유지되면 최소 26,575,425 비트의 스토리지 (3,321,929 바이트)가 필요하므로 작업을 수행 할 방법이 없습니다.
귀하의 데이터에 대해 무엇을 알려줄 수 있습니까?
트릭은 "increment counter"= "+"및 "output counter"= "!"의 압축 스트림으로 정수 다중 집합 인 알고리즘 상태를 나타내는 것입니다. 문자. 예를 들어, {0,3,3,4} 집합은 "! +++ !! +!"로 표시되고 그 뒤에 임의의 수의 "+"문자가옵니다. 다중 세트를 수정하려면 문자를 스트리밍하고 한 번에 일정한 양만 압축 해제 한 다음 압축 된 형태로 다시 스트리밍하기 전에 제자리에 변경합니다.
세부
최종 세트에는 정확히 10 ^ 6 개의 숫자가 있으므로 최대 10 ^ 6 "!" 문자. 또한 범위의 크기가 10 ^ 8이라는 것을 알고 있습니다. 즉, 최대 10 ^ 8 "+"문자가 있음을 의미합니다. 10 ^ 8 개의 "+"사이에 10 ^ 6 개의 "!"를 배열 할 수있는 방법의 수는입니다. (10^8 + 10^6) choose 10^6따라서 특정 배열을 지정하는 데는 ~ 0.965 MiB` 의 데이터가 필요합니다. 딱 맞을거야.
할당량을 초과하지 않고 각 캐릭터를 독립적으로 취급 할 수 있습니다. "!"보다 "+"문자가 정확히 100 배 더 많습니다. 이 문자는 종속적이라는 사실을 잊으면 각 문자가 "+"가 될 확률을 100 : 1로 단순화합니다. 100 : 101의 확률은 문자 당 ~ 0.08 비트에 해당 하며 거의 동일한 총 ~ 0.965MiB입니다 ( 이 경우 종속성을 무시하면 비용이 ~ 12 비트 에 불과합니다 !).
알려진 사전 확률로 독립 문자를 저장하는 가장 간단한 기술은 Huffman 코딩 입니다. 비실용적으로 큰 트리가 필요합니다 (10 자 블록에 대한 허프만 트리의 블록 당 평균 비용은 약 2.4 비트이며 총 ~ 2.9Mib입니다. 20 자 블록에 대한 허프만 트리에는 블록 당 평균 비용이 있습니다. 약 3 비트, 총 1.8MiB입니다. 우리는 아마도 100 개 정도의 크기 블록이 필요할 것입니다. 이는 지금까지 존재했던 모든 컴퓨터 장비가 저장할 수있는 것보다 더 많은 노드를 우리 트리에 의미한다는 것을 의미합니다. ). 그러나 ROM은 문제에 따라 기술적으로 "무료"이며 트리의 규칙 성을 활용하는 실제 솔루션은 본질적으로 동일하게 보입니다.
의사 코드
- ROM에 충분히 큰 허프만 트리 (또는 유사한 블록 별 압축 데이터)가 저장되어 있습니다.
- 10 ^ 8 "+"문자의 압축 된 문자열로 시작하십시오.
- 숫자 N을 삽입하려면 N "+"문자가 지나갈 때까지 압축 된 문자열을 스트리밍 한 다음 "!"를 삽입합니다. 오버 / 언더 실행을 방지하기 위해 일정한 양의 버퍼링 된 블록을 유지하면서 재 압축 된 문자열을 이전 문자열 위로 다시 스트리밍합니다.
- 100 만 번 반복 : [입력, 스트림 압축 해제> 삽입> 압축], 출력을 위해 압축 해제
1MB-3KB 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
기타
이 숫자 표현은 자체 길이를 설명하므로 다음 간격 번호가 시작되는시기를 알 수 있습니다.
127 미만의 작은 간격으로도 여전히 7000027 비트가 필요합니다.
최대 (10 ^ 8) / (2 ^ 7) = 781250 23 비트 간격 번호가있을 수 있으며, 너무 많은 추가 16 * 781,250 = 12,500,000 비트가 필요합니다. 우리는 더 간결하고 천천히 증가하는 간격 표현이 필요합니다.
평균 간격 크기는 100이므로 [100, 99, 101, 98, 102, ..., 2, 198, 1, 199, 0, 200, 201, 202, ...]로 다시 정렬하고이를 인덱싱하면 0 쌍이없는 고밀도 이진 피보나치 기본 인코딩 (예 : 11011 = 8 + 5 + 2 + 1 = 16)을 사용하여 숫자를 '00'으로 구분하면 간격 표현을 충분히 짧게 유지할 수 있다고 생각하지만 필요합니다. 더 많은 분석.
스트림을 수신하는 동안 다음 단계를 수행하십시오.
첫 번째는 적당한 청크 크기를 설정합니다.
의사 코드 아이디어 :
- 첫 번째 단계는 모든 중복을 찾아서 그 개수와 함께 사전에 붙여서 제거하는 것입니다.
- 세 번째 단계는 알고리즘 단계의 순서대로 존재하는 숫자를 배치하고 n, n + 1 ..., n + 2, 2n, 2n + 1과 같은 첫 번째 숫자와 단계가있는 카운터 특수 사전에 배치하는 것입니다. 2n + 2 ...
- 1000 개마다 또는 10000 개마다 반복되는 빈도가 낮은 나머지 숫자와 같은 합리적인 범위의 숫자를 덩어리 단위로 압축하기 시작합니다.
- 숫자가 발견되면 해당 범위의 압축을 풀고 범위에 추가하고 잠시 동안 압축되지 않은 상태로 둡니다.
- 그렇지 않으면 그 숫자를 byte [chunkSize]에 추가하십시오.
스트림을 수신하는 동안 처음 4 단계를 계속합니다. 마지막 단계는 메모리를 초과하면 실패하거나 모든 데이터가 수집되면 결과를 출력하기 시작하는 것입니다. 범위를 정렬하고 결과를 순서대로 뱉어 낸 다음 압축을 풀어야하는 순서대로 압축을 풀고 다음과 같은 경우에 정렬합니다. 당신은 그들에게 도달합니다.
ROM 크기가 중요하지 않으므로 TCP 버퍼 외에 추가 RAM이 필요하지 않습니다. 큰 유한 상태 기계를 구현하십시오. 각 상태는 읽은 숫자의 여러 세트를 나타냅니다. 백만 개의 숫자를 읽은 후 도달 된 상태에 해당하는 숫자를 인쇄하면됩니다.
참고 URL : https://stackoverflow.com/questions/12748246/sorting-1-million-8-digit-numbers-in-1-mb-of-ram
'developer tip' 카테고리의 다른 글
| 프로젝트 오일러와 속도 비교 : C vs Python vs Erlang vs Haskell (0) | 2020.10.02 |
|---|---|
| 지도에 Go의 키가 포함되어 있는지 확인하는 방법은 무엇입니까? (0) | 2020.10.02 |
| Interop 유형은 삽입 할 수 없습니다. (0) | 2020.10.02 |
| Swift에서 문자열을 배열로 분할 하시겠습니까? (0) | 2020.10.02 |
| @selector () in Swift? (0) | 2020.10.02 |