Есть ли более быстрый способ найти минимальное и максимальное значения?

Question

Часто я писал: {Min@#, Max@#} &

И все же это кажется неэффективным, поскольку выражение необходимо сканировать дважды, один раз, чтобы найти минимальное значение, и один раз, чтобы найти максимальное значение.Есть ли более быстрый способ сделать это?Выражение часто является тензором или массивом.

Answer 1

Это немного лучше.

minMax = Compile[{{list, _Integer, 1}},
   Module[{currentMin, currentMax},
    currentMin = currentMax = First[list];
    Do[
     Which[
      x < currentMin, currentMin = x,
      x > currentMax, currentMax = x],
     {x, list}];
    {currentMin, currentMax}],
   CompilationTarget -> "C",
   RuntimeOptions -> "Speed"];
v = RandomInteger[{0, 1000000000}, {10000000}];
minMax[v] // Timing

Я думаю, что это немного быстрее, чем версия Леонида, потому что Do немного быстрее, чем For, даже в скомпилированном коде.

В конечном счете, это пример того, какой удар по производительности вы испытываете при использовании функционального языка программирования высокого уровня.

Добавление в ответ Леониду:

Не знаюдумаю, что алгоритм может учитывать всю разницу во времени. Гораздо чаще всего, я думаю, оба теста будут применяться в любом случае.Однако разница между Do и For измерима.

cf1 = Compile[{{list, _Real, 1}},
   Module[{sum},
    sum = 0.0;
    Do[sum = sum + list[[i]]^2,
     {i, Length[list]}];
    sum]];
cf2 = Compile[{{list, _Real, 1}},
   Module[{sum, i},
    sum = 0.0;
    For[i = 1, i <= Length[list],
     i = i + 1, sum = sum + list[[i]]^2];
    sum]];
v = RandomReal[{0, 1}, {10000000}];
First /@{Timing[cf1[v]], Timing[cf2[v]]}

{0.685562, 0.898232}

Answer 2

Для массива вы можете сделать простейшую функциональную вещь и использовать

Fold[{Min[##],Max[##]}&, First@#, Rest@#]& @ data

К сожалению, это не демон скорости. Даже для коротких списков, 5 элементов, все ответы Леонида и Ответ Марка как минимум в 7 раз быстрее, не скомпилированные в v.7. Для длинных списков, 25000 элементов, это усугубляется тем, что Марк работает в 19,6 раза, но даже при такой длине это решение заняло всего около 0,05 с.

Однако я бы не стал считать {Min[#], Max[#]}& как вариант. В нескомпилированном виде он был в 1,7 раза быстрее, чем у Марка для короткого списка, и почти в 15 раз быстрее для длинных списков (соответственно, в 8 раз и почти в 300 раз быстрее, чем решение Fold).

К сожалению, я не смог получить хорошие цифры для скомпилированных версий ответов {Min[#], Max[#]}&, Леонида или Марка, вместо этого я получил множество непонятных сообщений об ошибках. На самом деле {Min[#], Max[#]}& увеличено время выполнения. Решение Fold значительно улучшилось, и заняло вдвое больше времени, чем нескомпилированные ответы Леонида.

Редактировать : для любопытства, вот некоторые временные измерения некомпилированных функций -

Каждая функция использовалась в 100 списках длины, указанной на горизонтальной оси, а среднее время в секундах - это вертикальная ось. В порядке возрастания времени кривыми являются {Min[#], Max[#]}&, ответ Марка, второй ответ Леонида, первый ответ Леонида и метод Fold сверху.

Answer 3

Я думаю, что это так же быстро, как и в практике программирования Mathematica. Единственный способ ускорить его в mma - использовать Compile с целью компиляции C, как показано ниже:

getMinMax = 
 Compile[{{lst, _Real, 1}},
   Module[{i = 1, min = 0., max = 0.},
       For[i = 1, i <= Length[lst], i++,
        If[min > lst[[i]], min = lst[[i]]];
        If[max < lst[[i]], max = lst[[i]]];];
        {min, max}], CompilationTarget -> "C", RuntimeOptions -> "Speed"]

Однако даже это, кажется, немного медленнее, чем ваш код:

In[61]:= tst = RandomReal[{-10^7,10^7},10^6];

In[62]:= Do[getMinMax[tst],{100}]//Timing
Out[62]= {0.547,Null}

In[63]:= Do[{Min@#,Max@#}&[tst],{100}]//Timing
Out[63]= {0.484,Null}

Вы, вероятно, можете написать функцию целиком на C, а затем скомпилировать и загрузить ее как dll - вы можете устранить некоторые накладные расходы таким образом, но я сомневаюсь, что вы выиграете больше, чем несколько процентов - не стоит усилий IMO.

EDIT

Интересно, что вы можете значительно увеличить скорость скомпилированного решения с помощью ручного исключения общих подвыражений (lst[[i]] здесь):

getMinMax = 
 Compile[{{lst, _Real, 1}},
   Module[{i = 1, min = 0., max = 0., temp},
     While[i <= Length[lst],
       temp = lst[[i++]];
       If[min > temp, min = temp];
       If[max < temp, max = temp];];
       {min, max}], CompilationTarget -> "C", RuntimeOptions -> "Speed"]

немного быстрее, чем {Min@#,Max@#}.

Answer 4

Для всех вас, кто проводит время, я хотел бы предупредить вас, что порядок исполнения чрезвычайно важен. Например, посмотрите на следующие два слегка различающихся тайминговых теста:

(1)

res =
 Table[
  a = RandomReal[{0, 100}, 10^8];
  {
   Min[a] // AbsoluteTiming // First, Max[a] // AbsoluteTiming // First,
   Max[a] // AbsoluteTiming // First, Min[a] // AbsoluteTiming // First
   }
  , {100}
  ]

Странный человек здесь последний Min

(2)

res =
 Table[
  a = RandomReal[{0, 100}, 10^8];
  {
   Max[a] // AbsoluteTiming // First, Min[a] // AbsoluteTiming // First,
   Min[a] // AbsoluteTiming // First, Max[a] // AbsoluteTiming // First
   }
  , {100}
  ]

Здесь самое высокое значение синхронизации найдено для первого Max, второе - самое высокое для второго max, а два Min примерно одинаковы и минимальны. На самом деле, я бы ожидал, что Max и Min займут примерно одно и то же время, но это не так. Первый, похоже, занимает на 50% больше времени, чем второй. Наличие положения полюса также, по-видимому, приводит к 50% гандикапу.

Теперь сравнение с алгоритмами, данными Марком и Леонидом:

res =
 Table[
  a = RandomReal[{0, 100}, 10^8];
  {
   {Max[a], Min[a]} // AbsoluteTiming // First,
   {Min@#, Max@#} &@a // AbsoluteTiming // First,
   getMinMax[a] // AbsoluteTiming // First,
   minMax[a] // AbsoluteTiming // First,
   {Min[a], Max[a]} // AbsoluteTiming // First
   }
  , {100}
  ]

Здесь мы находим около 0,3 с для {Max [a], Min [a]} (который включает гандикап положения полюса), уровень .1 - для метода Марка; остальные все примерно одинаковы.