0

私はこのようなデータを持っています

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の数は100万以上にすることができます

各行、いくつかのxまたはyは同じ値を持つことができます。たとえば、行1と行2には共通のx2があります。

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

徹底的な方法は機能しますが、100万* 100万の操作があるため、非常に遅くなります。いくつかの賢い方法があると思います。

ありがとう

アップデート：

実際、上記の問題は行列パーティションから発生します：、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

この行列を2つの部分行列に分割するには、少なくとも5つの方法があります。たとえば、

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

2つのサブマトリックスを取得します 

1 2
2 3

と

4 5 8 
2 3 5
2 5 6

したがって、実際には1 2 2 3は私が参照するxであり、4 5 8 2 3 5 256は私が言及するyです。したがって、各行はマトリックス内の一種の分割です。はっきりしているかどうかわかりませんか？コメントを追加してください。

4

1 に答える 1

0

上で見たところ、xとyのパターンが両方の行で重なっているので、リスト{x1、x2、... xn}と{y1、y2、..ym}が与えられます。

（1、n）でi、j、k、lが与えられる

およびo、p、q、r in（1、m）

1行目は次のとおりです。{xi、xi + 1、...、xj} {yo、yo + 1、...、yp}

2行目は次のとおりです。{xk、xk + 1、...、xl} {yq、yq + 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}なので、x{に追加しました2列目から23}、2行目から{2}。
yから{331 5}を2番目の列から、{4 5 6}を2番目の行から削除しました。
行3：{1 2 3 2 3 4 2 3 4} {3 5 5 6}なので、x{に追加しました。 3番目の列から344}、3番目の行から{23}。
yから{422}を3番目の列から削除し、{58}を3番目の行から削除しました

合計を計算しなかったことに注意してください。行1との違い

したがって、1以外の各行を一般化する場合（合計が必要ない場合は、行1をまったく計算しないでください）

nxnマトリックMの場合

delat行1=0;

r=2からr<nの場合

i=1からi<=r、およびj =1からj<rの場合（したがって、elemtn M（r、r）を2回カウントしません）

デルタ行r=デルタ行（r-1）+合計M（r、i）+合計M（j、r）-合計M（r、ni）-合計M（nj、r）

行1よりも小さい行は負になります。これまでに見た中で最小の行デルタを維持するだけで、どのデコンプ合計が最小であるかがわかります。

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

于 2012-05-01T12:16:37.690 に答える