アルゴリズムの最適化 - ページ 6

[Andrey Khatimlianskii]

C-4:

問題はすべて2サイクル目にある。極限状態からの左右の分岐を同時に処理するため、(N - 1)/2 本の棒を通過するだけですが、それだけでは十分ではありません。測定によると、等差数列の極値探索にかかる時間は周期Nに依存し、これは非常に悪いことです。

少なくとも1つのブレークが欠落している。

//Перебираем все бары
for (int bar = 0; bar < MyQuotes.Count; bar++)
{
   //Подготовка данных
   ...
   int pperiod = (N - 1)/2;
   //Перебираем бары относительно потенциального экстремума
   for (int i = 1; i <= pperiod; i++)
   {
      if (MyQuotes.High[bar - i] > MyQuotes.High[bar] ||
         MyQuotes.High[bar + i] > MyQuotes.High[bar])
         up = false;
      if (MyQuotes.Low[bar - i] < MyQuotes.Low[bar] ||
         MyQuotes.Low[bar + i] < MyQuotes.Low[bar])
         down = false;

      if ( !up && !down ) break; // А зачем искать дальше?
   }
}

もっといいのは、本当に上下に分けて、チェックに失敗したらすぐにやめることです。

[TheXpert]

Mathemat:

どうしてもダメなら、OCLを試してみてください。

大差はないでしょう。

[Vasiliy Sokolov]

TheXpert:
大きな違いはないでしょう。

はい、そうなります。これは、このタスクがシーケンシャルな実行を必要としないためである。バー全体の履歴はk個のセグメントに分けることができ、それぞれが異なるCPUコアで処理されることになる。OCLの仕組みは知りませんが、原理はここでも同じだと思います。もうひとつ、ジグザグ自体がシーケンシャルで、新しい行は前の行の終わりから始まるので、サブタスクへの分割が非常に難しい、あるいは不可能です。

[Vasiliy Sokolov]

komposter:

少なくとも1つのブレークが欠落している。

さらに良いのは、上下を本当に分けて、チェックに失敗したらすぐにやめることです。

ここでも、トップとボトムを分離することで、2つのパスのための結果が得られます。そのため、検索時間が2倍になります。分離単体では、マルチスレッドを使用しない場合、特に小さなnでは性能向上は望めません。

[hrenfx]

それでも、OCL（一般的な意味でのパラレリング）はアルゴリズム的な最適化ではなく、技術的な最適化なのです。

あなたの場合、最速のO(N)変解を並列化する必要性があるのかどうか疑問です。

[TheXpert]

C-4:
彼はそうする。

やだやだはない？見せてください。

では、頑張ってください。パラメータの値に線形に依存する複雑さを持つアルゴリズムの最適化について議論することは、おそらく何もしていないのでしょう。

[Vasiliy Sokolov]

TheXpert:

やだやだはない？見せてください。

とにかく、がんばってください。複雑さがパラメータの値に線形に依存するアルゴリズムの最適化について議論する - あなたは本当に何もすることがありません。

よし、アルゴリズムを完成させて、パラレリングの結果をスタジオに投稿しよう。

hrenfx

それでも、OCL（一般的な意味でのパラレリング）はアルゴリズム的な最適化ではなく、どちらかというと技術的な最適化なのです。

あなたの場合、最速のO(N)変解を並列化する必要性があるのか疑問です。

なんというか。どんな並列化も、アルゴリズムには常に重大な複雑性を伴います。さらに、データ量に線形に依存するアルゴリズムを並列化しないのであれば、他に何を並列化すればいいのでしょうか？

要するに、アルゴリズムを書き換えて、その結果どうなるかを見る。

[Andrey Khatimlianskii]

C-4:
ここでもトップとボトムを分離することで、2つのパスが存在することになります。これでは検索時間が2倍になってしまいます。分離単体では、マルチスレッドを使用しないと、特に小さなnでは性能向上は望めません。

なぜ、そう言い切れるのですか？

私のチェックでは、そうではありません。

01:29:25 SpeedTest EURUSD,M15 inputs: Interations=10000; pperiod=10;

01:29:25 SpeedTest EURUSD,M15:バーの数=3780

01:30:46 SpeedTest EURUSD,M15：オリジナル関数：81.558 秒、エクストリーム：131 / 121

01:31:10 SpeedTest EURUSD,M15：私の編集で（ブレーク）：23.291 秒、極値：131 / 121

01:31:27 SpeedTest EURUSD,M15: With my break (ブレーク):17.565 sec, extrema: 131 / 121

mq4スクリプトを添付します。

[Andrey Khatimlianskii]

もうひとつ、完成度の高いテストを。

01:38:56 SpeedTest EURUSD,M1 inputs: Interations=1000; pperiod=100;

01:38:56 SpeedTest EURUSD,M1:バー数=33896

01:50:19 SpeedTest EURUSD,M1: オリジナル関数:683.565 秒、極値: 121 / 127

01:50:54 SpeedTest EURUSD,M1: 編集あり (ブレーク): 34.383 sec, extrema: 121 / 127

01:51:16 SpeedTest EURUSD,M1: With my break (ブレーク):22.714 sec, extrema: 121 / 127

[TheXpert]

komposter:

C.T.D.さんは、最初の投稿でまさにそのことを書いています。