2

実行に数時間 (場合によっては数日) かかる PHP スクリプトがあります。これは非常に単純ですが、非常に CPU を集中的に使用し、実行時間のほとんどが費やされます (スクリプトのプロファイリングを行った後でわかります)。

  1. $array = explode(',', $a[$i]); ここ$a[$i]で、コンマで区切られた 30k 要素のベクトルを表す非常に長い文字列です

  2. foreach($array as $key => $value)ループ; ループごとに、いくつかの in_array() と比較および代入操作が実行されます

$a実際には非常に大きくて疎な行列 (30k * 30k) ですが、メモリに保持することはできません (8GB では十分な RAM がないようです)。explode()行に取り組む必要があるときはいつでも。

C (または他の言語) ですべてを書き直すとパフォーマンスが向上することはわかっていますが (どれくらい?)、その前に、PHP の実行時間を改善するために何かできることがあるかどうかを知りたいと思います。

回答後に編集します。

私はあなたのアドバイスをいくつか試しましたが、ここに私のレポートがあります：

1) str_getcsv はほとんどの場合、explode よりも遅い

2) SPLFixedArray は行列を格納するために要求されるメモリを減らしますが、それでも 30k x 30k の行列には 8GB では不十分なので、あまり役に立たないと思います。ここでの本当の問題は、PHP でマトリックスのスパース表現が欠如していることだと思います。

3) 分解操作のすべての結果を保存することはできません。これは、マトリックス全体をメモリに保持することを意味するためです (十分な RAM がありません)。

4) 遅くなるだろうと確信していたとしても、データベース アプローチを試してみました。各マトリックス要素を表すためにトリプル (i、j、値) を格納しました。重要度の低い値を削除して (しきい値よりも小さい値を犠牲にして、精度の低い結果を得ることができますが、それでも有用です)、1,800 万個のタプルだけを保存しても、mysql myisam を使用したアプローチは、メモリ内の配列アプローチよりもはるかに遅くなります。

5) MEMORY エンジン (RAM 内の mysql テーブル) を使用し、値がゼロのものを除くすべての行列要素を格納するデータベース アプローチを試しました。今回は 4,200 万件のレコードがあります... 1 桁ではなく 2 ～ 4 倍高速です... 15 ～ 20 日ではなく 5 日で仕事を終えることができると思います ... それでも多すぎます（24時間以内に仕上げたいと思います）他に提案があれば大歓迎です

編集2：問題を説明します

問題の詳細を説明します。すべてを単純化する必要があります。そうしないと説明が長くなりすぎますが、状況をよりよく理解するには十分だと思います。

ノード間の距離を表すマトリックスがあります。整数の距離であり、無限になることもあります。

node_1、node_2、距離の各距離をトリプルで表すメモリテーブルがあります(無限ではない距離のみが表されます)。

私が書いていないこの種の貪欲なアルゴリズムがあり、8GBのRAMを搭載したラップトップで実行可能な時間（1日未満としましょう）で実行するように最適化する必要があります。

アルゴは基本的に入力 2 つのノードを取得し、各ステップで検証する必要がある次の 2 つのプロパティに従って、開始ノードと終了ノードの間のパスを段階的に設計します。

  • 新しい中間ノードは、現在のノードに関して終了ノードに近い一連のノードの中から選択する必要があります
  • それらのノードのうち、現在のノードに近いノードが選択されます

1) 三角形の不等式が満たされていないことを考慮してください。2) 最短経路問題ではない

以下は、終了ノードに十分近づくまで何度か呼び出す関数の疑似コードです。

get_next_node($node_1, $node_2){

    $dist = select distance from distances_table where node_2 = $node_2 and node_1 = $node_1

    $candidates_ar = select node_1 from distances_table where node_2 = $node_2 and distance < $dist

    $distances_ar = select distance from distances_table where node_1 = $node_1 and node_2 in ($candidates_ar) // e.g. $distances_ar[12] contains distance between node 12 and $node_1

    $min = 1000;
    foreach ($candidates_ar as $value){
        if ($distances_ar[$value] < $min){
            $min = $distances_ar[$value]
            $next_node = $value
        }
    }

}

多くのチェックと追加の複雑さを省略しましたが、これが基本であり、アルゴリズムがほとんどの時間を費やす場所です。

A* の実装で解決できると思いますが、数時間（数日ではなく）で実行できるようにパフォーマンスを上げることができれば避けたいと思います。

ありがとう。

4

3 に答える 3

8

わかりました、パフォーマンスの問題があります。楽しい部分が始まります。

最初のステップは、推測しないことです。C で書き直さないでください。PHP コンパイラを切り替えないでください。それは吸盤のためです。代わりに、実際のボトルネックを見つけることから始めてください。

XDEBUG を取得し、アプリケーションのcachegrind プロファイリングを生成します。これにより、ほとんどの時間が費やされている場所が表示されます。

xhprofも使用できます。

ポイントは、推測ではなく、プロファイルです。アルゴリズムの遅い部分を見つけて、それらを最適化します。

問題はおそらくコードではなく、使用しているアルゴリズムです。アルゴリズムを形式化することをお勧めします。これにより、特定の制約に合わせてパーツを最適化および調整できるようになります。

例えば。現在、大きな CSV 文字列を解析しています。なんで？それをデータベースに貼り付けて、データベースに面倒な作業を任せてみませんか? 特定のユースケースでは明らかに不可能かもしれませんが、PHPで30k要素の配列を操作している人を見ると、通常、それはそもそもすべきではないことをしているためです。

他のすべてが失敗した場合は、アルゴリズムを分割して実行できるようにしてください。そうすれば、map-reduce または同様の手法を実行してランタイムを微調整することができます。

要するに、それは本当にあなたが何をしているかにかかっています。しかし、ランタイムの再コーディングまたは切り替えは、私の最後の手段であり、最初のステップではありません...

于 2013-06-24T16:12:30.683 に答える
-1

Cで書き直した方がずっと速いでしょう！

代わりに使用できますstr_getcsv($a[$i]);が、これは少し高速です。

RAM に関しては、データを好きなように処理し、必要に応じて使用unset($a[$i])してください。

So either rewrite in C, or you could make it go in stages, split the CSV into 10 chunks and process it that way, you could even run all 10 at the same time which may increase speed. Or have your CSV file in a database to really cut down on speed.

于 2013-06-24T15:26:03.280 に答える
-1

Facebook ヒップホップ コンパイラについて聞いたことがありますか。これを試すことができます。スクリプトをはるかに高速に実行し、最小限の CPU リソースを使用するのに役立ちます。

于 2013-06-24T15:38:09.530 に答える