1 MB の RAM しかなく、他のローカル ストレージがないコンピューターがあります。TCP 接続を介して 100 万の 8 桁の 10 進数を受け取り、それらを並べ替え、並べ替えられたリストを別の TCP 接続を介して送信するために、このコンピューターを使用する必要があります。
数字のリストには重複が含まれている可能性がありますが、それを破棄してはいけません。コードは ROM に配置されるため、1 MB からコードのサイズを差し引く必要はありません。イーサネット ポートを駆動して TCP/IP 接続を処理するコードは既にありますが、コードがデータを読み書きする 1 KB のバッファーを含め、状態データ用に 2 KB が必要です。この問題の解決策はありますか?
質問と回答のソース:
ベストアンサー1
これまでここで触れられていない、かなり巧妙なトリックが 1 つあります。データを保存する追加の方法がないものと想定していますが、厳密にはそうではありません。
この問題を回避する方法の 1 つは、次のような恐ろしいことをすることです。これは、いかなる状況でも誰も試みるべきではありません。ネットワーク トラフィックを使用してデータを保存します。NAS のことではありません。
次のように、数バイトの RAM のみを使用して数値をソートできます。
- まず 2 つの変数を取ります:
COUNTERおよびVALUE。 - まずすべてのレジスタを
0;に設定します。 - 整数を受け取るたびに
I、を増分して にCOUNTER設定します。VALUEmax(VALUE, I) - 次に、データを設定した ICMP エコー要求パケットを
Iルーターに送信します。消去しIて繰り返します。 - 返された ICMP パケットを受信するたびに、整数を抽出し、別のエコー要求で再度送信するだけです。これにより、整数を含む大量の ICMP 要求が前後に飛び交うことになります。
COUNTERに達すると1000000、ICMP 要求の絶え間ないストリームに格納されたすべての値を取得し、VALUEに最大の整数が含まれるようになります。 をいくつか選択しますthreshold T >> 1000000。COUNTERをゼロに設定します。ICMP パケットを受信するたびに、でない限り、COUNTER含まれている整数を増分し、I別のエコー要求で送り返しますI=VALUE。 の場合は、それをソートされた整数の送信先に送信します。 になったら、をだけCOUNTER=T減分し、ゼロにリセットして、これを繰り返します。 がゼロに達すると、すべての整数が最大から最小の順に送信先に送信され、2 つの永続変数 (および一時的な値に必要な少量) に使用した RAM は約 47 ビットのみになります。VALUE1COUNTERVALUE
これはひどいことだし、実際的な問題がいろいろあるかもしれないこともわかっていますが、皆さんの中には笑ったり、少なくとも恐怖を感じたりする人もいるかもしれないと思いました。