0

C++11 でネストされたループ再帰を克服する方法はありますか? プログラムの実行時間が遅い。むしろ、次の式を解くためのより効率的な方法はありz=|a-b|*|x-y|ますか? a、b、x、y は 10000 整数配列の要素ですか?

コードは次のとおりです。

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

ifstream in("int.in");

int main()
{
    long long n, n1, z, x, y, in2=0;
    in>>n
    long long l[n], p[n];
    for(x=0;x!=n;x++)
        in>>l[x]>>p[x];
    for(x=0;x!=n;x++)
    {
        for(y=x+1;y<n;y++)
        {
            ineq+=(abs(l[x]-l[y])*abs(p[x]-p[y]))); //executes slow
            /*n1=l[x]-l[y]; //Alternative algorithm
            if(n1<0)
                n1*=-1;
            z=p[x]-p[y];
            if(z<0)
                z*=-1;
            in2+=n1*z;*/
        }
    }
    cout<<in2<<"\n";
}

short intデータ型を、 long、long longおよびに変更しようとしましたが、unsignedガベージ値をダンプするか、「セグメンテーション コア フォールト」エラーを実行します。

絶対値式については、もともとハードコーディング（コメントアウト）でやってみたのですが、どうやらガベージ値を出力しているようです。abs()functionを使用して abs ソリューションを最適化しようとしましたineq+=abs(l[x]-l[y])*abs(p[x]-p[y]));が、実行が遅くなるようです。実装できる他の最適化については知りませんので、いくつかお勧めしてください。

Linux に適したソリューションが推奨されます。ありがとうございました。

補足: a、b、x、y の値はすべて範囲内にあります1<=a,b,x,y<=10000。

補足: このプログラムはファイル "int.in" から読み取り、最初の整数 (アイテムの数) を取り、新しい行をペアで読み取ります (l[x] と p[x] はペアです)。

補足: 多次元配列のみを使用してみましたが、1 次元配列が CPU キャッシュにあり、多次元はメモリに散らばっていて速度が遅いことをどこかで読みました。

4

1 に答える 1

1

問題は別の方法で描くことができます:式(もちろんと) で c と d (両方とも正)を探しています。z=c*dc is |a-b|d is |x-y|

したがって、最初に配列を注文します。次に、の解をz=c*d探し、どの a と b がc == a - b真になり、x と y が真になるかを見つけd == x - yます。

abs(ab) は abs(ba) と同じなので、式が真になるすべての値が得られます。

于 2015-05-06T08:53:27.203 に答える