wolfram-mathematica - 在Mathematica中对稀疏数组的有效替代(Outer)吗？

Question

假设我有两个非常大的列表{a1，a2，…}和{b1，b2，…}，其中所有ai和bj都是大的稀疏数组。为了提高内存效率，我将每个列表存储为一个综合的稀疏数组。

现在，我想在ai和bj的所有可能对上计算一些函数f，其中每个结果f [ai，bj]再次是稀疏数组。顺便说一下，所有这些稀疏数组都具有相同的维数。

尽管

Flatten[Outer[f, {a1, a2, ...}, {b1, b2, ...}, 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似乎在计算过程中也会消耗太多内存。

Answer 1

我将提出一种解决方案，该解决方案相当复杂，但在计算过程中只允许使用大约两倍于将最终结果存储为SparseArray所需的内存。为此付出的代价将是执行速度大大降低。

编码

稀疏数组构造/解构API

这是代码。首先，略微修改(以解决高维稀疏数组)的稀疏数组构造-解构API，取自this answer:

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，但是出于我们的目的，这不是主要的问题。

这是一个更专业的版本，它为二维索引对生成插入器。

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}}

，我们将使用第二种形式。

SparseArray-构建功能

该函数将通过获取数据块(也是 SparseArray形式)并将它们粘合在一起来迭代地构建 SparseArray对象。它基本上是 this答案中使用的代码，打包成一个函数。它接受用于生成下一个数据块的代码段，并包装在 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 -s中提取一对以上的元素，以加快代码的速度。我们一次处理的对数由可选的 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

对于此特定示例，建议的方法比直接使用 Outer的内存效率高5倍，但速度要慢15倍。我必须调整 chunksize参数(默认值为 100，但是对于上述情况，我使用 2000来获得最佳速度/内存使用组合)。我的方法仅将峰值用作存储最终结果所需内存的两倍。与基于 Outer的方法相比，内存节省的程度将取决于所讨论的稀疏数组。