Каков наилучший способ получить минимальное или максимальное значение из массива чисел?
https://stackoverflow.com/questions/424800
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Допустим, у меня есть массив чисел: [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;
}
Это просто не похоже на самый эффективный способ сделать это (я стараюсь избегать циклов, когда это возможно).
Решение
Теоретические ответы от всех остальных - аккуратные, но давайте будем прагматичными. 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.
Другие советы
Нет надежного способа получить минимум / максимум без проверки каждого значения. Вы не хотите пробовать сортировку или что-то в этом роде, обход массива - это O (n), что лучше, чем любой алгоритм сортировки в общем случае.
Если
- Массив не отсортирован
- Нахождение минимального и максимального значений выполняется одновременно
Затем существует алгоритм, который находит минимальное и максимальное значение за 3n / 2 числа сравнений.Что нужно сделать, так это обработать элементы массива попарно.Больший из пары значений следует сравнить с текущим максимумом, а меньший из пары значений - с текущим минимумом.Кроме того, нужно соблюдать особую осторожность, если массив содержит нечетное количество элементов.
В коде c ++ (заимствуя некоторый код у Мехрдада).
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 сравнения.Вероятно, это самый оптимальный вариант, которого можно достичь.На данный момент я не могу указать на определенный источник этого.(Но, мне кажется, я где-то видел доказательство этого.)
Рекурсивное решение, приведенное Мехрдадом выше, вероятно, также обеспечивает это минимальное количество сравнений (последнюю строку необходимо изменить).Но при том же количестве сравнений итеративное решение всегда будет превосходить рекурсивное решение из-за накладных расходов при вызове функции, как он упоминал.Однако, если кого-то волнует только нахождение min и max из нескольких чисел (как это делает Эрик Белэйр), никто не заметит никакой разницы в современных компьютерах при любом из описанных выше подходов.Для большого массива разница может быть существенной.
Хотя это решение и решение, данное Мэтью Брубейкером, имеют O (n) сложность, на практике следует тщательно оценивать задействованные скрытые константы.Количество сравнений в его решении равно 2n.Ускорение, полученное с помощью решения с 3n / 2 сравнениями, в отличие от 2n сравнений, было бы заметным.
Если массив не отсортирован, это лучшее, что вы получите. Если он отсортирован, просто возьмите первый и последний элементы.
Конечно, если он не отсортирован, то сортировка первого и получение первого и последнего гарантированно будут менее эффективными, чем простой цикл. Даже самые лучшие алгоритмы сортировки должны смотреть на каждый элемент более одного раза (в среднем O (log N) раз для каждого элемента. Это всего O (N * Log N). Простое однократное сканирование - только O (N).
Если вам нужен быстрый доступ к самому большому элементу в структуре данных, обратите внимание на кучу эффективного способа удержания объектов в некотором порядке.
Вы должны пройтись по массиву, иначе нет возможности проверить все элементы. Только одно исправление для кода - если все элементы отрицательны, maxValue будет 0 в конце. Вы должны инициализировать его с минимально возможным значением для целого числа.
И если вы собираетесь искать в массиве много раз, лучше сначала отсортировать его, чем выполнять поиск быстрее (бинарный поиск), а минимальный и максимальный элементы - это только первый и последний.
Зависит от того, что вы называете «лучшим». С теоретической точки зрения вы не можете решить проблему менее чем 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) } ;
}
Самое простое решение - отсортировать и получить первый и последний элемент, хотя, очевидно, он не самый быстрый;)
Наилучшим решением с точки зрения производительности для поиска минимального или максимума является наивный алгоритм, который вы написали (с одним циклом).
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 поверх Array везде, где только можете, и не всегда полагаться на реализации по умолчанию, особенно когда они заставляют использовать Array
PS: та же реализация с циклом for each () в 12 раз медленнее ...!
Это зависит от требований реального приложения.
Если ваш вопрос носит чисто гипотетический характер, то основы уже были объяснены.Это типичный поиск по сравнениюпроблема сортировки.Уже упоминалось, что алгоритмически вы не добьетесь большего, чем O (n) для этого случая.
Однако, если вы смотрите на практическое использование, все становится еще интереснее.Затем вам нужно будет рассмотреть, насколько велик массив, и процессы, связанные с добавлением и удалением из набора данных.В этих случаях, возможно, лучше всего использовать вычислительный "удар" во время вставки / удаления путем сортировки на лету.Вставки в предварительно отсортированный массив обходятся не так уж дорого.
Самый быстрый ответ на запрос Min Max всегда будет из отсортированного массива, потому что, как упоминали другие, вы просто берете первый или последний элемент, что дает вам стоимость O (1).
Для получения более подробного технического объяснения связанных с этим вычислительных затрат и обозначения Big O ознакомьтесь со статьей Википедии здесь.
Ник.
Если вы создаете массив один раз и хотите найти максимум только один раз, итерации - это лучшее, что вы можете сделать.
Если вы хотите изменить массив и иногда хотите узнать максимальный элемент, вы должны использовать Приоритет Очередь . Одна из лучших структур данных для этого - куча Фибоначчи , если это слишком сложно, используйте двоичная куча , которая работает медленнее, но все же хорошо.
Чтобы найти минимум и максимум, просто соберите две кучи и измените знак чисел в одной из них.
Пожалуйста, примите во внимание, что сортировка массива будет выполняться быстрее, чем зацикливание до определенного размера массива. Если ваш массив небольшой (и так будет в любое время), тогда ваше решение вполне подойдет. Но если он может стать слишком большим, вы должны использовать условный подход, чтобы использовать подход сортировки, когда массив маленький, и обычную итерацию, когда он слишком велик
Если вы хотите найти минимальное и максимальное значения одновременно, цикл можно изменить следующим образом:
int min = int.maxValue;
int max = int.minValue;
foreach num in someArray {
if(num < min)
min = num;
if(num > max)
max = num;
}
Это должно привести к достижению времени O (n).
Кратчайший путь :
Math.min.apply(null,массив);//это вернет минимальное значение из массива
Math.max.apply(null,массив);//это вернет максимальное значение из массива
другой способ получения минимального и максимального значения из массива
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).В конце концов, верните номер.
Есть несколько способов сделать это.
<Ол>Как найти макс. и мин. в массиве с использованием минимальных сравнений?
<Ч>Если вы действительно параноики по поводу скорости, времени работы и количество сравнений, также обратитесь к http://www.geeksforgeeks.org/maximum-and-minimum -в-ан-массив /
Алгоритм 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;
}
}
}
Ниже приведено решение с 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);
}
Удивленный никто не упомянул здесь параллелизм.
Если вы получили действительно огромный массив, вы можете использовать параллельный для поддиапазонов. В конце сравните все поддиапазоны. Но параллелизм также имеет некоторую потерю ширины, так что это не оптимизирует маленькие массивы. Однако, если у вас есть огромные наборы данных, это начинает иметь смысл, и вы получаете сокращение временного разделения, приближающееся к количеству потоков, выполняющих тест.
Найти максимальные значения из массива Давайте посмотрим, как получить минимальные, максимальные значения с помощью одной функции
public void findMaxValue(){
int[] my_array = {1,2,,6,5,8,3,9,0,23};
int max = my_array[0];
for(int i=1; i<my_array.length; i++)
{
if(my_array[i] > max)
max = my_array[i];
}
return max;
}
То же самое можно сделать для поиска минимального значения
Прочитав все комментарии (спасибо за проявленный интерес), я обнаружил, что " лучший " способ (наименьшее количество кода, наиболее эффективный) сделать это - просто отсортировать массив, а затем получить первое значение в массиве:
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].@level;
Надеюсь, это когда-нибудь поможет кому-то еще!
