1MB RAM으로 1백만 개의 8 진수 숫자 정렬

질문 : 1MB RAM으로 1 백만 개의 8 진수 숫자 정렬

---

1MB의 RAM이 있고 다른 로컬 저장소가없는 컴퓨터가 있습니다. TCP 연결을 통해 1 백만 개의 8 자리 십진수를 받아들이고 정렬 한 다음 다른 TCP 연결을 통해 정렬 된 목록을 보내야합니다.

번호 목록에는 중복이 포함될 수 있으므로 삭제해서는 안됩니다. 코드는 ROM에 배치되므로 1MB에서 코드 크기를 뺄 필요가 없습니다. 이미 이더넷 포트를 구동하고 TCP / IP 연결을 처리하는 코드가 있으며, 상태 데이터에 2KB가 필요합니다. 여기에는 코드가 데이터를 읽고 쓰는 데 사용하는 1KB 버퍼가 포함됩니다. 이 문제에 대한 해결책이 있습니까?

질문 및 답변 출처 :

slashdot.org

cleaton.net

답변

---

지금까지 여기에 언급되지 않은 다소 교활한 속임수가 있습니다. 데이터를 저장할 수있는 추가 방법이 없다고 가정하지만 이는 엄격히 사실이 아닙니다.

문제를 해결하는 한 가지 방법은 다음과 같은 끔찍한 작업을 수행하는 것입니다. 어떤 상황에서도 누구도 시도해서는 안됩니다. 네트워크 트래픽을 사용하여 데이터를 저장합니다. 그리고 아니요, NAS를 의미하는 것이 아닙니다.

다음과 같은 방법으로 몇 바이트의 RAM만으로 숫자를 정렬 할 수 있습니다.

• COUNTER 및 VALUE 두 가지 변수를 사용합니다.
• 먼저 모든 레지스터를 0 설정합니다.
• I 를받을 때마다 COUNTER 증가시키고 VALUE 를 max(VALUE, I) .
• I 로 설정된 데이터와 함께 ICMP 에코 요청 패킷을 라우터에 보냅니다. I 지우고 반복하십시오.
• 반환 된 ICMP 패킷을받을 때마다 정수를 추출하여 다른 에코 요청으로 다시 보냅니다. 이로 인해 정수를 포함하는 앞뒤로 이동하는 엄청난 수의 ICMP 요청이 생성됩니다.

COUNTER 1000000 에 도달하면 모든 값이 ICMP 요청의 끊임없는 스트림에 저장되고 VALUE 에 최대 정수가 포함됩니다. threshold T >> 1000000 선택하십시오. COUNTER 를 0으로 설정하십시오. 당신은 ICMP 패킷 증가가 나타날 때마다 COUNTER 정수는이 포함 된 보내 I 하지 않는 한, 다른 에코 요청에서 다시 I=VALUE 이 경우 전송에 정렬 된 정수의 대상에. COUNTER=T VALUE 를 1 씩 감소 COUNTER 를 0으로 재설정하고 반복합니다. VALUE 가 0에 도달하면 모든 정수를 가장 큰 것부터 가장 작은 것까지 순서대로 전송해야하며 두 개의 영구 변수 (및 임시 값에 필요한 작은 양)에 대해 약 47 비트의 RAM 만 사용해야합니다.

나는 이것이 끔찍하다는 것을 알고 있으며 모든 종류의 실제적인 문제가있을 수 있다는 것을 알고 있지만, 나는 그것이 여러분 중 일부를 웃게하거나 적어도 여러분을 겁나게 할 것이라고 생각했습니다.

출처 : https://stackoverflow.com/questions/12748246/sorting-1-million-8-decimal-digit-numbers-with-1-mb-of-ram