Quelle est la meilleure façon d'obtenir la valeur minimale ou maximale d'un Tableau de nombres?

Les réponses théoriques à partir de tout le monde sont tous propres, mais soyons pragmatiques. ActionScript fournit les outils dont vous avez besoin, de sorte que vous n'avez même pas à écrire une boucle dans ce cas!

Tout d'abord, notez que Math.min() et Math.max() peut prendre un nombre quelconque d'arguments. Aussi, il est important de comprendre la apply() méthode disponible pour Function objets. Il vous permet de passer des arguments à la fonction à l'aide d'un Array. Prenons l'avantage de deux:

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);

Voici la meilleure partie: la "boucle" est en fait exécuter à l'aide de code natif (à l'intérieur de Flash Player), de sorte qu'il est plus rapide que de chercher la valeur minimale ou maximale à l'aide d'un pur ActionScript boucle.

Si

1. Le tableau n'est pas trié
2. Trouver le min et le max est fait simultanément

Alors il existe un algorithme qui trouve le min et le max 3n/2 nombre de comparaisons. Ce qu'on doit faire est de traiter les éléments de la matrice dans les paires. La plus grande, la paire devrait être comparé avec le courant max et la plus petite de la paire doit être comparé avec le courant min. Aussi, il faut prendre des précautions particulières si le tableau contient un nombre impair d'éléments.

Dans du code c++ (emprunt du code de 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;
}

Il est très facile de voir que le nombre de comparaisons qu'il prend est 3n/2. La boucle s'exécute n/2 fois et à chaque itération 3 les comparaisons sont effectuées. C'est probablement l'optimum l'on peut obtenir. En ce moment, je ne peut pas pointer vers une source précise de qui. (Mais, je crois avoir vu une preuve de quelque part.)

La solution récursive donné par Mehrdad ci-dessus, probablement réalise également le faible nombre de comparaisons (la dernière ligne doit être changé). Mais avec le même nombre de comparaisons itératif toujours la solution de battre une solution récursive en raison de la surcharge dans l'appel de fonction comme il l'a mentionné. Cependant, si l'on ne se soucie de trouver des min et max de quelques chiffres (comme Eric Belair, t), personne ne remarquerez aucune différence dans notre ordinateur avec l'une des méthodes ci-dessus. Pour un grand tableau, la différence pourrait être importante.

Bien que cette solution, et la solution donnée par Matthieu Brubaker a O(n) la complexité, dans la pratique, on doit soigneusement évaluer les constantes cachées impliqués. Le nombre de comparaisons dans sa solution est 2n. L'accélération acquise avec la solution 3n/2 comparaisons, par opposition à 2n comparaisons serait notable.

Que vous avez à parcourir le tableau, pas d'autre moyen de vérifier tous les éléments. Juste une correction pour le code - si tous les éléments sont négatifs, maxValue sera de 0 à la fin. Vous devez l'initialiser avec la valeur minimum possible pour entier.

Et si vous allez à la recherche de la matrice de nombreuses fois, c'est une bonne idée de les trier d'abord, que la recherche est plus rapide (binaire de recherche) et le minimum et le maximum des éléments sont juste la première et la dernière.

Mathématiques.max() est en fait as3 code compilé pour AVM2 opcodes, et en tant que tel n'est pas plus "natif" que n'importe quel autre code as3. En conséquence, il n'est pas nécessairement le plus rapide de mise en œuvre.

En fait, étant donné qu'il fonctionne sur type Tableau, il est plus lent que soigneusement code écrit avec Vecteur:

J'ai fait une rapide comparaison des performances de plusieurs naïf Vecteur et Matrice des implémentations de Mathématiques.max, en utilisant gskinner de PerformanceTest (Vecteur et Matrice remplie avec les mêmes Nombres aléatoires).
La manière la plus rapide Vecteur de la mise en œuvre semble être plus de 3x plus rapide que les Mathématiques.max avec les récentes AIR SDK/libération du joueur (flash player GAGNER 14,0,0,122 LIBÉRATION, compilé avec le SDK d'AIR 14):

en moyenne de 3,5 ms pour 1 000 000 de valeurs, par rapport aux Mathématiques.max() moyenne de 11 ms :

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;
}

Conclusion est que si vous êtes préoccupé par la performance, vous devez utiliser de Vecteur au cours de la Matrice de partout où vous pouvez, en premier lieu, et ne pas toujours compter sur des implémentations par défaut, surtout quand ils forcer l'utilisation de la Matrice de

PS:même mise en œuvre pour chaque() de la boucle est 12x plus lent ...!

Si vous êtes à la construction de la matrice de une fois et que vous voulez trouver le maximum d'une fois, le parcours est le meilleur que vous pouvez faire.

Lorsque vous souhaitez modifier le tableau et parfois envie de connaître la valeur maximale de l'élément, vous devez utiliser un File D'Attente De Priorité. L'une des meilleures structures de données qui est une Tas De Fibonacci, si c'est trop compliqué d'utiliser un Tas Binaire qui est plus lent, mais toujours bon.

Pour trouver le minimum et le maximum, juste à la construction de deux tas de changer le signe des nombres dans l'un d'eux.

Si vous voulez trouver à la fois le min et max dans le même temps, la boucle peut être modifié comme suit:

int min = int.maxValue;
int max = int.minValue;
foreach num in someArray {
if(num < min)
min = num;
if(num > max)
max = num;
}

Cela devrait se réaliser en O(n) moment.

Il y a un certain nombre de façons cela peut être fait.

1. De la force Brute. La recherche linéaire pour les deux min et max séparément. (2N
   les comparaisons et 2N étapes)
2. Itération de façon linéaire et vérifier chaque numéro pour les deux min et max. (2N comparaisons)
3. Utilisation Diviser et conquérir. (Entre 2N et 3N/2 comparaisons)
4. Comparer par paires expliqué ci-dessous (3N/2 Comparaisons)

Comment trouver le max. et min. dans le tableau à l'aide de minimum de comparaisons?

Si vous êtes vraiment paranoïaque à propos de la vitesse, la durée d'exécution & nombre de comparaisons, voir aussi
http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/

Ci-dessous est la Solution à 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);
}

Trouver max les valeurs d'un tableau
Nous allons voir comment obtenir min, max valeurs à l'aide d'une seule fonction de

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; 
}

même chose peut faire pour trouver la valeur min