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

Ответ 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.

Ответ 2

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

Ответ 3

Если

• Массив не сортируется
• Поиск минимального и максимального выполняется одновременно

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

В коде С++ (заимствование некоторого кода из Мехрдада).

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, было бы заметно.

Ответ 4

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

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

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

Ответ 5

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

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

Ответ 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) } ;
}

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

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

Ответ 7

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

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

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

в среднем 3,5 мс для 1 000 000 значений по сравнению с 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: та же реализация с a для каждого цикла() меньше 12x...!

Ответ 8

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

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

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

Ответ 9

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

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

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

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

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

Ник.

Ответ 10

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

Ответ 11

Если вы хотите одновременно найти как min, так и max, цикл можно изменить следующим образом:

int min = int.maxValue;
int max = int.minValue;

foreach num in someArray {
  if(num < min)
    min = num;
  if(num > max)
    max = num;
}

Это должно достичь времени O (n).

Ответ 12

Самый короткий путь:

Math.min.apply(нуль, массив);//это вернет значение min из массива Math.max.apply(нуль, массив);//это вернет максимальное значение из массива

иначе получить значение min и max из массива

 function maxVal(givenArray):Number
    {
    var max = givenArray[0];
    for (var ma:int = 0; ma<givenArray.length; ma++)
    {
    if (givenArray[ma] > max)
    {
    max = givenArray[ma];
    }
    }
    return max;
    }

    function minVal(givenArray):Number
    {
    var min = givenArray[0];
    for (var mi:int = 0; mi<givenArray.length; mi++)
    {
    if (givenArray[mi] < min)
    {
    min = givenArray[mi];
    }
    }
    return min;
    }

Как вы можете видеть, код в обеих этих функциях очень похож. Функция задает переменную - max (или min), а затем пробегает массив с циклом, проверяя каждый следующий элемент. Если следующий элемент выше текущего, установите его на max (или min). В конце верните номер.

Ответ 13

Существует несколько способов сделать это.

• Грубая сила. Линейный поиск как min, так и max отдельно. (2N сравнения и шаги 2N)
• Итерируйте линейно и проверьте каждое число как для min, так и для max. (сравнения 2N)
• Используйте Divide и побеждайте. (между сравнениями 2N и 3N/2)
• Сравнение по парам, приведенным ниже (сравнения 3N/2)

Как найти макс. и мин. в массиве с использованием минимальных сравнений?

Если вы действительно параноик относительно скорости, времени выполнения и количества сравнений, также см. http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/

Ответ 14

Алгоритм MaxMin (первый, последний, макс, мин)

//Этот алгоритм хранит самый высокий и самый низкий элемент

//Значения глобального массива A в глобальных переменных max и min

//tmax и tmin являются временными глобальными переменными

{
if (first==last) //Sub-array contains single element
 {
    max=A[first];
    min=A[first];
 }
 else if(first+1==last) //Sub-array contains two elements
  {
     if(A[first]<A[Last])
      {
      max=a[last];  //Second element is largest
      min=a[first]; //First element is smallest
      }
   else
   {
     max=a[first]; //First element is Largest 
     min=a[last];  //Second element is smallest
   }
}
else
 //sub-array contains more than two elements
{
 //Hence partition the sub-array into smaller sub-array 
 mid=(first+last)/2;
 //Recursively solve the sub-array
 MaxMin(first,mid,max,min);
 MaxMin(mid+1,last,tmax,tmin);
 if(max<tmax)
  {
     max=tmax;
  }
    if(min>tmin)
  {
   min=tmin;
  }
 }
}

Ответ 15

Ниже представлено решение с o (n): -

public static void findMaxAndMinValue(int A[]){
    int min =0, max = 0;
    if(A[0] > A[1] ){
        min = A[1];
        max = A[0];
    }else{
        max = A[1];
        min = A[0];
    }
    for(int i = 2;i<A.length ;i++){
        if(A[i] > max){
            max = A[i];
        }
        if(min > A[i]){
            min = A[i];
        }
    }
    System.out.println("Maxinum Value is  "+min+" & Minimum Value is  "+max);
}

Ответ 16

Прочитав все комментарии (спасибо за ваш интерес), я обнаружил, что "лучший" способ (наименьший объем кода, наиболее эффективный) для этого заключался в просто сортировке массива, а затем захвате первое значение в Массив:

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

myArray.sort(Array.NUMERIC);

var minValue:int = myArray[0];

Это также работает для массива объектов - вы просто используете функцию Array.sortOn() и указываете свойство:

// Sample data
var myArray:Array /* of XML */ = 
    [
    <item level="2" name="a" />
    <item level="3" name="b" />
    <item level="3" name="c" />
    <item level="2" name="d" />
    <item level="5" name="e" />
    ]

// Perform a descending sort on the specified attribute in Array to get the maximum value
myArray.sortOn("@level", Array.DESCENDING | Array.NUMERIC);

var lowestLevel:int = myArray[0][email protected];

Я надеюсь, что это когда-нибудь поможет кому-то еще!