最小合計を得るための高速計算？

Question

私はこの

row1: x1 x2 x3... xn, y1,y2,...yn 
row2: x2,x3,....xj, y4,y5,...ym 
..... 
row 1 million, x6,x2,x7...xk, y2,y3,...yl 

各行のようなデータは、xとyの数一つ百万も

より各行、同じ値を有することができ、xまたはyのいくつかの数であることができる持っています。行1と行2のようにx2は共通です。

私の目標は、xとyの最小の和をどの行で見つけるかということです。 たとえば、行1の合計はsum（x1 + x2、.. + xn + y1 + y2 + ... yn）です。

徹底的な方法では動作しますが、100万回* 100万回の操作が発生するため、非常に遅くなります。 私はいくつかの巧妙な方法で動作すると信じています。

おかげ

更新：実際

上記の問題は、行列のパーティションから来:,この行列を分割するには、少なくとも5つの方法がある5x5の

1 2 3 4 5 
2 3 4 5 6 
2 3 4 5 8 
9 1 2 3 5 
1 5 2 5 6 

で以下のような行列を与えますたとえば、

1 2 | 3 4 5 
2 3 | 4 5 6 
----+------ 
2 3 | 4 5 8 
9 1 | 2 3 5 
1 5 | 2 5 6 

二つのサブマトリックス

1 2 
2 3 

と

4 5 8 
2 3 5 
2 5 6 

ので、実際に1 2 2 3 Iが参照Xであり、4 5 8 2 3 5 2 5 6私は言及Yです。 です。各行は、マトリックス内の一種の分割です。 私は明確かどうか分からないのですか？コメントを追加してください。

Answer 1

Iは、上記見ていたものとの両方の行のxとyのパターンの重なりが、そう{X1、X2、...、XN}と{Y1、Y2、... YM}

リストを与えられていることです（1、N）

におけるI、J、K、L及び所与中のO、P、Q、R（1、m）のいずれかである

行：{XI、XI + 1、... xk、1、...、xl} {yq、yq + 1、...、yr} {xk、yk + 1、...、yr}

あなたが本当に必要とするのは、行の違いとそれを比較し、オーバーラップ（同じ値を持つ部分）が同じ合計を持つので、その合計だけです。

さらに2つのリストについて教えてください。彼らは分類されていますか？ xとyのリストが行とは無関係に何であるか知っていますか？ xのリストの値がyのリストに表示されますか？彼らはどんな方法でソートされていますか？

これらのことがわかっていると、必要なものを見つけるのがずっと速くなります。

もしそうでなければ、行を歩いて重なりを判断する必要があります。

更新：

これは我々が唯一の対角線スルー分解を前提としていますが、あなたは他人を行うためのアルゴリズムを一般化することができます。

上記の例を使用すると、私たちが作業できるかどうかを確認できます。xとyのセットで数値をグループ化しています。

行1：{1} {3 4 5 6 3 4 5 8 1 2 3 5 5 2 5 6}
行2 {1 2 2 3} {4 5 8 2 3 5 2 5 6} 2番目の列からx {2 3}に、2番目の列から{2}に追加しました。
2番目の列からy {3 3 1 5}を削除し、2番目の列から{4 5 6}を削除しました。
行3 {1 2 3 2 3 4 2 3 4} {3 5 5 6} 3番目の列からx {3 4 4}に追加され、3番目の列から{2 3}に追加されます。
第3列のy {4 2 2}と第3行の{5 8}から削除しました。

注：私は合計を計算しませんでした。 n×nのマトリックM

ためので、行1

からわずかな違い、我々は1以外の行ごとに一般化する場合には（あなたは、総合計を必要としない場合は、その後のすべての行1を計算していない）

遅延行1 = 0;私< = R、及びj = 1〜J < R（ので、我々は二回カウントelemtn M（R、R）はありません）

にI = 1のためのR <のn

にはr = 2のための

デルタ行r =デルタ行（R-1）+和M（R、I）+和M（J、R） - 和M（R、NI） - 和M（NJ、R）

行1より小さい行は負の値になります。あなたは今まで見たことのある最小の行デルタを保つことができ、どのデコンパンプの合計が最小であるかを知ることができます。

これは意味がありますか？