5

私は最近のインタビューでこの問題に直面しました：

範囲内に着信番号のストリームがあり0 to 60000、その範囲から番号を取得し、その瞬間までのその番号の発生回数を返す関数があります。このシステムを実装するための適切なデータ構造/アルゴリズムを提供します。

私の解決策は次のとおりです。

ビットベクトルを指すサイズ60001の配列を作成します。これらのビットベクトルには、着信番号のカウントが含まれ、着信番号は、対応する番号の配列にインデックスを付けるためにも使用されます。ビットベクトルは、カウントが大きくなりすぎて保持できないため、動的に増加します。

したがって、その数が一定の割合で発生している場合、100numbers/sec100万年後には合計数は=になります(100*3600*24)*365*1000000 = 3.2*10^15。ストリーム内のすべての番号が同じである最悪の場合ceil((log(3.2*10^15) / log 2) )= 52bits、番号が均一に分散されている場合、番号(3.2*10^15) / 60001 = 5.33*10^10ごとに出現回数があり、番号ごとに合計が必要になり36 bitsます。したがって、4バイトのポインタ(60001 * 4)/1024 = 234 KBが配列用のメモリを必要とし、同じ番号の場合は、ビットベクトルサイズ=が必要です52/8 = 7.5 bytes。これはまだ約234KBです。また、他のケースでは、(60001 * 36 / 8)/1024 = 263.7 KB合計約500KBのビットベクトルが必要です。したがって、通常のPCとメモリを使用してこれを行うことは非常に実行可能です。

しかし、インタビュアーは、それは無限のストリームであるため、最終的にはオーバーフローし、PCが多数あり、それらの間でメッセージを渡したり、ファイルシステムなどについて考えることができる場合、どうすればこれを行うことができるかについてのヒントを私に与えました。しかし、私はこの解決策かどうかを考え続けましたその時は機能していませんでしたが、他の人も機能していました。言うまでもなく、私はその仕事に就けませんでした。

より少ないメモリでこの問題を解決するにはどうすればよいですか？別のアプローチを考えられますか（PCのネットワークを使用する場合があります）？

4

3 に答える 3

5

問題の正式なモデルは次のようになります。

いつでもすべてのカップルの言語L（数、これまでの出現数）を認識するような、一定の空間境界のチューリングマシンが存在するかどうかを知りたいと思います。これは、すべての正しいカップルが受け入れられ、すべての間違ったカップルが拒否されることを意味します。

Hopcroft-Ullmanの定理3.13の結果として、一定のスペース境界のあるマシンによって認識されるすべての言語が規則的であることを私たちは知っています。

上記の言語が正規言語ではないことは、正規言語のポンピング補題を使用することで証明できます。したがって、一定のスペースに制限されたマシンではそれを認識できません。

于 2012-07-29T13:36:53.047 に答える
0

int arr [60000] [1]のような配列を使用すると、インデックスベースの検索を簡単に使用できます。たとえば5000の数値を取得するたびに、index（num-1）=（5000-1）as、arr[に直接アクセスします。 num-1] [1]、そして数を増やします。これで、特定のnumが何回発生したかを知りたいときはいつでも、arr [num-1] [1]でアクセスでき、カウントを取得できます。その数については、その最も単純な線形時間の実装。

于 2012-07-30T11:31:52.743 に答える
-1

これは外部ソーティングではありませんか？無限ストリームをファイルに保存します。ファイルでseek（）（RandomAccessFile.seek()Javaの場合）を実行し、適切なタイムスタンプを取得します。データはタイムスタンプで並べ替えられるため、これはバイナリ検索に似ています。適切なタイムスタンプに到達すると、問題は無限の数のセットから特定の数を数えることになります。ここでは、メモリ内でクイックソートを実行する代わりに、数値の範囲が制限されているため、カウントソートを実行できます。

于 2012-07-29T16:17:58.480 に答える