• [アーティクル]

この記事は機械翻訳されたものです。

働くプログラマ:

コンピューターの科学 (機械翻訳)

Ted Neward
Joe Hummel, Ph.D

コード サンプルのダウンロード

Ted Neward多くの年のために、自身が「コンピューター科学者として」記述の同僚を聞いたまた、"'科学' に名前を入れている研究の任意のフィールドは実際には科学ではない」と聞いた確かに私の分野でかなり大人数がきていないコンピューター科学別かなり大きな数で見ると軽蔑の大学と大学教授のお決まりのオフィスから来る仕事で正式なトレーニング — といくつかの正当化。 型システムを記述する称するギリシャ記号のスルーレートを助けたは、基幹業務アプリケーションが稼働して着いたらのですか？

途方もなくスマートの人々 の数を知っている、それらの 1 つはジョー フンメル、タイトルのコンピューター科学者、博士により合法的主張することができます誰です。 彼の名前とすべての背後にあります。 私のコンピューティングの科学を探求するには、このコラムの執筆参加を頼んだ。 それを開始するにコンピューター科学の仕事を通じてどのようにこれらの部品のいくつかの背後にある理論を理解、実際には、できるの簡単な部分のいくつか作業プログラマーとしてだけは少し楽に興味深いものになるだろうと思った。

今回は、私たちは私たちは、単純な概念を説明する一貫した方法を与えることを求めているのクラシックの「ビッグオー」の議論に取り組む: (時間、メモリ、電源およびなど) は、コンピューターに必要な指定されたプログラムを実行するどのように多くのリソースですか？ この決定はアルゴリズムの解析, アルゴリズムを選択した特定の数学的なカテゴリに配置することを目的として呼ばれます。 それはなぜですか。 だから、状況の最高の 1 つを選択できます。 リソース消費の中でジャンプを示す各連続したカテゴリとの多くのカテゴリーがあります。 私たちに焦点を実行時間、および最初の 3 つのカテゴリだけのつもり: o (1)、O(lgN)、o (n)。 典型的な場合は、N はアルゴリズムによって処理されるデータ項目の数を示します。 どこのエグゼクティブ ・ サマリーの私たちすべてこのと見るつもりだ図 1、期待できるカテゴリごとに N につれ実行時間強調します。

Execution Times as the Number of Items Processed (N) Grows
図 1 実行時間項目の数と処理 (不可) の成長します。

順序 N アルゴリズムを O(N) 書かれた、"大きな N O"を発音し、として「直線」はまた知られてN のデータ項目を与え、o (n) アルゴリズムは N の時間ステップの順序をかかります。 注文ログ N アルゴリズム O(lgN)、書かれている「ログ N ビッグオー」を発音してとして「対数する。」というN のデータ項目を与え、O(lgN) アルゴリズムは log2(N) の時間ステップの順序 (少数) かかります。 順序 1 アルゴリズムの o (1) を書いて、「ビッグオー」1 の発音し、「として定数」という最後に、N データ アイテムでは、o (1) アルゴリズムで一定数の時間ステップ (まだ少ない) かかります。 再訪する時間を割いて図1。 他に何はこのグラフを伝える可能性がありますか？ たとえば、N を 2 倍にすると、線形アルゴリズム倍の時間がかかることに注意してください。

これが実際の生活を適用する方法とは少しアルゴリズム解析について知るだけで巨大な影響をすることができますの例を見てみましょう。 不審な IP アドレスのリストに対する一致を検索するには、ログ ファイルを指定するいると仮定します。 十分に簡単な:

List<string> suspicious = BuildList(); /* step 0 */
foreach (string line in logfile)
{
  string ipaddr = parse(line);         /* step 1 */
  if (suspicious.Contains(ipaddr))     /* step 2 */
    matches++;                         /* step 3 */
}

どのようにこの方法の計算時間を分類しないでください？ M 行 N の不審な IP アドレスのログ ファイルがあると仮定しましょう。 並べ替えられていないリスト (ステップ 0) の N 要素の構築と O(N) の 1 回限りのコストが発生します。 M の反復、ループで実行されるループのコストが O だ (M ※ 1 つのイテレーションのコスト)。 各反復処理では、3 つの基本的な手順を実行します。

  1. 行をを
  2. リストを検索します。
  3. 単位と一致する一致が見つかった場合

それを分析してください。

アルゴリズム解析の知的側面を学習して何をカウントして何をカウントされません。 たとえば、行を解析中 — おそらく、正規表現または行のトークンに分割 — 高価になる可能性があります、それは定数データの相対的な時間のかかります。 ファイルに M または 2 M の線があるかどうか他の言葉では、行を解析するために必要な時間完全、変わりません。 また、N または 2 n の不審な IP アドレスがあるかどうかそれを変更は。 したがって、我々 は、手順 1 と 3 c (定数) の時間がかかると言います。 ただし、リストを検索、ステップ 2、不審な IP アドレスの数を基準を変更しています。

if (suspicious.Contains(ipaddr))

Contains メソッドは、線形の検索、最初の要素から開始し、一致が見つかるか、リストの末尾に達するまで検索を実行します。 （どのように私たちこれできるでしょうか。 3 つの方法： 私たちはそれをテスト、我々 のソース コードを見たまたは、MSDN ライブラリのドキュメントを告げて)。

ランダムなデータで、平均では半分のリスト N/2 の手順を必要とする検索します。 これはほとんどの場合、保持するが、この特定のケースでは、強い引数、銀行、大統領候補の Web サイトに弊社の Web サーバーではないのでほとんどの IP アドレス、ログ ファイルの信頼です。 つまり、特定のクライアントが信頼できないという五分のチャンスの存在ではなく、N ステップを必要とする一致を見つけることなくがリスト検索の大半を排気するでしょう。

定数、事の順序を計算するときに削除されますので、検索を O(N) の複雑さを降伏、どちらの場合では O(M * N) のループ。 ターンでは、これは全体的にアルゴリズムの複雑性を生成します。

= O(build + loop)
= O(N + M * N)
= O( (1 + M) * N )
= O(M * N)

したがって、当社のソリューションのバージョン 1 に O(MN) の時間が必要です。

' データ、データ、データ ！ 粘土がなければレンガを作れない ！」

自問するには、最初の質問です：「我々 はより良いアルゴリズムは必要か」M は通常大規模な何百万に （おそらく数十億) の行。 ないそれについてを行うことができますので、それを検索するには、各ラインに触れること。 不審な IP アドレスの数 N が小さいだかどうか (N と言う、< 100）、あなたの仕事を完了した後。 今日の高速マシンでは、M の時間ステップと 100 M の時間ステップの少しの測定可能な違いです。 ただし、N として育つより大きい (たとえば、N >> 100、または 100 よりも大幅に大きい)、他の検索アルゴリズムを検討する価値があります。

あなたがもちろん、本当に大きなハードウェア予算を持っていない限り。 （時に、その場合でも)。

効率的なアルゴリズムは、中央にジャンプ バイナリの検索し、検索の左または右、探している要素中の要素より小さいかどうかに応じて以上です。 それぞれの半分の時間で探索空間を切断して、アルゴリズムは O(lgN) の動作を示します。 この実際にはどういう意味ですか？ 与えられた N = 1, 000 要素、最悪のバイナリ検索が 10 時間ステップ (210 ≒ 1,000) 線形検索が順序で 1,000 かかります。 N = 100 万、違いはさらに劇的です — 100 万対 20 時間ステップの順序。 キーのトレードオフは、バイナリ検索並べ替えられた順序でデータが必要です。 ここでは、バイナリ サーチを使用するよう修正ログ ファイル検索プログラムです。

List<string> suspicious = BuildList();      /* step 0 */
suspicious.Sort();                          /* step 0.5 */
foreach (string line in logfile)
{
  string ipaddr = parse(line);               /* step 1 */
  if (suspicious.BinarySearch(ipaddr) >= 0)  /* step 2 */
    matches++;                               /* step 3 */
}

イテレーションあたりのコストがより効率的なバイナリ検索 （ステップ 2） を与え O(lgN) に O(N) からを低減できる一方疑わしい一覧 (ステップ 0.5) の並べ替えと、1 回限りのコスト O(NlgN) を表します。 これは全体的にアルゴリズムの複雑性を生成します。

= O(build + sort + loop)
= O(N + N * lgN + M * lgN)
= O(N * (1 + lgN) + M * lgN)
= O(N * lgN + M * lgN)
= O((N + M) * lgN)

このシナリオでは、m >> N、N より小さい定数のような M を追加したとき、および当社のソリューションのバージョン 2 約 O(MlgN) 時間が必要になります機能します。 それで? N = 1,000 の不審な IP アドレス、我々 だけ実行時間 1,000 M の時間ステップの注文から 10 100 倍速くある M に減少します。 追加の並べ替え時間約 10,000 の時間ステップ (O(NlgN)) 以上に繰り返し貯蓄によって検索時間のオフセットします。

ハッシュに行こう

検索しているデータについての何かを知っているとき、あなたはハッシュ テーブルを作成することができます （と）。 ハッシュ低減平均検索時間 O (1) —、あなたより良い行うことはできません。 これは、単一の値にその値をハッシュ関数によって生成、テーブルに格納されている要素のマッピングを作成することによってされます。 ハッシュのキーの要件は、いくつかの衝突 (重複するマッピング） の整数の範囲にわたって検索データをマップする良いハッシュ関数の存在です。 改訂ログ ファイル プログラム (バージョン 3) は、組み込み文字列のサポートは、Microsoft .net Framework でハッシュ効果的なを活用：

Dictionary<string, int> suspicious = BuildHashTable();  /* step 0 */
foreach (string line in logfile)
{
  string ipaddr = parse(line);                          /* step 1 */
  if (suspicious.ContainsKey(ipaddr))                   /* step 2 */
    matches++;                                          /* step 3 */
}

ハッシュ表の （ステップ 0） 構築 O(N) の 1 回限り、前払い費用が発生します。 これは全体的にアルゴリズムの複雑性を生成します。

= O(build + loop)
= O(N + M * 1)
= O(N + M)

M のシナリオと仮定すると >> N、バージョン 3 最速ソリューション、O(M) 時間で約です。 N = 1,000 の不審な IP アドレス、我々 だけ実行時間、10 のもう一つの要因によって、1,000 x の元のバージョンよりも高速です減少します。 このアプローチに関する注目すべきは N のさらに大きな値を — と言う、10,000、あるいは 100,000 — 実行時間 M の時間ステップの順序は同じです。

キャッチとは何ですか？ バージョン 2 とバイナリ検索では、単純です: 最初の IP アドレスの一覧を並べ替える必要があります。 ハッシュをこのバージョンでは、考慮する 3 つの問題: 効果的なハッシュ関数、前払い建設コストより大きいメモリ フット プリントを作成します。 キーは、ハッシュ関数です。 有効なハッシュ関数、データ追加後の初期のハッシュ テーブルに検索が不要の衝突の最小値の表が分散されます。 このような関数は o (1) の先行建設コスト 1 データム、または o (n)、同じ線形検索を提供しています。 ただし、このような効果は、通常負荷率の 10 ％ は、データ テーブルのわずか 10 ％ を占めていることを意味、近所です。 正式にこれは O(N) のような他がハッシュとメモリ フット プリント 10 x 線形とバイナリの検索よりも大きいしたがって必要です。

なぜこれは、もう一度やっているか？

そのすべての pseudo-math 後は、非コンピューター科学理論の操作の多くは、私たちが効率的な解決方法を見つけたと思うが、確かに多くの定数、途中寄った大学院打つでしょう。 これは百万 - に導く­のドルの質問:「実際には本当に返済理論分析か？」公正な質問、特にとき考慮この記事の究極の目標-アルゴリズムの解析 (既にいない場合) を使用してコードをコミットする前に、競合のアプローチを評価することをお勧めします。

何回エンジニアの時間のための議論を見て、テーブルの周りに座っていたきた — も日、時々 — アプローチ A が B. アプローチよりも適切であるかどうかを ほとんどの人々 は、ナプキンをプルは、アルゴリズムの迅速な分析を実行します。

だから、我々 の分析を行っている今は、いくつかのテストを実行、実際には起こる見てみましょう。 行うには、M のエントリをランダムなログ ファイルを生成し、[これらのファイルに対してランダムに生成されたリストの n 個の IP アドレスを検索します。 (完全なソース ファイルと入力ファイルは bit.ly/srchlogfiles.)

要約するには、M と仮定すると >> N を私たちに示すようにアルゴリズムの複雑な派生図 2。

図 2 アルゴリズムの複雑さと仮定すると M >> N

  時刻 (t)
バージョン 1: 線形検索を使用します。 O(M * N)
バージョン 2: バイナリ検索を使ってください。 O(M * lgN)
バージョン 3: ハッシュを使用してください。 O(M)

我々 のテストのために、100 万と二重の N の各テストの設定に M: 128、256 や 512。 N の 2 倍と検索アルゴリズムの性能特性がハイライトされます。 我々 の分析は N 倍になってたびに正確である場合は、実行時間に示すように変更する必要があります図 3。

図 3 は実行時間の変化を予測したとき 不可 2 倍になります

  2 N の時間
バージョン 1 O (M ※ 2 ※ N) = > 2 ※ O(M * N) = > 2 t
バージョン 2 O (M ※ lg(2N)) = > O (M ※ (lg2 + lgN)) = > O (M ※ (1 + lgN) = > O (M + M ※ lgN) = > M + O(M * lgN) = > M + t
バージョン 3 O(M) = > t

他の言葉では、バージョン 1 時間 （2 t） をダブルすべきバージョン 2 (t + M) の別の M 時間ステップを取る必要があります、追加の時間 (t) バージョン 3 はいけない。 図 4 、実際の番組を録画時間 （秒単位）。

図 4 実際の実行時間 (秒)

M 不可 バージョン 1 バージョン 2 バージョン 3
1,000,000 128 3.81 2.88 2.15
  256 5.65 2.98 2.15
  512 9.39 3.11 2.17
  1,024 16.78 3.23 2.19
  2,048 31.52 3.36 2.19
  4,096 61.18 3.49 2.28
  8,192 120.63 3.68 2.39
  16,384 238.86 3.95 2.54
  32,768 473.91 4.34 2.89

見ることができます図 4、バージョン 1 — 線形探索に基づく — は N 倍としての時間確かに二重。 おそらくほとんどの状況の悪いことです。

バージョン 2 — バイナリの探索に基づく — 桁の 1 のバージョンよりも速く実行されよりゆっくりと成長します。 成長率はどこ 0.1 ～ 0.3 秒が表示されます M の操作を実行するための TM の時間に依存するために定量化が困難です。 我々 の分析によるとバージョン 2 TM N 倍としての一定速度で成長する必要がありますが、この場合に表示されない; このキャッシュの増加圧力の結果をことができる (およびしたがってキャッシュ ・ ミス) N につれ。

最後に、 図 4 バージョン 3 が実際には基本的に同じ実行時間が N に関係なく、最速のアルゴリズム (再びかなり一定ではない) を確認します。

バランスを求める

現実主義者の観点からは、バージョン 2 からバージョン 3 への強化努力のささいな金額以上の何かの価値があることは明らかではない — 1 秒以上の節約にもかかわらず。 潜在的な貯蓄は本当に私たちは本当に大きな値 M または N (ハッシュ 10 x IP アドレスを格納するより多くのメモリが必要があります覚えておいて) を参照してくださいに開始しない限り、大きな違いを生むつもりはないです。 この最後の点を発生させます: を最適化しようとして停止するときに知っています。 それは、エキサイティングで何らかの操作を実行する場合は、絶対最速アルゴリズムを見つけるためのプログラマーを説得力のあるかもしれないが、フロント-と-は、2 番目はしばしばより良いことが出来ましたセンターを最適化しようとする時間をユーザーの顔でのこの操作のでない限り、何か他の作業を費やしています。 (約 10,000 ％ の貯蓄) 時間価値がある、バージョン 1 からバージョン 2 へのジャンプを明らかですが、すべてのものと同様に、プログラマのバランスを求める必要があります。 時々 理論実践への道を与える必要がありますが他の回では、理論は我々 の取り組みを実践する必要を決定ことができます。

コーディングを楽しんでください。

Ted Neward Neudesic LLC、建築コンサルタントです。 彼が 100 以上の記事を書かれてあり、作成または「プロ F c# 2.0」を含む、数十本を共著 （Wrox、2010年）。彼は c# MVP であり、世界中のカンファレンスで話します。彼は相談を行い、定期的にメンター — 彼に到達 ted@tedneward.com または Ted.Neward@neudesic.com 彼に来てあなたのチームとの仕事や自分のブログで読むことに興味があれば blogs.tedneward.com。

Joe Hummel民間コンサルタント、Pluralsight LLC の技術スタッフ、MVP Training.net のトレーナー、客員研究員工学部は、カリフォルニア大学アーバイン校のメンバーです。 彼は博士号を取得 高パフォーマンス コンピューティングの分野で UC アーバインと並列の全てのものに興味があります。彼は、シカゴ地域で存在し、とき彼は航海ではないに到達することができます joe@joehummel.net。