Mathematica快速2D分级算法

Question

我在Mathematica中开发适当快速的分箱算法时遇到了一些麻烦.我有一个大的(~100k元素)数据集,形式为T = {{x1,y1,z1},{x2,y2,z2},....}我希望将其合并为一个2D数组100x100箱,箱值由落入每个箱柜的Z值之和给出.

目前,我正在遍历表的每个元素,使用Select根据bin边界列表选择它应该位于哪个bin中,并将z值添加到占用该bin的值列表中.最后,我将Total映射到箱子列表,总结其内容(我这样做是因为我有时想做其他事情,比如最大化).

我已经尝试过使用Gather和其他类似的函数来做到这一点,但上面的方法速度非常快,不过可能我使用Gather很差.无论如何,通过我的方法进行排序还需要几分钟,我觉得Mathematica可以做得更好.有没有人有一个很好的高效算法方便吗？

Answer 1

这是一个基于Szabolcs帖子的方法,大约快一个数量级.

data = RandomReal[5, {500000, 3}];
(*500k values*)
zvalues = data[[All, 3]];

epsilon = 1*^-10;(*prevent 101 index*)
(*rescale and round (x,y) coordinates to index pairs in the 1..100 range*)
indexes = 1 + Floor[(1 - epsilon) 100 Rescale[data[[All, {1, 2}]]]];

res2 = Module[{gb = GatherBy[Transpose[{indexes, zvalues}], First]}, 
    SparseArray[
     gb[[All, 1, 1]] -> 
      Total[gb[[All, All, 2]], {2}]]]; // AbsoluteTiming

给出{2.012217,Null}

AbsoluteTiming[
 System`SetSystemOptions[ 
  "SparseArrayOptions" -> {"TreatRepeatedEntries" -> 1}];
 res3 = SparseArray[indexes -> zvalues];
 System`SetSystemOptions[ 
  "SparseArrayOptions" -> {"TreatRepeatedEntries" -> 0}];
 ]

给出{0.195228,Null}

res3 == res2
True

"TreatRepeatedEntries" - > 1添加重复的位置.

Answer 2

由于Szabolcs的可读性问题,我打算重写下面的代码.在此之前,要知道如果您的垃圾箱是常规的,并且您可以使用Round,Floor或Ceiling(使用第二个参数)代替Nearest,下面的代码将会更快.在我的系统上,它的测试速度比GatherBy发布的解决方案更快.

假设我理解你的要求,我建议:

data = RandomReal[100, {75, 3}];

bins = {0, 20, 40, 60, 80, 100};

Reap[
  Sow[{#3, #2}, bins ~Nearest~ #] & @@@ data,
  bins,
  Reap[Sow[#, bins ~Nearest~ #2] & @@@ #2, bins, Tr@#2 &][[2]] &
][[2]] ~Flatten~ 1 ~Total~ {3} // MatrixForm

重构:

f[bins_] := Reap[Sow[{##2}, bins ~Nearest~ #]& @@@ #, bins, #2][[2]] &

bin2D[data_, X_, Y_] := f[X][data, f[Y][#2, #2~Total~2 &] &] ~Flatten~ 1 ~Total~ {3}

使用:

bin2D[data, xbins, ybins]