algorithm - コードの Big-O 効率をプログラムで取得する

Question

特定の関数の Big-O 時間の複雑さを (少なくとも大まかに) 自動的に決定する方法があるかどうか疑問に思いますか?

O(n) 関数と O(n lg n) 関数をグラフにすると、どちらがどちらであるかを視覚的に確認できると思います。これを自動的に実行できるヒューリスティックなソリューションが必要だと思います。

何か案は？

編集:半自動化されたソリューションを見つけることができてうれしく思います.完全に手動の分析を回避する方法があるかどうか疑問に思っています.

score 61 · Accepted Answer

あなたが求めているのは、停止問題の拡張のようです。理論上でさえ、そのようなことが可能だとは思いません。

「このコード行は実行されますか?」という質問に答えるだけです。一般的なケースでは、不可能ではないにしても非常に困難です。

追加するために編集: 一般的なケースは扱いにくいですが、部分的な解決策についてはこちらを参照してください: http://research.microsoft.com/apps/pubs/default.aspx?id=104919

また、手動で分析を行うことが唯一の選択肢であると述べている人もいますが、それが本当に正しい見方だとは思いません. システム・機械に人間が加わっても、難解な問題は難解です。さらに考えてみると、99% の解決策が実行可能であり、人間と同じかそれ以上に機能する可能性さえあると思います。

score 39 · Accepted Answer

さまざまなサイズのデータセットに対してアルゴリズムを実行し、曲線近似を使用して近似値を求めることができます。(ほとんどの場合、作成した曲線を見るだけで十分ですが、どの統計パッケージにも曲線適合があります)。

一部のアルゴリズムは、小さなデータセットを持つ 1 つの形状を示しますが、大きなデータセットを持つ別の形状を示すことに注意してください...そして、大規模の定義は少しあいまいなままです。これは、優れたパフォーマンス曲線を持つアルゴリズムは、現実世界のオーバーヘッドが非常に大きくなり、(小さなデータセットの場合) 理論的に優れたアルゴリズムほどうまく機能しない可能性があることを意味します。

コード検査技術に関する限り、存在しません。しかし、さまざまな長さで実行するようにコードを計測し、単純なファイル (RunSize RunLength で十分です) を出力するのは簡単なはずです。適切なテストデータを生成することは、より複雑になる可能性があります (一部のアルゴリズムは、部分的に順序付けられたデータでうまく機能する場合と機能しない場合があるため、通常のユースケースを表すデータを生成する必要があります)。

「何が大きいか」の定義の問題と、パフォーマンスがデータに依存するという事実のために、静的分析は誤解を招くことがよくあります。パフォーマンスを最適化し、2 つのアルゴリズムのいずれかを選択するとき、現実世界の「ゴムが道路にぶつかる」テストは、私が信頼する唯一の最終的な仲裁者です。

score 14 · Accepted Answer

短い答えは、定数が重要であるため不可能だということです。

たとえば、で実行される関数を作成する場合がありますO((n^3/k) + n^2)。これは O(n^3) に単純化されます。これは、n が無限大に近づくにつれて、n^3定数に関係なく項が関数を支配するためkです。

ただし、k上記の例の関数でが非常に大きい場合、関数は、項が優勢になり始めるn^2クロスオーバーポイントまでほぼ正確に実行されているように見えます。n^3定数kはどのプロファイリングツールにも認識されないため、ターゲット関数をテストするデータセットのサイズを正確に知ることは不可能です。任意に大きくなる可能性がある場合k、大きな実行時間を決定するためのテストデータを作成することはできません。

score 13 · Accepted Answer

ストップウォッチで複雑さを「測定」できると主張する試みが非常に多いことに驚いています。何人かの方が正解されていますが、肝心なところはまだまだ突き詰める余地があると思います。

アルゴリズムの複雑さは「プログラミング」の問題ではありません。それは「コンピュータサイエンス」の問題です。この質問に答えるには、数学者の観点からコードを分析する必要があります。そのため、Big-O の複雑さを計算することは、実質的に数学的証明の形式となります。基本的なコンピューター操作、代数、おそらく微積分 (極限)、および論理についての非常に強い理解が必要です。そのプロセスの代わりに「テスト」を行うことはできません。
停止問題が適用されるため、アルゴリズムの複雑さは基本的に機械では判断できません。
自動化されたツールの限界が適用されるため、支援するプログラムを作成することは可能かもしれませんが、電卓が物理学の宿題に役立つか、リファクタリングブラウザがデータの再編成に役立つ程度にしか役立ちません。コードベース。
このようなツールの作成を真剣に考えている人には、次の演習をお勧めします。サブジェクトアルゴリズムとして、好みの並べ替えなど、適度に単純なアルゴリズムを選択します。アルゴリズムの複雑さを計算し、最終的に「Big-O」を計算するプロセスを案内するための信頼できるリファレンス (本、Web ベースのチュートリアル) を入手してください。サブジェクトアルゴリズムを使用してプロセスを進めながら、手順と結果を文書化します。最良のケース、最悪のケース、平均的なケースなど、いくつかのシナリオで手順を実行し、進捗状況を文書化します。作業が完了したら、ドキュメントを確認し、それを実行するプログラム (ツール) を作成するには何が必要かを自問してください。それはできますか？実際に自動化されるのはどれくらいで、手動のままになるのはどれくらいですか?

幸運をお祈りしています。

score 9 · Accepted Answer

なぜあなたがこれができるようになりたいのか、私は興味があります。私の経験では、誰かが「このアルゴリズムのランタイムの複雑さを確認したい」と言ったとき、彼らは自分が求めていると思うことを尋ねていません。あなたが最もよく尋ねているのは、可能性の高いデータに対するそのようなアルゴリズムの現実的なパフォーマンスは何かということです。関数の Big-O を計算することは合理的な有用性がありますが、実際の使用ではアルゴリズムの「実際の実行時パフォーマンス」を変更できる側面が非常に多くあるため、インストルメンテーションとテストに勝るものはありません。

たとえば、次のアルゴリズムにはまったく同じ Big-O (風変わりな疑似コード) があります。

例 a:

huge_two_dimensional_array foo
for i = 0, i < foo[i].length, i++
  for j = 0; j < foo[j].length, j++
    do_something_with foo[i][j]

例 b:

huge_two_dimensional_array foo
for j = 0, j < foo[j].length, j++
  for i = 0; i < foo[i].length, i++
    do_something_with foo[i][j]

繰り返しますが、まったく同じ big-O ですが、そのうちの 1 つは行の順序を使用し、もう 1 つは列の順序を使用します。参照の局所性とキャッシュの一貫性により、特に配列 foo の実際のサイズによっては、 2 つの完全に異なる実際のランタイムが存在する可能性があることがわかります。これは、並行性が組み込まれているソフトウェアの一部である場合、アルゴリズムがどのように動作するかという実際のパフォーマンス特性に触れることさえしません。

否定的なネリーではなく、Big-O は範囲の狭いツールです。アルゴリズム分析の奥深くにいる場合、またはアルゴリズムについて何かを証明しようとしている場合に非常に役立ちますが、商用ソフトウェア開発を行っている場合、証明はプリンの中にあり、実際のパフォーマンスの数値が必要になります。賢明な決定を下すために。

乾杯！

score 4 · Accepted Answer

これは単純なアルゴリズムでは機能しますが、O(n^2 lg n) や O(n lg^2 n) はどうでしょうか?

視覚的に非常に簡単にだまされる可能性があります。

そして、それが本当に悪いアルゴリズムなら、n=10 でも戻らないかもしれません。

score 3 · Accepted Answer

これが決定不可能であることの証明：

ある関数fについて、すべてのnについてプログラムがO（f（n））で停止するかどうかを決定するアルゴリズムHALTS_IN_FN（Program、function）があるとします。

Pを次のプログラムとします。

if(HALTS_IN_FN(P,f(n)))
{
    while(1);
}
halt;

関数とプログラムが固定されているため、この入力のHALTS_IN_FNは定数時間です。HALTS_IN_FNがtrueを返す場合、プログラムは永久に実行され、もちろん、どのf（n）に対してもO（f（n））で停止しません。HALTS_IN_FNがfalseを返す場合、プログラムはO（1）時間で停止します。

したがって、パラドックス、矛盾があり、プログラムは決定不可能です。

score 3 · Accepted Answer

多くの人が、これは理論上本質的に解決不可能な問題であるとコメントしています。当然のことですが、それ以上に、最も些細なケースを除いて、それを解決することさえ非常に難しいように思えます.

一連のネストされたループを持つプログラムがあるとします。それぞれが配列内のアイテムの数に基づいています。O(n^2)。しかし、内側のループが特定の状況でのみ実行される場合はどうなるでしょうか。平均して、約 log(n) のケースで実行されるとしましょう。突然、「明らかに」O(n^2) アルゴリズムは実際には O(n log n) になります。内側のループが実行されるかどうか、および実行される頻度を決定できるプログラムを作成することは、元の問題よりも困難になる可能性があります。

O(N) は神ではないことに注意してください。高い定数は、競技場を変える可能性があり、変わるでしょう。クイックソートアルゴリズムはもちろん O(n log n) ですが、再帰が十分に小さくなった場合、たとえば 20 アイテム程度まで減ると、クイックソートの実装の多くは戦術を別のアルゴリズムに変更します。実際には別のタイプのソートを行う方が速いからです。、悪い O(N) の挿入ソートを言いますが、定数ははるかに小さくなります。

したがって、データを理解し、知識に基づいた推測を行い、テストしてください。

score 2 · Accepted Answer

このようなベンチマークを実行するときも注意が必要です。一部のアルゴリズムは、入力タイプに大きく依存する動作をします。

クイックソートを例にとってみましょう。最悪の場合は O(n²) ですが、通常は O(nlogn) です。同じサイズの 2 つの入力の場合。

巡回セールスマンは (確かではないと思いますが) O(n²) (編集: ブルートフォースアルゴリズムの場合、正しい値は 0(n!) です) ですが、ほとんどのアルゴリズムでは、かなり優れた近似解がはるかに高速に得られます。

これは、ほとんどの場合、ベンチマーク構造をアドホックベースで適応させる必要があることを意味します。言及された 2 つの例に一般的なものを書くことを想像してください。これは非常に複雑で、おそらく使用できず、いずれにせよ誤った結果をもたらす可能性があります。

score 2 · Accepted Answer

これを自動的に行うことはほとんど不可能だと思います。O(g(n)) は最悪の場合の上限であり、多くの関数は多くのデータセットに対してそれよりも優れたパフォーマンスを発揮することに注意してください。それらを比較するには、それぞれの最悪のケースのデータセットを見つける必要があります。これは、多くのアルゴリズムにとって、それ自体が困難な作業です。

score 1 · Accepted Answer

ジェフリー・L・ウィトレッジは正しいです。停止問題からの簡単な還元は、これが決定不可能であることを証明します...

また、もし私がこのプログラムを書くことができたら、それを使って P 対 NP を解き、100 万ドルを手に入れたいです... B-)

score 0 · Accepted Answer

他の人が言っているように、これは理論的に不可能です。しかし実際には、時々間違っていることを気にしない限り、関数がO（ n）であるかO（n ^ 2）であるかについて知識に基づいた推測を行うことができます。

初めてアルゴリズムを実行し、さまざまなnの入力で実行します。両対数グラフに点をプロットします。ポイントを通る最適な線を引きます。線がすべての点にうまく適合している場合、データはアルゴリズムがO（n ^ k）であることを示しています。ここで、kは線の傾きです。

私は統計家ではありません。あなたはこれらすべてを一粒の塩で服用するべきです。しかし、私は実際に、パフォーマンスの低下に対する自動テストのコンテキストでこれを実行しました。ここのパッチには、そのためのJSコードが含まれています。

score 0 · Accepted Answer

入力の型と構造は関数によって大きく異なるため、これは完全に自動化された方法では不可能だと思います。

score 0 · Accepted Answer

これを行う目的が何であるかはわかりませんが、私が教えていたコースで同様の問題がありました. 学生は、特定の複雑さで機能するものを実装する必要がありました。

ソリューションを手動で調べずにコードを読むために、@Godeke が提案した方法を使用しました。目的は、バランスのとれた検索ツリーの代わりにリンクリストを使用した学生、またはヒープソートの代わりにバブルソートを実装した学生 (つまり、必要な複雑さで機能しない実装であるが、実際にコードを読まずに実装した学生) を見つけることでした。

驚くべきことに、結果はカンニングをした学生を明らかにしませんでした。それは、生徒たちが正直で学びたいと思っているからかもしれません (または、これを確認することを知っていた ;-) )。入力が小さい場合、または入力自体が順序付けられている場合など、不正な学生を見逃す可能性があります。また、カンニングはしていないが定数値が大きい学生については、間違っている可能性もあります。

エラーが発生する可能性はありますが、チェック時間を大幅に節約できるため、それだけの価値があります。

score 0 · Accepted Answer

まあ、関数が停止するかどうかさえ証明できないので、少し質問していると思います。

それ以外の場合は、@Godeke がそれを持っています。

score -1 · Accepted Answer

同種の計算リソースがたくさんある場合は、それらをいくつかのサンプルに対して時間測定し、線形回帰を実行してから、単純に最も高い項を取ります。

score -1 · Accepted Answer

指示を得るのは簡単です（例えば、「関数は線形ですか？準線形ですか？多項式ですか？指数関数ですか」）

正確な複雑さを見つけるのは難しいです。

たとえば、Python ソリューションは次のとおりです。関数と、その関数のサイズ N のパラメーターを作成する関数を指定します。プロットまたは回帰分析を実行する (n,time) 値のリストが返されます。速度のために一度計時しますが、本当に良い指標を得るには、環境要因からの干渉を最小限に抑えるために何度も計時する必要があります (例: timeitモジュールを使用)。

import time
def measure_run_time(func, args):
  start = time.time()
  func(*args)
  return time.time() - start

def plot_times(func, generate_args, plot_sequence):
  return [
    (n, measure_run_time(func, generate_args(n+1)))
    for n in plot_sequence
  ]

そして、それをバブルソートの時間に使用するには：

def bubble_sort(l):
  for i in xrange(len(l)-1):
    for j in xrange(len(l)-1-i):
      if l[i+1] < l[i]:
        l[i],l[i+1] = l[i+1],l[i]

import random
def gen_args_for_sort(list_length):
  result = range(list_length) # list of 0..N-1
  random.shuffle(result) # randomize order
  # should return a tuple of arguments
  return (result,)

# timing for N = 1000, 2000, ..., 5000
times = plot_times(bubble_sort, gen_args_for_sort, xrange(1000,6000,1000))

import pprint
pprint.pprint(times)

これは私のマシンに印刷されました：

[(1000, 0.078000068664550781),
 (2000, 0.34400010108947754),
 (3000, 0.7649998664855957),
 (4000, 1.3440001010894775),
 (5000, 2.1410000324249268)]

algorithm - コードの Big-O 効率をプログラムで取得する

18 に答える 18

Related

Reference