10

Mathematica で適切に高速なビニングアルゴリズムを開発するのに苦労しています. T={{x1,y1,z1},{x2,y2,z2},....} という形式の大規模な (~100k 要素) データ セットがあり、それを 2D 配列にビン化したい100x100 ビン。ビン値は、各ビンに分類される Z 値の合計によって与えられます。

現在、テーブルの各要素を反復処理しており、Select を使用して、ビン境界のリストに基づいてどのビンにあると想定されているかを選択し、そのビンを占める値のリストに z 値を追加しています。最後に、Total をビンのリストにマップし、それらの内容を合計します (これを行うのは、最大化などの他のことをしたい場合があるためです)。

これを行うために Gather などの関数を使用してみましたが、おそらく Gather の使用が不十分であるにもかかわらず、上記の方法はとてつもなく高速でした。とにかく、私の方法で並べ替えを行うにはまだ数分かかりますが、Mathematica の方がうまくいくと思います。誰かが便利な効率的なアルゴリズムを持っていますか?

4

4 に答える 4

12

これは、Szabolcs の投稿に基づく方法で、約 1 桁高速です。

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 重複した位置を追加します。

于 2011-11-20T17:37:38.310 に答える
5

Szabolcs の読みやすさに関する懸念から、以下のコードを書き直すつもりです。それまでは、ビンが規則的で、の代わりにRound、Floor、またはCeiling(2 番目の引数で) を使用できる場合、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]
于 2011-11-18T07:21:22.797 に答える
4

これが私のアプローチです：

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

(* approach 1: create bin-matrix first, then fill up elements by adding  zvalues *)
res1 = Module[
    {result = ConstantArray[0, {100, 100}]},
    Do[
      AddTo[result[[##]], zvalues[[i]]] & @@ indexes[[i]], 
      {i, Length[indexes]}
    ];
    result
    ]; // Timing

(* approach 2: gather zvalues by indexes, add them up, convert them to a matrix *)
res2 = Module[{gb = GatherBy[Transpose[{indexes, zvalues}], First]},
    SparseArray[gb[[All, 1, 1]] -> (Total /@ gb[[All, All, 2]])]
    ]; // Timing

res1 == res2

これら 2 つのアプローチ ( res1& res2) は、このマシンでそれぞれ 1 秒あたり 100k と 200k の要素を処理できます。これは十分に速いですか、それともこのプログラム全体をループで実行する必要がありますか?

于 2011-11-18T08:30:15.990 に答える
3

これは、Mathematica ツール バッグの中身で定義されている関数 SelectEquivalents を使用した私のアプローチです。これは、このような問題に最適です。

data = RandomReal[100, {75, 3}];
bins = Range[0, 100, 20];
binMiddles = (Most@bins + Rest@bins)/2;
nearest = Nearest[binMiddles];

SelectEquivalents[
   data
   ,
   TagElement -> ({First@nearest[#[[1]]], First@nearest[#[[2]]]} &)
   ,
   TransformElement -> (#[[3]] &)
   ,
   TransformResults -> (Total[#2] &)
   ,
   TagPattern -> Flatten[Outer[List, binMiddles, binMiddles], 1]
   , 
   FinalFunction -> (Partition[Flatten[# /. {} -> 0], Length[binMiddles]] &)
]

2つ以上の次元に従ってグループ化したい場合は、FinalFunctionでこの関数を使用して、リスト結果に目的の次元を与えることができます(どこで見つけたか覚えていません)。

InverseFlatten[l_,dimensions_]:= Fold[Partition[#, #2] &, l, Most[Reverse[dimensions]]];
于 2011-11-18T13:40:43.820 に答える