9

非常に大きな (50 GB 以上) ASCII テキスト ファイルのインデックスを作成する必要があります。これにより、ファイルへの高速ランダム読み取りアクセスを提供できます (n 行目を取得し、n 行目に n 番目の単語を取得します)。List<List<long>> mapここで、要素はmap[i][j]ファイル内の i 行目の j 番目の単語の位置です。

インデックスを順番に作成します。つまり、ファイル全体を読み取り、インデックスにmap.Add(new List<long>())(新しい行) とmap[i].Add(position)(新しい単語) を入力します。次に、特定の単語位置を で取得しますmap[i][j]。

私が目にする唯一の問題は、行/単語の合計数を予測できないことです。そのため、List再割り当てのたびに O(n) にぶつかり、これを回避する方法がわかりません。

タスク用に選択したデータ構造に他に問題はありますか? どの構造がより良いでしょうか？

UPD : ファイルはランタイム中に変更されません。私がリストしたもの以外にコンテンツを取得する方法はありません。

4

1 に答える 1

6
  1. 大きなリストのサイズを大きくすると、非常にコストのかかる操作になります。そのため、最初にリスト サイズを確保しておくことをお勧めします。
  2. 2つのリストを使用することをお勧めします。1 つ目はファイル内の単語のインデックスを含み、2 つ目は最初のリストのインデックス (適切な行の最初の単語のインデックス) を含みます。
  3. 使用可能なすべての RAM を超える可能性が非常に高くなります。また、システムが GC 管理 RAM のページイン/ページアウトを開始すると、プログラムのパフォーマンスが完全に低下します。マネージド メモリではなく、メモリ マップト ファイルにデータを格納することをお勧めします。http://msdn.microsoft.com/en-us/library/dd997372.aspx

UPD メモリ マップ ファイルは、RAM に収まらない大量のデータを処理する必要がある場合に効果的です。基本的に、インデックスが使用可能な RAM よりも大きくなった場合は、これが唯一の選択肢です。

于 2013-03-17T07:55:12.143 に答える