6

ディスクには非常に大きなファイル (>10G) があり、ファイル内の各行は、次のように行番号と人名で構成されています。

1 Jane
2 Perk
3 Sime
4 Perk
.. ..

この大きなファイルを読み取って、各名前の頻度を見つけ、最終的に次のように各名前の頻度の降順で結果を出力する必要があります。

Perk 2
Jane 1
Sime 1

インタビュアーが要求したように、上記のジョブはできるだけ効率的に実行する必要があり、マルチスレッドが許可されています。そして私の解決策は次のようなものです：

  1. ファイルが大きすぎるため、ファイルをいくつかの小さなファイルに分割します。各小さなファイルは約です。各小さなファイルの開始点と終了点を見つけることができ100Mます。lseek(beg, end)

  2. これらの小さなファイルには、個人の名前をキーとして使用する共有ハッシュマップがあり、それが値として表示される回数があります。

  3. 小さなファイルごとに、単一のスレッドが通過します。スレッドが人の名前に遭遇するたびvalueに、共有ハッシュマップ内の対応する名前がインクリメントされます。

  4. すべてのスレッドが終了したら、フィールドに従ってハッシュマップをソートするときだと思いvalueます。

ただし、そのファイルには名前が多すぎる可能性があるため、並べ替えは遅くなります。名前を降順で出力する方法について、良いアイデアが思いつきませんでした。

誰かが上記の問題で私を助けてくれることを願っています。

4

5 に答える 5

7

map-reduceアプローチを使用することは、問題に対して良い考えかもしれません。このアプローチは、次の 2 つのステップで構成されます。

  1. Map : ファイルからデータのチャンクを読み取り、そのデータを処理するスレッドを作成します
  2. Reduce : メイン スレッドは、他のすべてのスレッドが終了するのを待ってから、個々のスレッドの結果を結合します。

このソリューションの利点は、各スレッドが異なるデータのチャンクで動作するため、スレッド間でロックする必要がないことです。あなたが提案しているように、共有データ構造を使用することも解決策になる可能性がありますが、ロックの競合によりオーバーヘッドが発生する可能性があります。

すべてのスレッドからのデータが利用可能な場合、reduce ステップでソート部分を実行する必要があります。しかし、reduce ステップで完全なソートをより簡単に (より迅速に) 完了するために、map ステップで何らかの作業を行いたい場合があります。

最後に順次並べ替えを避けたい場合は、カスタム データ構造を使用できます。名前をすばやく見つけるには、マップ (赤黒木やハッシュ テーブルなど) を使用します。さらに、名前間の頻度の順序を維持するためにヒープを使用します。もちろん、これらのデータ構造の並列バージョンが必要になります。並列化の粗さに応じて、ロック競合の問題が発生する場合と発生しない場合があります。

于 2012-07-19T10:18:51.210 に答える
6

「効率的に」という言葉を使用してインタビューの質問としてそれを尋ねた場合、「cut -f 2 -d ' ' < file | sort | uniq -c」のような答えを期待するでしょう。すでに問題を解決しました。実際、これは良い考えです。インタビューの質問にこのようなものを追加します。

ボトルネックはディスクになるため、あらゆる種類のマルチスレッドがソリューションを過度に設計しています（これは「効率」にも反します）。このように読み取りを分割すると、回転するディスクがある場合は処理が遅くなるか、少なくともバッファ キャッシュが混乱し、ドロップ ビハインド アルゴリズムが開始される可能性が低くなります。悪い考え、やらないでください。

于 2012-07-19T10:52:46.080 に答える
3

インタビュアーの元の質問には、「...そしてマルチスレッドが許可されています」と記載されています。この質問の言い回しは少し曖昧かもしれませんが、質問の趣旨は明らかです。面接担当者は候補者に、問題を解決するためのプログラムを作成し、マルチスレッドの使用 (または使用しない) を分析/正当化するよう求めています。提案されたソリューション。大規模な問題について考え、彼らが行うアルゴリズムの選択を説明する候補者の能力をテストするのは簡単な質問です。候補者がインターネットのウェブサイトから何かを理解せずに逆流させていないことを確認してください。

これを考えると、この特定のインタビューの質問は、マルチスレッドが使用されているかどうかに関係なく、O( n log n ) (漸近的に言えば) で効率的に解決でき、さらにマルチスレッドを使用して実際の実行時間を対数的に加速することができます。

ソリューションの概要

一流企業から OP の質問を受けた場合、次のアプローチは、問題と関連する問題を本当に理解していることを示します。ここでは、2 段階のアプローチを提案します。

  1. ファイルは最初に分割され、メモリに読み込まれます。

  2. マージ ソートの特別なバージョンがパーティションで使用され、ファイルがソートされているときに各名前の頻度を同時に集計します。

例として、それぞれ 1 文字の長さで、それぞれの初期頻度カウントが 1 である 32 個の名前を持つファイルを考えてみましょう。上記の戦略は、次のように視覚化できます。

1. File:           ARBIKJLOSNUITDBSCPBNJDTLGMGHQMRH                32 Names

2. A|R|B|I|K|J|L|O|S|N|U|I|T|D|B|S|C|P|B|N|J|D|T|L|G|M|G|H|Q|M|R|H 32 Partitions
   1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1 with counts

3.  AR  BI  JK  LO  NS  IU  DT  BS CP  BN  DJ  LT  GM  GH  MQ  HR  Merge #1
    11  11  11  11  11  11  11  11 11  11  11  11  11  11  11  11  and tally

4.   ABRI    JKLO    INSU    BDST   BCNP    DJLT    GHM     HMQR   Merge #2
     1111    1111    1111    1111   1111    1111    211     1111   and tally

5.     ABIJKLOR         BDINSTU       BCDJLNPT         GHMQR       Merge #3
       11111111         1111211       11111111         22211       and tally

6.           ABDIJKLNORSTU                  BCDGHJLMNPQRT          Merge #4
             1212111111211                  1112211211111          and tally

7.                       ABCDGHIJKLMNOPQRSTU                       Merge #5
                         1322111312132113121                       and tally

したがって、メモリ内の最終的なリストを最初から最後まで読み取ると、並べ替えられたリストが得られます。

A|B|C|D|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
1|3|2|2|1|1|1|3|1|2|1|3|2|1|1|3|1|2|1 = 32 Name instances (== original file).


ソリューションが効率的な理由

ハッシュ テーブルが使用されているかどうか (元の投稿者が示唆したように)、およびマルチスレッドが使用されているかどうかにかかわらず、この問題に対する解決策は、並べ替えを実行する必要があるため、O( n log n )よりも効率的に解決できません。この制限があるため、採用できる戦略は 2 つあります。

  1. ディスクからデータを読み取り、ハッシュ テーブルを使用して名前/頻度の合計を管理し、ハッシュ テーブルの内容を並べ替えます (元の投稿者が推奨する方法)

  2. ディスクからデータを読み取り、ファイルからの頻度の合計で各名前を初期化し、名前をマージソートして、各名前のすべての合計を同時に合計します (このソリューション)。

解決策 (1) では、すべてのデータが読み込まれた後にハッシュ テーブルを並べ替える必要があります。解決策 (2) では、並べ替え中に頻度の集計を実行するため、ハッシュ テーブルのオーバーヘッドが取り除かれます。マルチスレッドをまったく考慮しなくても、解決策 (1) の最も効率的なハッシュ テーブルの実装を使用しても、解決策 (2) はハッシュ テーブルのオーバーヘッドがまったくないため、既により効率的であることがわかります。

マルチスレッドに関する制約

ソリューション (1) とソリューション (2) の両方で、これまでに考案された最も効率的なハッシュ テーブルの実装がソリューション (1) に使用されていると仮定すると、両方のアルゴリズムは O( n log n ) で漸近的に同じように実行されます。操作の順序が少し異なるだけです。ただし、ソリューション (1) をマルチスレッド化すると実際には実行が遅くなりますが、ソリューション (2) をマルチスレッド化すると速度が大幅に向上します。これはどのように可能ですか？

解決策 (1) をマルチスレッド化すると、ディスクからの読み取りまたはその後の並べ替えのいずれかで、すべてのスレッドが同時にハッシュ テーブルにアクセスしようとするため、ハッシュ テーブルで競合の問題が発生します。特にテーブルへの書き込みでは、この競合により解決策 (1)の実行時間が大幅に短縮される可能性があるため、マルチスレッドを使用せずに実行すると、実際には実行時間が短縮されます。

マルチスレッド化によって実行時間を高速化するには、各スレッドが実行する作業の各ブロックが他のすべてのスレッドから独立していることを確認する必要があります。これにより、すべてのスレッドが共有リソースで競合することなく最大速度で実行され、ジョブをはるかに高速に完了することができます。解決策 (2) はまさにこれを行い、ハッシュ テーブルを完全に削除し、問題を互いに独立したサブ問題に分割できる分割統治アルゴリズムであるMerge Sortを使用します。

実行時間をさらに改善するためのマルチスレッド化とパーティション化

マージソートをマルチスレッド化するために、ファイルをパーティションに分割し、新しいスレッドを作成して、連続するパーティションの各ペアをマージすることができます。ファイル内の名前は可変長であるため、パーティション分割を行うには、ファイルを最初から最後まで連続してスキャンする必要があります。ファイルへのランダム アクセスは使用できません。ただし、どのようなソリューションでも少なくとも 1 回はファイルの内容をスキャンする必要があるため、ファイルへのシリアル アクセスのみを許可することで最適なソリューションが得られます。

マルチスレッド化ソリューション(2)で期待できる実行時間の高速化はどのようなものですか? このアルゴリズムの分析は、その単純さを考えると非常にトリッキーであり、さまざまなホワイト ペーパーの主題となっています。ただし、ファイルをn 個のパーティションに分割すると、ファイルをパーティション分割しない単一の CPU よりも( n / log( n )) 倍速くプログラムを実行できます。簡単に言えば、単一のプロセッサが 640 GB のファイルを処理するのに 1 時間かかる場合、ファイルを 64 個の 10 GB のチャンクに分割し、32 個の CPU を搭載したマシンで実行すると、プログラムは約 6 分で完了することができ、10 倍の時間がかかります(ディスクを無視) 。諸経費）。

于 2012-07-30T05:47:30.713 に答える
3

マルチスレッドは良い考えではないと思います。プログラムの「遅い」部分はディスクからの読み取りであり、ディスクからの読み取りをマルチスレッド化しても高速にはなりません。それはそれをはるかに複雑にするだけです（たとえば、チャンクごとに最初の「完全な」行を見つける必要があり、さまざまなスレッドを調整する必要があり、アクセスするたびに共有ハッシュマップをロックする必要があります） . 「ローカル」ハッシュ マップで作業し、最後にそれらをマージできます (すべてのスレッドが終了すると (10GB の最後)、部分的なハッシュ マップがマージされます)。これで、共有マップへのアクセスを同期する必要がなくなりました。

完全なハッシュマップをメモリに保持できる場合、結果のハッシュマップをソートするのが最も簡単な部分になると思います:-)単にそれmallocをメモリの(ed)ブロックにコピーしqsort、そのカウンターでコピーします。

于 2012-07-19T10:13:48.613 に答える
3

ソリューションの (2) と (4) の手順により、本質的に順次になります (2 番目の手順では、ハッシュ マップの一貫性を維持するためのロックが導入され、最後の手順では、すべてのデータを並べ替えようとしています)。

最後のハッシュマップのワンステップソートは少し奇妙です。ヒープソート（データ構造のロックが必要）またはマージソート（「ヒストグラム」ファイルの一部をソートしますが、マージは避けます）などのインクリメンタルソート手法を使用する必要がありますすべてを「最後に 1 つのメイン スレッドで」 - ソート ネットワークを作成し、ソートの各ステップで出力ファイルの内容を混合してみてください)。

マルチスレッド読み取りが問題になる可能性がありますが、最新の SSD ドライブと積極的な読み取りキャッシュでは、マルチスレッドは主な速度低下要因ではありません。結果の並べ替えプロセスを同期させることがすべてです。

以下はマージソートの並列化のサンプルです: http://dzmitryhuba.blogspot.com/2010/10/parallel-merge-sort.html

繰り返しますが、私が言ったように、いくつかのソートネットワークは効率的な並列ソートを可能にするのに役立つかもしれませんが、単純な「すべてのサブスレッドを待って結果をソートする」ことはできません。たぶん、プロセッサがたくさんある場合はバイトニックソート。

于 2012-07-19T10:21:11.663 に答える