代码之家 › 专栏 › 技术社区 › dreeves

无For循环的单调化(列表咀嚼)

wolfram-mathematica for-loop loops functional-programming list

dreeves · 技术社区 · 14 年前

Mathematica代码中的For或While循环总是让我觉得有点脏,但我很困惑自己试图做一些列表,像咀嚼所有函数一样,并诉诸于此:

(* # Given a list of {x,y} pairs, transform the data as follows: every time 
   # there's a decrease in y-value from one datapoint to the next, say {x1,Y} 
   # followed by {x2,y}, add Y to the value of every datapoint on or after x2. *)
monotonify[data_] := Module[{data0, i, offset = 0},
  data0 = data;
  For[i = 2, i <= Length[data], i++,
    If[data[[i-1,2]] > data[[i,2]], offset += data[[i-1,2]]];
    data0[[i]] += {0,offset}];
  data0]

(把y值想象成里程表读数,有时里程表会意外复位——很明显,因为这个值会降低,里程表不应该这样做。因此,我们通过将每次重置前的最后已知值与所有未来值相加来转换读数。)

你如何用一种好的函数式风格来写单调化?

(事实上我不认为以上是循环 非常好 可能是轻度强迫症。)

5 回复 | 直到 14 年前

High Performance Mark 14 年前

好的,现在我已经按照最初的要求修改了处理输入的方法。

从示例数据集开始:

dataset = {{a, 1}, {b, 2}, {c, 3}, {d, 4}, {e, 5}, {f, 0}, {g, 4}, 
{h,5}, {i, 6}, {j, 7}, {k, 4}, {l, 7}, {m, 8}, {n, 9}, {o, 0}, {p,2}, 
{q, 3}};

接受转置:

trDataset = Transpose[dataset];

接下来是一个仅对Y值操作的函数:

trDataset[[2]] = FoldList[Plus, dataset[[1, 2]], Map[Max[#, 0] &, Differences[dataset[[All, 2]]]]]

撤消换位:

dataset = Transpose[trDataset]

现在输出是

{{a, 1}, {b, 2}, {c, 3}, {d, 4}, {e, 5}, {f, 5}, {g, 9}, {h, 10}, {i, 
  11}, {j, 12}, {k, 12}, {l, 15}, {m, 16}, {n, 17}, {o, 17}, {p, 
  19}, {q, 20}}

我还没有测试这个解决方案的性能。

编辑: 好吧,这是解决问题的基础,我把剩下的工作留给你@dreeves。这个版本的单调化只对一个数字列表起作用,我还没有把它集成到我之前的建议中,来处理你的输入。

monotonify[series_] := 
 Split[series, Less] //. {a___, x_List, y_List, z___} /; 
     Last[x] > First[y] -> {a, x, y + Last[x], z} // Flatten

编辑2: 另一个作用于数字列表的函数。这比我以前的尝试快得多。

monotonify[series_] := 
Accumulate[Flatten[Map[Flatten[{#[[1]], Differences[#]}] &, 
       Split[series, Less]]]]

sakra 14 年前

下面是另一个解决方案:

Module[{corr, lasts},
 lasts = data[[All, 2]]; 
 corr = Prepend[Accumulate[MapThread[If[#1 > #2, #1, 0] &, {Most[lasts], Rest[lasts]}]], 0];
 Transpose[{data[[All, 1]], lasts + corr}]]

它计算校正矢量,然后将其添加到给定数据点的y值。

dreeves 14 年前

一旦挑战结束,我就无法尝试,但我觉得For loop版本更简单:

mon00[{prev_,offset_}, next_] := {next, offset + If[prev > next, prev, 0]}
monotonify0[list_] := list + Rest[FoldList[mon00, {-Infinity,0}, list]][[All,2]]
monotonify[data_] := Transpose@{#1, monotonify0[#2]}& @@ Transpose@data

其思想是编写一个helper函数,该函数只对y值的一个简单列表执行此操作,然后使用双转置习惯用法对数据的第二列执行操作。

双转置习语的方便参考

用于转换矩阵中的特定列,例如,用transformElement[x]替换4列矩阵第2列中的每个值x:

{#1, transformElement[#2], #3, #4}& @@@ matrix

如果需要使用将整列作为列表的函数转换列,请使用以下习惯用法:

Transpose @ {#1, transformList[#2], #3, #4}& @@ Tranpose@matrix

Pillsy 14 年前

我用了很多 Split , Flatten 和 Accumulate . 我不确定最终结果比 For 循环,但如果重要的话,应该是又快又好。

monotonize[list_] := 
  With[{splits = Split[list, LessEqual]},
   With[{diffs = Most[Last /@ splits] - Rest[First /@ splits]},
    Flatten[
      MapThread[Plus, {Accumulate[Prepend[diffs, 0]], splits}],
     1]]];

monotonizeSecond[list_] :=
  With[{firsts = First /@ list, lasts = Last /@ list},
   Transpose[{firsts, monotonize@lasts}]];

我认为 With 比依赖匿名函数的解决方案更加清晰。也, monotonize 似乎在“未修饰”列表中是有用的,所以我将其作为一个单独的函数进行了分解。

Davorak 14 年前

从根本上说,Mathematica中的大多数函数运算符一次只能操作列表中的一个元素。这不是唯一的选项,但是这些函数可以设置为一次获取列表中的两个相邻元素,这个假设函数将使获得所需结果变得很简单。

不用转换函数,我们可以使用分区轻松地转换数据。

Clear[monotonify];
monotonify[data_] := 
 Transpose[{data[[All, 1]], 
  Rest@FoldList[
    If[#2[[1]] < #2[[2]], #1 + #2[[2]] - #2[[1]], #1 + #2[[2]]] &, 0, 
    Partition[data[[All, 2]], 2, 1, {2, -1}, 0]]}]

我对这个版本进行了重构,添加了一个helper函数,以明确该函数是如何折叠的,但是mathematica并没有对其进行优化。

Clear[monotonify, m00];
m00[acc_, {prev_, next_}] := 
 If[prev < next, acc + next - prev, acc + next]
monotonify[data_] := 
 Transpose[{data[[All, 1]], 
  Rest@FoldList[m00, 0, Partition[data[[All, 2]], 2, 1, {2, -1}, 0]]}]

编辑:忘记一些{}