0

主要な浮動小数点演算を行うプログラムの半分を作成しました。開始したデータによっては、線分を表す非常に大きな配列を生成できます。これらのライン セグメントの位置は、ラインの各端点の X、Y、Z 位置を記録するために、浮動小数点数を含むデカルト座標系を使用して記録されます。両端に X,Y,Z を使用することはできないので、最初に X,Y,Z を使用し、最後に Q,R,S を使用しました。したがって、基本的に私がやりたいことは、同一または反転したすべての行にフラグを立てて、1行目のQ、R、Sが2行目のX、Y、Zと等しくなり、1行目のX、Y、Zが等しくなるようにすることです2行目のQ、R、S。私の現在のフラグ テクニックは、X を -1 に設定することです。両方の行にフラグを立てたくありません。1 つを除くすべての行にフラグを立てます。これは私の現在の機能です：

int filter(int lines)
{
printf("Filtering...\n");
refline=0;
scanline=1;
while(refline<(lines))
    {
        if( segpointX[refline] == segpointQ[scanline] && segpointY[refline] == segpointR[scanline] && segpointZ[refline] == segpointS[scanline] && segpointQ[refline] == segpointX[scanline] && segpointR[refline] == segpointY[scanline] && segpointS[refline] == segpointZ[scanline] 
         || segpointX[refline] == segpointX[scanline] && segpointY[refline] == segpointY[scanline] && segpointZ[refline] == segpointZ[scanline] && segpointQ[refline] == segpointQ[scanline] && segpointR[refline] == segpointR[scanline] && segpointS[refline] == segpointS[scanline])
            {
                //printf("Origional: %f  %f  %f  ><  %f  %f  %f\n",segpointX[refline],segpointY[refline],segpointZ[refline],segpointQ[refline],segpointR[refline],segpointS[refline]);
                //printf("Duplicate: %f  %f  %f  ><  %f  %f  %f\n\n",segpointX[scanline],segpointY[scanline],segpointZ[scanline],segpointQ[scanline],segpointR[scanline],segpointS[scanline]);
                segpointX[scanline]=-1;
            }

         scanline++;

        if(scanline==lines+1)
            {
                refline++;
                scanline=refline+1;
            }   
    }
return(0);
}

私は自分が持っている行数を知っています。それが「行」整数です。このコードは本来どおりに機能しますが、プログラムの残りの部分に比べて非常に遅いです。これをより速く行う方法があるに違いないと思いますが、方法がわかりません。すべての浮動小数点演算を考えると信じられないほど高速なプログラムの残りの部分を引きずり出すため、この関数を使用するのは本当に残念です。これを現在よりも約 3 倍高速化する適切な方法がない場合は、めちゃくちゃなデータに対処し、次の関数を十分にスマートにして無視する必要があるかもしれません。ただし、次の関数は、データの重複を補正しようとせずに十分に複雑であるため、不良行にフラグを立てることは非常に役立ちます。

4

2 に答える 2

2

配列内の重複にフラグを立てる従来の方法は、配列を何らかの方法でソートし (O(N・logN))、1 回のパスで連続する同一要素にフラグを立てて削除する (O(N)) ことです。これは総複雑度 O(N·logN) ですが、あなたのアプローチは O(N 2 ) です。

あなたの場合、すべての困難は、データポイント間に何らかの順序関係を確立することに要約されます。

まず、同等の行 (同じエンドポイント) が同じ方法で表されるように、行の形式を正規化します。これを行うには、各行でタプル (XYZ)/(QRS) を比較します。Q が X より小さい場合、QRS は XYZ と交換されます。X==Q の場合、Y と R がチェックされ、それらが再び等しい場合は、Z と S.

この O(N) パスの最後に、同等の行はすべて同じ XYZQRS 表現を持ちます。

ここで、データの表現を変更したくない場合 (6 つの独立した配列。1 つのstructs の配列の方が単純で効率的)、実際のデータの代わりにインデックスの配列を並べ替える方が簡単です (また、実際のデータの順序を変更したくない場合は、より効率的であるか、実行可能な唯一の可能性さえあります)。0 から までの数値で整数の配列を初期化しlines-1ます。次に、qsort関数を使用して並べ替えを行い、カスタム比較関数を渡すことができます。

この関数は、比較するインデックスを受け取ります。これらのインデックスを使用して、対応する XYZ/QRS にアクセスし、それらを順番に比較します (最初の要素の X と 2 番目の要素の X を比較し、等しい場合は Y に進みます)。並べ替えの最後に、インデックス配列が並べ替えられ、同じアイテムが近くに立っています。

ここで、最後のパスを実行できます。インデックス配列をスキャンし、現在のインデックスに対応する要素を次のインデックスの要素と比較します。それらが等しい場合は、最初の要素を重複としてマークします。それ以外の場合は、重複シーケンスの最後のアイテムにいるか、新しいシーケンスの開始にいるため、(少なくとも一時的に) このアイテムを保持する必要があります。オーダー制なので、同じものがずらりと並んでいるので、ワンパスで目印を付けることができます。

これは、完全一致が必要な場合にのみ正しく機能することに注意してください。つまり、FP の不正確さは考慮されません。

于 2013-10-14T01:38:01.780 に答える
0

あなたのアルゴリズムはN^2. でこれを実行できるはずですN log N。ただし、到達するために必要な複雑さN log Nは、データによってある程度異なります。

データが X 方向に適切に分散されていると仮定して、次のようにします。

  1. X < Q になるように、必要に応じて各線分を反転します。これは O(N) です。
  2. すべての線分を X で並べ替えます。これは O(N log N) です。
  3. 重複が隣接するようになったため、単純なスキャンでそれらを削除できます。

これは 100% 正しいわけではありませんが、大まかな要旨は正しくなります。いくつかの退化したケースを処理する必要があります。

  1. あなたがすることは、フリップ段階で X==Q です。(答え。Y/Q に基づいて反転します。それも等しい場合は、Z/S を使用します)
  2. 並べ替えフェーズで 2 つのセグメントが同じ X を持っている場合はどうしますか。（答え。Y、Z、Q、R、S をこの順序で二次キーとして使用してください。）
于 2013-10-14T01:37:45.500 に答える