3

最近のインタビューでこんな質問をされました。

入力ファイル、正規表現、および出力ファイルが与えられます。入力ファイルを読み取り、各行を正規表現に一致させ、一致する行を出力ファイルに書き込みます。

FileReader にチェーンされた BufferedReader を使用する大まかなスキームを思いつきました (ディスクからの読み取りを最適化するため)。書き込みにも同様のスキームを使用しました。

インタビュアーは、このプロセスがファイルから行を読み取るのに 3 秒、正規表現を行と比較するのに 1 秒、書き戻すのにさらに 5 秒かかると述べました。したがって、1 行あたり合計 9​​ 秒かかります。どうすればこれを改善できますか?

ファイル全体を一度に読み取り、処理し、出力ファイル全体を一度に書き込むことを提案しました。しかし、それは役に立たないと言われました（1行書く= 5秒、2行書く= 10秒）。

インタビュアーはさらに、これはハードウェア/ハード ドライブの制限によるものだと述べています。コードを改善して、1 行あたりの合計秒数 (現在は 9 秒) を短縮する方法を尋ねられました。

バッファリングされた読み取り/書き込みしか考えられず、SO についてもあまり見つけることができませんでした。何かご意見は ？

4

3 に答える 3

2

インタビュアーは、出力の書き込みと並行して読み取り/正規表現チェックを実行するソリューションを探していたと思います。読み取りとフィルタリングによって非同期的に埋めるワークキューを設定し、書き込みを別のスレッドに配置する場合、結合されたプロセスは2行目から1行あたり5秒かかります。

ここでの前提は、読み取り、解析、および書き込みが互いに独立して発生する可能性があるということです。この場合、1行目が書き込まれている間に2行目を読み取ることができます。正規表現を読み取って適用するのに必要な時間はわずか4秒で、ライターが2行目の準備ができるまでに5秒かかります。書き込みはボトルネックのままですが、プロセス全体が約44％高速化されますが、これは悪くありません。

于 2013-03-03T14:22:08.653 に答える
0

読み取り時間と書き込み時間が固定されているため、この場合の唯一のオプションは、正規表現ビットの性質を変更することです。

正規表現で実行できるすべての巧妙な作業のオーバーヘッドなしに、正規表現テストをすばやく適用するコードを記述できます。

一方、問題が各IO要求の実行に数秒かかることであるが、制限が実際のドライブではない場合は、複数のリーダーが同時に読み取るようにします。

于 2013-03-03T14:24:23.867 に答える
0

システムについてはあまり詳しくないので、難しい質問です。

私の推測では、スレッド/非同期処理を使用するでしょう。1つのスレッドを使用して読み取りを行い、1つのスレッドを使用して2つ以上の書き込みを処理することで、IO待機にかかる時間を短縮します。

これをASCIIチャートに変換してみましょう。

  • R / rは読み取りを意味します（3秒）
  • P / pは処理を意味します（1秒）
  • W / wは書き込みを意味します（5秒）

大文字は開始を示し、小文字は継続作業を示します。「：」はスレッドがアイドル状態であることを意味します

Thread 1: RrrRrrRrrRrrRr
Thread 2: ...P..P..P..P.
Thread 3: ....Wwwww
Thread 4: .......Wwwww

この設定では、最初のバッチは9秒後に書き戻されますが（ここではあまり行いません）、2番目のバッチは12秒後に完了します。シングルスレッド2番目のものは合計18秒必要です

于 2013-03-03T14:24:27.613 に答える