Каков наилучший способ получить минимальное или максимальное значение из массива чисел?

Question

Допустим, у меня есть массив чисел: [2,3,3,4,2,2,5,6,7,2]

Каков наилучший способ найти минимальное или максимальное значение в этом массиве?

Прямо сейчас, чтобы получить максимум, я перебираю массив и сбрасываю переменную в значение, если оно больше существующего значения:

var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];

var maxValue:Number = 0;

for each (var num:Number in myArray)
{
    if (num > maxValue)
        maxValue = num;
}

Это не самый лучший способ сделать это (я стараюсь избегать циклов, когда это возможно).

Answer 1

Все остальные теоретические ответы аккуратны, но давайте будем прагматичны. ActionScript предоставляет необходимые инструменты, чтобы вам даже не пришлось писать цикл в этом случае!

Во-первых, обратите внимание, что Math.min() и Math.max() могут принимать любое количество аргументов. Кроме того, важно понимать метод apply(), доступный для Function объектов. Это позволяет передавать аргументы функции, используя Array. Давайте воспользуемся преимуществом обоих:

var myArray:Array = [2,3,3,4,2,2,5,6,7,2];
var maxValue:Number = Math.max.apply(null, myArray);
var minValue:Number = Math.min.apply(null, myArray);

Вот лучшая часть: «цикл» фактически выполняется с использованием собственного кода (внутри Flash Player), поэтому он быстрее, чем поиск минимального или максимального значения с использованием чистого цикла ActionScript.

Answer 2

Нет надежного способа получить минимум / максимум без проверки каждого значения. Вы не хотите пробовать сортировку или что-то в этом роде, обход массива - это O (n), что лучше, чем любой алгоритм сортировки в общем случае.

Answer 3

Если

1. Массив не отсортирован
2. Нахождение минимума и максимума выполняется одновременно

Тогда есть алгоритм, который находит минимальное и максимальное значения в 3n / 2 числах сравнений. Что нужно сделать, это обработать элементы массива в парах. Большее из пары следует сравнивать с текущим значением max, а меньшее из пары следует сравнивать с текущим значением min. Кроме того, необходимо соблюдать особую осторожность, если массив содержит нечетное количество элементов.

В коде c ++ (заимствование некоторого кода из Mehrdad).

struct MinMax{
   int Min,Max;
}

MinMax FindMinMax(int[] array, int start, int end) {
   MinMax  min_max;
   int index;
   int n = end - start + 1;//n: the number of elements to be sorted, assuming n>0
   if ( n%2 != 0 ){// if n is odd

     min_max.Min = array[start];
     min_max.Max = array[start];

     index = start + 1;
   }
   else{// n is even
     if ( array[start] < array[start+1] ){
       min_max.Min = array[start];
       min_max.Max = array[start+1];
     }
     else{
       min_max.Min = array[start+1];
       min_max.Max = array[start];
     }
     index = start + 2;
   }

   int big, small;
   for ( int i = index; i < n-1; i = i+2 ){
      if ( array[i] < array[i+1] ){ //one comparison
        small = array[i];
        big = array[i+1];
      }
      else{
        small = array[i+1];
        big = array[i];
      }
      if ( min_max.Min > small ){ //one comparison
        min_max.Min = small;
      }
      if ( min_max.Max < big ){ //one comparison
        min_max.Max = big;
      }
   }

   return min_max;
}

Очень легко увидеть, что для сравнения требуется 3n / 2. Цикл выполняется n / 2 раза, и в каждой итерации выполняется 3 сравнения. Это, вероятно, оптимальный результат, которого можно достичь. В данный момент я не могу указать на определенный источник этого. (Но я думаю, что где-то видел это доказательство.)

Рекурсивное решение, данное Мехрдадом выше, вероятно, также достигает этого минимального числа сравнений (последнюю строку необходимо изменить). Но при одинаковом количестве сравнений итеративное решение всегда побеждает рекурсивное решение из-за накладных расходов при вызове функции, как он упоминал. Однако, если кто-то заботится только о поиске минимума и максимума из нескольких чисел (как это делает Эрик Белэр), никто не заметит никакой разницы в сегодняшнем компьютере с любым из описанных выше подходов. Для большого массива разница может быть значительной.

Хотя это решение и решение, данное Мэтью Брубейкером, имеют O (n) сложность, на практике следует тщательно оценивать задействованные скрытые константы. Количество сравнений в его решении составляет 2n. Ускорение, полученное благодаря решению с 3n / 2 сравнениями, в отличие от 2n сравнений, будет заметно.

Answer 4

Если массив не отсортирован, это лучшее, что вы получите. Если он отсортирован, просто возьмите первый и последний элементы.

Конечно, если он не отсортирован, то сортировка первого и захват первого и последнего гарантированно будут менее эффективными, чем простой цикл. Даже самые лучшие алгоритмы сортировки должны смотреть на каждый элемент более одного раза (в среднем O (log N) раз для каждого элемента. Это всего O (N * Log N). Простое однократное сканирование - только O (N)).

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

Answer 5

Вы должны пройтись по массиву, другого способа проверить все элементы нет. Только одно исправление для кода - если все элементы отрицательны, maxValue будет 0 в конце. Вы должны инициализировать его с минимально возможным значением для целого числа.
И если вы собираетесь искать в массиве много раз, лучше сначала отсортировать его, чем выполнять поиск быстрее (бинарный поиск), а минимальные и максимальные элементы - это только первый и последний.

Answer 6

Зависит от того, что вы называете «лучшим». С теоретической точки зрения вы не можете решить проблему менее чем за O(n) в детерминированной машине Тьюринга.

Наивный алгоритм слишком цикличен и обновляет мин, макс. Однако рекурсивное решение потребует меньше сравнений, чем простой алгоритм, если вы хотите получить min, max одновременно (это не обязательно быстрее из-за накладных расходов на вызов функции).

struct MinMax{
   public int Min,Max;
}

MinMax FindMinMax(int[] array, int start, int end) {
   if (start == end)
      return new MinMax { Min = array[start], Max = array[start] };

   if (start == end - 1)
      return new MinMax { Min = Math.Min(array[start], array[end]), Max = Math.Max(array[start], array[end]) } ;

   MinMax res1 = FindMinMax(array, start, (start + end)/2);
   MinMax res2 = FindMinMax(array, (start+end)/2+1, end);
   return new MinMax { Min = Math.Min(res1.Min, res2.Min), Max = Math.Max(res1.Max, res2.Max) } ;
}

Самое простое решение - отсортировать и получить первый и последний элемент, хотя, очевидно, он не самый быстрый;)

Наилучшим решением с точки зрения производительности, чтобы найти минимум или максимум, является наивный алгоритм, который вы написали (с одним циклом).

Answer 7

Math.max () на самом деле является кодом as3, скомпилированным с кодами операций AVM2, и поэтому не является более "родным", чем любой другой код as3. Как следствие, это не обязательно самая быстрая реализация.

На самом деле, учитывая, что он работает с типом Array, он работает медленнее, чем тщательно написанный код. Vector:

Я провел быстрое сравнение производительности нескольких простых реализаций Vector и Array Math.max, используя PerformanceTest от gskinner (Vector и Array заполняются одинаковыми случайными числами). Самая быстрая реализация Vector оказалась более чем в 3 раза быстрее, чем Math.max с недавним AIR SDK / релиз-плеером (Flash Player WIN 14,0,0,122 RELEASE, скомпилирован с AIR SDK 14):

в среднем 3,5 мс для 1000000 значений по сравнению со средним значением Math.max (), равным 11 мс:

function max(values:Vector.<Number>):Number
{
    var max:Number = Number.MIN_VALUE;
    var length:uint = values.length;
    for (var i:uint = 0; i < length ; ++i)
        if (values[i] > max)
            max = values[i];
    return max;
}

Вывод заключается в том, что если вас беспокоит производительность, вы должны использовать Vector over Array везде, где только можете, и не всегда полагаться на реализации по умолчанию, особенно когда они заставляют использовать Array

PS: та же реализация с циклом for each () в 12 раз медленнее ...!

Answer 8

Это зависит от реальных требований приложений.

Если ваш вопрос просто гипотетический, то основы уже были объяснены. Это типичная проблема поиска и сортировки. Уже упоминалось, что алгоритмически вы не добьетесь лучшего, чем O (n) для этого случая.

Однако, если вы посмотрите на практическое использование, все становится более интересным. Затем вам нужно будет рассмотреть, насколько большой массив, и процессы, связанные с добавлением и удалением из набора данных. В этих случаях может быть лучше взять вычислительный «удар» во время вставки / удаления, сортируя на лету. Вставки в предварительно отсортированный массив не такие дорогие.

Самый быстрый ответ на запрос Min Max всегда будет из отсортированного массива, потому что, как уже упоминали другие, вы просто берете первый или последний элемент, что дает вам стоимость O (1).

Для получения более подробного технического пояснения о вычислительных затратах и ​​обозначения Big O ознакомьтесь со статьей Википедии здесь .

Ник.

Answer 9

Если вы строите массив один раз и хотите найти максимум только один раз, итерации - это лучшее, что вы можете сделать.

Если вы хотите изменить массив и иногда хотите узнать максимальный элемент, вы должны использовать Priority Queue . Одна из лучших структур данных для этого - Куча Фибоначчи , если это слишком сложно, используйте Binary Heap , которая медленнее, но все же хороша.

Чтобы найти минимум и максимум, просто соберите две кучи и измените знак чисел в одной из них.

Answer 10

Пожалуйста, примите во внимание, что сортировка массива будет быстрее, чем зацикливание до определенного размера массива. Если ваш массив небольшой (и так будет в любое время), тогда ваше решение вполне подойдет. Но если он может стать слишком большим, вы должны использовать условный подход, чтобы использовать подход сортировки, когда массив маленький, и обычную итерацию, когда он слишком большой