9

2 つの非常に大きなリスト {a1, a2, …} と {b1, b2, …} があり、すべての ai と bj が大きな疎配列であるとします。メモリ効率のために、各リストを 1 つの包括的なスパース配列として格納します。

ここで、各結果 f[ai, bj] が再びスパース配列である ai と bj のすべての可能なペアに対して関数 f を計算したいと思います。ちなみに、これらのスパース配列はすべて同じ次元です。

その間

Flatten[Outer[f, {a1, a2, ...}, {b1, b2, ...}, 1], 1]

必要な結果を返します (原則として) 過剰な量のメモリを消費しているように見えます。特に、戻り値は疎配列のリストであるのに対し、私の関心のあるケースでは、1 つの包括的な疎配列の方がはるかに効率的であることがわかります。

上記の の使用に代わる効率的な方法はありOuterますか?

より具体的な例:

{SparseArray[{{1, 1, 1, 1} -> 1, {2, 2, 2, 2} -> 1}],
 SparseArray[{{1, 1, 1, 2} -> 1, {2, 2, 2, 1} -> 1}],
 SparseArray[{{1, 1, 2, 1} -> 1, {2, 2, 1, 2} -> 1}],
 SparseArray[{{1, 1, 2, 2} -> -1, {2, 2, 1, 1} -> 1}],
 SparseArray[{{1, 2, 1, 1} -> 1, {2, 1, 2, 2} -> 1}],
 SparseArray[{{1, 2, 1, 2} -> 1, {2, 1, 2, 1} -> 1}],
 SparseArray[{{1, 2, 2, 1} -> -1, {2, 1, 1, 2} -> 1}],
 SparseArray[{{1, 2, 2, 2} -> 1, {2, 1, 1, 1} -> 1}]};
ByteCount[%]

list = SparseArray[%%]
ByteCount[%]

Flatten[Outer[Dot, list, list, 1], 1];
ByteCount[%]
list1x2 = SparseArray[%%]
ByteCount[%]

Flatten[Outer[Dot, list1x2, list, 1], 1];
ByteCount[%]
list1x3 = SparseArray[%%]
ByteCount[%]

Outer(スパース配列のリスト)の未加工の中間結果が非常に非効率的であるだけでなくOuter、計算自体でも大量のメモリを消費しているようです。

4

3 に答える 3

5

かなり複雑ですが、最終結果をとして保存するために必要なメモリの2倍のメモリしか使用できないソリューションを提案しますSparseArray。これに支払う代償は、実行がはるかに遅くなります。

コード

スパース配列の構築/分解API

これがコードです。まず、(高次元のスパース配列に対処するために)わずかに変更されたスパース配列の構築-この回答から取得した脱構築API :

ClearAll[spart, getIC, getJR, getSparseData, getDefaultElement, 
  makeSparseArray];
HoldPattern[spart[SparseArray[s___], p_]] := {s}[[p]];
getIC[s_SparseArray] := spart[s, 4][[2, 1]];
getJR[s_SparseArray] := spart[s, 4][[2, 2]];
getSparseData[s_SparseArray] := spart[s, 4][[3]];
getDefaultElement[s_SparseArray] := spart[s, 3];
makeSparseArray[dims_List, jc_List, ir_List, data_List, defElem_: 0] :=
   SparseArray @@ {Automatic, dims, defElem, {1, {jc, ir}, data}};

イテレータ

次の関数はイテレータを生成します。イテレータは、反復プロセスをカプセル化するための優れた方法です。

ClearAll[makeTwoListIterator];
makeTwoListIterator[fname_Symbol, a_List, b_List] :=
  With[{indices = Flatten[Outer[List, a, b, 1], 1]},
   With[{len  = Length[indices]},
    Module[{i = 0},
      ClearAll[fname];
      fname[] := With[{ind = ++i}, indices[[ind]] /; ind <= len];
      fname[] := Null;
      fname[n_] := 
        With[{ind = i + 1}, i += n; 
           indices[[ind ;; Min[len, ind + n - 1]]] /; ind <= len];
      fname[n_] := Null;
 ]]];

上記の関数をより多くのメモリに実装できた可能性があることに注意してください-効率的に使用Outerしないでください。しかし、私たちの目的では、これは大きな問題にはなりません。

これは、2次元インデックスのペアのインターレーターを生成する、より特殊なバージョンです。

ClearAll[make2DIndexInterator];
make2DIndexInterator[fname_Symbol, i : {iStart_, iEnd_}, j : {jStart_, jEnd_}] :=
   makeTwoListIterator[fname, Range @@ i, Range @@ j];
 make2DIndexInterator[fname_Symbol, ilen_Integer, jlen_Integer] :=
   make2DIndexInterator[fname, {1, ilen}, {1, jlen}];

これがどのように機能するかです:

In[14]:= 
makeTwoListIterator[next,{a,b,c},{d,e}];
next[]
next[]
next[]

Out[15]= {a,d}
Out[16]= {a,e}
Out[17]= {b,d}

これを使用して、バッチ結果を取得することもできます。

In[18]:= 
makeTwoListIterator[next,{a,b,c},{d,e}];
next[2]
next[2]

Out[19]= {{a,d},{a,e}}
Out[20]= {{b,d},{b,e}}

、およびこの2番目の形式を使用します。

SparseArray-ビルド関数

SparseArrayこの関数は、データのチャンク(これもSparseArrayフォームで)を取得し、それらを結合することによって、オブジェクトを繰り返し構築します。これは基本的にこの回答で使用されるコードであり、関数にパッケージ化されています。これは、ラップされた次のデータチャンクを生成するために使用されるコードピースを受け入れますHold(代わりにそれを作成することもできますHoldAll

Clear[accumulateSparseArray];
accumulateSparseArray[Hold[getDataChunkCode_]] :=
  Module[{start, ic, jr, sparseData, dims, dataChunk},
   start = getDataChunkCode;
   ic = getIC[start];
   jr = getJR[start];
   sparseData = getSparseData[start];
   dims = Dimensions[start];
   While[True, dataChunk = getDataChunkCode;
     If[dataChunk === {}, Break[]];
     ic = Join[ic, Rest@getIC[dataChunk] + Last@ic];
     jr = Join[jr, getJR[dataChunk]];
     sparseData = Join[sparseData, getSparseData[dataChunk]];
     dims[[1]] += First[Dimensions[dataChunk]];
   ];
   makeSparseArray[dims, ic, jr, sparseData]];

すべてを一緒に入れて

この関数がメインの関数であり、すべてをまとめています。

ClearAll[sparseArrayOuter];
sparseArrayOuter[f_, a_SparseArray, b_SparseArray, chunkSize_: 100] := 
  Module[{next, wrapperF, getDataChunkCode},
    make2DIndexInterator[next, Length@a, Length@b];
    wrapperF[x_List, y_List] := SparseArray[f @@@ Transpose[{x, y}]];
    getDataChunkCode :=
      With[{inds = next[chunkSize]},
         If[inds === Null, Return[{}]];
         wrapperF[a[[#]] & /@ inds[[All, 1]], b[[#]] & /@ inds[[All, -1]]]
      ];
    accumulateSparseArray[Hold[getDataChunkCode]]
  ];

ここでは、最初に、要素を抽出するために使用されるインデックスペアリストのオンデマンド部分を提供するイテレータを生成します(またSparseArrays)。SparseArrayコードを高速化するために、通常、一度に2つの大きな入力から複数の要素のペアを抽出することに注意してください。一度に処理するペアの数は、オプションのchunkSizeパラメーター(デフォルトは。)によって制御されます100。次に、これらの要素を処理するコードを作成し、結果をに戻します。SparseArrayここで、補助関数を使用しますwrapperF。イテレータの使用は絶対に必要というわけではありませんが(他の回答と同様に、代わりにReap-を使用できSowます)、反復のロジックをスパース配列の一般的な累積のロジックから切り離すことができました。

ベンチマーク

まず、大規模なスパースアレイを準備し、機能をテストします。

In[49]:= 
arr = {SparseArray[{{1,1,1,1}->1,{2,2,2,2}->1}],SparseArray[{{1,1,1,2}->1,{2,2,2,1}->1}],
SparseArray[{{1,1,2,1}->1,{2,2,1,2}->1}],SparseArray[{{1,1,2,2}->-1,{2,2,1,1}->1}],
SparseArray[{{1,2,1,1}->1,{2,1,2,2}->1}],SparseArray[{{1,2,1,2}->1,{2,1,2,1}->1}]};

In[50]:= list=SparseArray[arr]
Out[50]= SparseArray[<12>,{6,2,2,2,2}]

In[51]:= larger = sparseArrayOuter[Dot,list,list]
Out[51]= SparseArray[<72>,{36,2,2,2,2,2,2}]

In[52]:= (large= sparseArrayOuter[Dot,larger,larger])//Timing
Out[52]= {0.047,SparseArray[<2592>,{1296,2,2,2,2,2,2,2,2,2,2}]}

In[53]:= SparseArray[Flatten[Outer[Dot,larger,larger,1],1]]==large
Out[53]= True

In[54]:= MaxMemoryUsed[]
Out[54]= 21347336

次に、電力テストを行います

In[55]:= (huge= sparseArrayOuter[Dot,large,large,2000])//Timing
Out[55]= {114.344,SparseArray[<3359232>,{1679616,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2}]}

In[56]:= MaxMemoryUsed[]
Out[56]= 536941120

In[57]:= ByteCount[huge]
Out[57]= 262021120

In[58]:= (huge1 = Flatten[Outer[Dot,large,large,1],1]);//Timing
Out[58]= {8.687,Null}

In[59]:= MaxMemoryUsed[]
Out[59]= 2527281392

この特定の例では、提案された方法は、を直接使用するよりも5倍メモリ効率が高くなりますがOuter、約15倍遅くなります。パラメータを微調整する必要がありましたchunksize(デフォルトはですが100、上記では2000、最適な速度とメモリ使用の組み合わせを取得するためにを使用しました)。私の方法では、最終結果を保存するために必要なメモリの2倍のメモリをピーク値として使用しました。ベースの方法と比較した場合のメモリ節約の程度はOuter、問題のスパース配列によって異なります。

于 2011-12-22T19:58:25.830 に答える
0

lst1lst2があなたのリストである場合、

Reap[
   Do[Sow[f[#1[[i]], #2[[j]]]],
       {i, 1, Length@#1},
       {j, 1, Length@#2}
       ] &[lst1, lst2];
   ] // Last // Last

仕事をし、よりメモリ効率が良いかもしれません。一方で、そうではないかもしれません。ナセルは正しいです、明示的な例が役立つでしょう。

編集:ナセルのランダムに生成された配列を使用すると、の場合len=200MaxMemoryUsed[]このフォームには170MBが必要Outerであるのに対し、質問のフォームには435MBが必要であることを示しています。

于 2011-12-21T21:21:59.127 に答える
0

サンプルデータを使用すると、非常に役立つlist機能を見つけることができると思います。AppendSparseArray

acc = SparseArray[{}, {1, 2, 2, 2, 2, 2, 2}]

Do[AppendTo[acc, i.j], {i, list}, {j, list}]

Rest[acc]

Rest結果の最初のゼロで満たされたテンソルを削除する必要があります。シードの 2 番目の引数はSparseArray、プレフィックス1. SparseArrayパフォーマンスを最適化するには、シードの背景を明示的に指定する必要がある場合があります。

于 2011-12-22T02:19:34.563 に答える