Mathematica如何使用排序函数有效地找到最小值

Question

我有以下数据对列表:

pairs = {{3, "John"}, {1, "Bob"}, {2, "Jane"}, {1, "Beth"}};

我想找到具有最小第一个值的数据对.在上面的示例中,我正在寻找的是:{1, "Bob"}或者{1, "Beth"},但不是两者.

我可以Sort[pairs, #1[[1]] < #2[[1]] &][[1]]用来完成这个.然而,由于即使是速度最快的O> O(n),也让我觉得必须有一种更有效的方法来做到这一点.

以下给出了正确的答案:

minPair = pairs[[1]];
Map[Function[x, If[x[[1]] < minPair[[1]], minPair = x]], pairs];
minPair;

但是,它比Sort上面的使用慢.我知道,我的Mathematica-fu还没有,所以我的问题.

计时

SetAttributes[TimingDo, HoldRest];
TimingDo[note_String, func_] := 
  results = 
   Append[results, {note , func, Timing[Do[func, {iterations}]][[1]]}];

pairs = {{3, "John"}, {1, "Bob "}, {2, "Jane"}, {1, "Beth"}};
results = {};
iterations = 10000;

TimingDo[ "mmorris[Sort]:               ",
  Sort[pairs, #1[[1]] < #2[[1]] &][[1]]];

TimingDo["mmorris[Map]:                ",
  minPair = pairs[[1]];
  Map[Function[x, If[x[[1]] < minPair[[1]], minPair = x;]], pairs];
  minPair];

TimingDo["mmorris[Map2]:               ",
  minPair = pairs[[1]];
  minValue = minPair[[1]];
  Map[Function[x, 
    If[x[[1]] < minValue, minPair = x; minValue = minPair[[1]];]], 
   pairs];
  minPair];

TimingDo["Mike Honeychurch[Position]:  ",
  pairs[[Position[pairs, Min[pairs[[All, 1]]]][[1, 1]]]]];

TimingDo["Mike Honeychurch[Ordering]:  ",
  pairs[[First@Ordering[pairs[[All, 1]]]]]];

TimingDo["Mike Honeychurch[Ordering']: ",
  pairs[[First@Ordering[pairs[[All, 1]], 1]]]];

TimingDo["Mike Honeychurch[SortBy]:    ",
  SortBy[pairs, First][[1]]];

cf = Compile[{{in, _Integer, 1}}, Block[{x, pos}, x = Part[in, 1];
    pos = 0;
    Do[If[Part[in, i] < x, x = Part[in, i];
       pos = i;];, {i, Length[in]}];
    pos]];

TimingDo["ruebenko[Compile]:           ",
  {p1, p2} = Developer`ToPackedArray /@ Transpose[pairs];
  pairs[[cf[p1]]]];

TimingDo[ "ruebenko[Ordering]:          ",
  {p1, p2} = Developer`ToPackedArray /@ Transpose[pairs];
  pairs[[Ordering[p1][[1]]]]];

TimingDo["TomD[Select]:                ",
  Select[pairs, #[[1]] == Min[pairs[[All, 1]]] &, 1][[1]]];

TimingDo["TomD[Function]:              ",
  (Function[xx, Select[xx, #[[1]] == Min[xx[[All, 1]]] &, 1]]@
     pairs)[[1]]];

Map[Print, Sort[results, #1[[3]] < #2[[3]] &]];

结果(清单大小为4)

pairs = {{3, "John"}, {1, "Bob "}, {2, "Jane"}, {1, "Beth"}};

{Mike Honeychurch[Ordering']: ,{1,Bob },0.01381}

{Mike Honeychurch[Ordering]:  ,{1,Bob },0.016171}

{Mike Honeychurch[SortBy]:    ,{1,Beth},0.036649}

{TomD[Select]:                ,{1,Bob },0.042448}

{Mike Honeychurch[Position]:  ,{1,Bob },0.042909}

{ruebenko[Ordering]:          ,{1,Bob },0.048088}

{ruebenko[Compile]:           ,{1,Bob },0.050277}

{TomD[Function]:              ,{1,Bob },0.054296}

{mmorris[Sort]:               ,{1,Beth},0.06838}

{mmorris[Map2]:               ,{1,Bob },0.117905}

{mmorris[Map]:                ,{1,Bob },0.119051}

结果(清单大小1000)

pairs = RandomInteger[1000, {1000, 2}];

{Mike Honeychurch[Ordering']: ,{0,217},0.236041}

{ruebenko[Compile]:           ,{0,217},0.416627}

{ruebenko[Ordering]:          ,{0,217},0.675427}

{Mike Honeychurch[Ordering]:  ,{0,217},0.771243}

{Mike Honeychurch[SortBy]:    ,{0,217},2.68054}

{Mike Honeychurch[Position]:  ,{0,217},2.70455}

{mmorris[Map2]:               ,{0,217},26.7715}

{mmorris[Map]:                ,{0,217},29.8413}

{mmorris[Sort]:               ,{0,217},98.1023}

{TomD[Function]:              ,{0,217},115.968}

{TomD[Select]:                ,{0,217},116.78}

Answer 1

你可以找到这样的所有最小值:

pos = Position[pairs, Min[pairs[[All, 1]]]]

pairs[[pos[[All, 1]]]]

如果你只想要其中一个

pos = Position[pairs, Min[pairs[[All, 1]]]][[1, 1]]

pairs[[pos]]

在我的机器上,这比你问题中列出的方法更快,我希望它对于更大的列表来说要快得多.

编辑

实际上这更快 - 对于你的小清单.

pos = First@Ordering[pairs[[All, 1]]];
pairs[[pos]]

最好在您的真实生活列表中测试所有这些以确定时间.(注意也SortBy[pairs,First]快于Sort)