18

誰かが私のために、私が現在使用しているものよりも効率的なデカルト積アルゴリズムを示してくれませんか（あると仮定して）。私はSOを見回して少しググったが、明らかなものが何も見えないので、何かが足りない可能性がある。

foreach (int i in is) {
   foreach (int j in js) {
      //Pair i and j
   }
}

これは、コードで行うことの非常に単純化されたバージョンです。2つの整数は、1つ以上のオブジェクトを取得するために使用されるルックアップキーであり、2つのルックアップからのすべてのオブジェクトがペアになって新しいオブジェクトになります。

はるかに大規模で複雑なシステムのこの小さなコードブロックは、データセットがスケールを超えて動作しているため、パフォーマンスの大きなボトルネックになります。これの一部は、オブジェクトの格納に使用されるデータ構造と関連するルックアップを改善することで軽減できる可能性がありますが、私が感じる主な問題は、デカルト積自体の計算です。

編集

そこで、Marcのコメントに応えて使用できるトリックがあるかどうかを確認するために、アルゴリズムの特定の使用法に関するもう少し背景を説明します。システム全体は、グラフデータのセットに対してSPARQLクエリを処理するSPARQLクエリエンジンです。SPARQLはパターンベースの言語であるため、各クエリは、グラフと照合される一連のパターンで構成されます。後続の2つのパターンに共通の変数がない（互いに素である）場合、クエリ全体の可能なソリューションのセットを取得するには、2つのパターンによって生成されたソリューションのデカルト積を計算する必要があります。パターンはいくつでも存在する可能性があり、クエリが一連の互いに素なパターンで構成されている場合、可能なソリューションでかなり指数関数的な拡張につながる可能性のあるデカルト積を複数回計算する必要があります。

どういうわけか、既存の回答から、適用できるトリックがあるかどうか疑問に思います

アップデート

そのため、デカルト積を実行する必要性を最小限に抑え、クエリエンジンを全体的に最適化するために、実装した内容に関する更新を投稿すると思いました。製品の必要性を完全に排除できるとは限らないことに注意してください。ただし、ほとんどの場合、最適化できるため、結合される2つのセットのサイズははるかに小さくなります。

トリプルパターンのセットである各BGP（基本グラフパターン）はブロックとして（本質的に）実行されるため、エンジンは最適なパフォーマンスを得るために、BGP内でパターンを自由に並べ替えることができます。たとえば、次のBGPについて考えてみます。

?a :someProperty ?b .
?c :anotherProperty ?d .
?b a :Class .

最初のパターンの結果は2番目のパターンと互いに素であり、最初の2つのパターンの結果は個々の結果のデカルト積であるため、クエリをそのまま実行するにはデカルト積が必要です。3番目のパターンは最初のパターンの可能な結果を​​制限するため、この結果には実際に必要な結果よりもはるかに多くの結果が含まれますが、この制限はその後まで適用されません。しかし、そのように再注文した場合：

?b a :Class .
?a :someProperty ?b .
?c :anotherProperty ?d .

2番目と3番目のパターンはまだばらばらであるため、最終結果を得るにはデカルト積が必要ですが、並べ替えることにより、2番目のパターンの結果のサイズを制限します。つまり、デカルト積のサイズははるかに小さくなります。

他にもさまざまな最適化がありますが、SPARQLエンジンの内部についてかなり詳細に説明し始めているので、ここではそれらを投稿しません。詳細に興味のある方は、コメントを残すか、ツイートを送ってください@RobVesse

4

6 に答える 6

34

デカルト積の複雑さはO（n 2）であり、近道はありません。

特定のケースでは、2つの軸を反復する順序が重要です。たとえば、コードが配列内のすべてのスロット（または画像内のすべてのピクセル）にアクセスしている場合は、自然な順序でスロットにアクセスするようにしてください。通常、画像は「スキャンライン」に配置されるため、Yのピクセルは隣接しています。したがって、外側のループのYと内側のXを繰り返す必要があります。

デカルト積が必要かどうか、またはより効率的なアルゴリズムであるかどうかは、解決しようとしている問題によって異なります。

于 2009-11-16T10:44:47.487 に答える
11

追加の知識がなければ、ネストされたループのパフォーマンスを実際に変更することはできませんが、それは用途によって異なります。にnアイテムがisあり、にmアイテムがjsある場合は、常にO（n * m）になります。

ただし、外観を変更することはできます。

var qry = from i in is
          from j in js
          select /*something involving i/j */;

これはまだO（n * m）ですが、LINQのわずかな余分なオーバーヘッドがあります（ただし、通常の使用では気付かないでしょう）。

あなたはあなたの場合何をしていますか？トリックがあるかもしれません...

絶対に避けるべきことの1つは、クロス結合を強制的にバッファリングすることです。このforeachアプローチは問題なく、バッファリングしません。ただし、各アイテムをに追加する場合はList<>、メモリへの影響に注意してください。同上OrderByなど（不適切に使用された場合）。

于 2009-11-16T10:45:37.407 に答える
4

O（n ^ 2）よりも優れたものを提案することはできません。これは、出力のサイズであり、したがって、アルゴリズムをこれ以上速くすることはできないためです。

私が提案できるのは、製品を計算する必要があるかどうかに別のアプローチを使用することです。たとえば、P特定の要素が製品セットに属しているかどうかを照会する場合にのみ、製品セットが必要ない場合があります。必要なのは、それが構成されているセットに関する情報だけです。

確かに（擬似コード）

bool IsInSet(pair (x,y), CartesianProductSet P)
{
   return IsInHash(x,P.set[1]) && IsInHash(y,P.set[2])
}

ここで、デカルト積は次のように計算されます。

// Cartesian product of A and B is
P.set[1]=A; P.set[2]=B;

セットをハッシュとして実装する場合、セットのデカルト積でのルックアップは、無料で入手できるハッシュmでのルックアップにすぎません。mデカルト積の構築とIsInSetルックアップにはそれぞれO(m)時間がかかります。ここで、は乗算するセットmの数であり、各セットの--sizeよりはるかに小さくなります。n

于 2009-11-16T12:36:05.283 に答える
3

質問に追加情報が追加されました。

すでに計算したものを記録して、再度重複しないようにすると、重複を回避できます。このような簿記のコスト（ハッシュマップまたは単純なリスト）は、重複を計算するコストよりも少ないと想定されます。

C＃ランタイムは非常に高速ですが、非常に手間のかかる作業の場合は、ネイティブコードを使用することをお勧めします。

また、この問題の本質的な並列性に気付くかもしれません。製品の計算が他の製品の計算に影響を与えない場合は、複数のプロセッサコアを使用して作業を並行して実行できます。ThreadPoolを見てください。QueueUserWorkItem。

于 2009-11-16T11:46:02.293 に答える
1

キャッシュの局所性（またはjを維持するために必要なローカルメモリ）が問題になる場合は、入力配列を再帰的に二等分することで、アルゴリズムをキャッシュに適したものにすることができます。何かのようなもの：

cartprod(is,istart,ilen, js,jstart,jlen) {
  if(ilen <= IMIN && jlen <= JMIN) { // base case
    for(int i in is) {
      for(int j in js) {
        // pair i and j
      }
    }
    return;
  }
  if(ilen > IMIN && jlen > JMIN) { // divide in 4
    ilen2= ilen>>1;
    jlen2= jlen>>1;
    cartprod(is,istart,ilen2,            js,jstart,jlen2);
    cartprod(is,istart+ilen2,ilen-ilen2, js,jstart,jlen2);
    cartprod(is,istart+ilen2,ilen-ilen2, js,jstart+jlen2,jlen-jlen2);
    cartprod(is,istart,ilen2,            js,jstart+jlen2,jlen-jlen2);
    return;
  }
  // handle other cases...
}

このアクセスパターンは、すべてのレベルの自動キャッシュを自動的にかなりうまく利用することに注意してください。この種の手法は、キャッシュを意識しないアルゴリズム設計と呼ばれます。

于 2009-11-16T12:23:27.377 に答える
1

JavaのようなイテレータをC＃で作成する方法はわかりませんが、私のソリューションをここからC＃に自分で転送できるかもしれません。

組み合わせが大きすぎて完全にメモリに保持できない場合は、興味深いことがあります。

ただし、コレクションを属性でフィルタリングする場合は、組み合わせを作成する前にフィルタリングする必要があります。例：

1から1000までの数字とランダムな単語があり、それらを組み合わせてから、それらの組み合わせをフィルタリングする場合、数字は20で割り切れ、単語は「d」で始まります。1000*（26 * x）=26000*になる可能性があります。検索するxの組み合わせ。

または、最初に数値をフィルタリングして、50個の数値を取得し、（均等に分散されている場合は）1文字をフィルタリングします。これは、最終的には50*x要素のみです。

于 2012-06-04T15:34:27.927 に答える