Quel est le meilleur moyen d’obtenir la valeur minimale ou maximale d’un tableau de nombres?
https://stackoverflow.com/questions/424800
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Disons que j'ai un tableau de nombres: [2,3,3,4,2,2,5,6,7,2]
Quel est le meilleur moyen de trouver la valeur minimale ou maximale dans ce tableau?
Pour obtenir le maximum, je boucle en boucle dans le tableau et je réinitialise une variable à la valeur si elle est supérieure à la valeur existante:
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;
}
Cela ne semble pas être le moyen le plus performant de le faire (j'essaie d'éviter les boucles autant que possible).
La solution
Les réponses théoriques de tous les autres sont toutes soignées, mais soyons pragmatiques. ActionScript fournit les outils dont vous avez besoin pour ne pas avoir à écrire de boucle dans ce cas!
Tout d'abord, notez que Math.min () et Math.max () peuvent prendre n'importe quel nombre d'arguments. De plus, il est important de comprendre la méthode apply () disponible pour les objets Function . Il vous permet de passer des arguments à la fonction en utilisant un Array . Profitons des 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; boucle " est réellement exécuté à l'aide de code natif (dans Flash Player). Il est donc plus rapide que de rechercher la valeur minimale ou maximale à l'aide d'une boucle ActionScript pure.
Autres conseils
Il n’existe aucun moyen fiable d’obtenir le minimum / maximum sans tester chaque valeur. Vous ne voulez pas essayer une sorte ou quelque chose comme ça, parcourir le tableau est O (n), ce qui est mieux que tout algorithme de tri ne peut le faire dans le cas général.
Si
- Le tableau n'est pas trié
- La recherche du minimum et du maximum s'effectue simultanément
Ensuite, il existe un algorithme qui trouve le minimum et le maximum dans 3n / 2 nombre de comparaisons. Ce qu'il faut faire, c'est traiter les éléments du tableau par paires. Le plus grand de la paire doit être comparé au maximum actuel et le plus petit de la paire au minimum actuel. En outre, il faut faire particulièrement attention si le tableau contient un nombre impair d’éléments.
Dans le code c ++ (empruntant du code à 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 nécessaires est de 3n / 2. La boucle est exécutée n / 2 fois et à chaque itération, 3 comparaisons sont effectuées. C'est probablement l'optimum que l'on peut atteindre. Pour le moment, je ne peux pas pointer vers une source précise de cela. (Mais, je pense en avoir vu la preuve quelque part.)
La solution récursive donnée par Mehrdad ci-dessus réalise probablement également ce nombre minimal de comparaisons (la dernière ligne doit être modifiée). Mais avec le même nombre de comparaisons, une solution itérative sera toujours préférable à une solution récursive en raison de la surcharge de l'appel de fonction, comme il l'a mentionné. Cependant, si l’on se soucie seulement de trouver le minimum et le maximum de quelques nombres (comme le fait Eric Belair), personne ne remarquera la moindre différence entre l’ordinateur actuel et l’une des approches ci-dessus. Pour un large éventail, la différence pourrait être significative.
Bien que cette solution et la solution proposée par Matthew Brubaker aient une complexité (n), dans la pratique, il convient d’évaluer soigneusement les constantes cachées impliquées. Le nombre de comparaisons dans sa solution est 2n. L'accélération obtenue avec la solution avec les comparaisons 3n / 2 par opposition aux comparaisons 2n serait perceptible.
À moins que le tableau ne soit trié, vous obtiendrez le meilleur résultat. S'il est trié, prenez simplement le premier et le dernier élément.
Bien sûr, s’il n’est pas trié, il est garanti que le tri en premier et le premier et le dernier seront moins efficaces qu’une simple boucle. Même les meilleurs algorithmes de tri doivent examiner chaque élément plus d'une fois (une moyenne de 0 fois (log N) pour chaque élément. C'est le total de O (N * Log N). Un simple balayage une fois n'est que de O (N).
Si vous souhaitez accéder rapidement au plus grand élément d'une structure de données, examinez les tas afin de conserver efficacement les objets dans un ordre quelconque.
Vous devez 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 0 à la fin. Vous devez l’initialiser avec la valeur minimale possible pour un entier.
Et si vous allez parcourir le tableau plusieurs fois, il est judicieux de le trier en premier, car la recherche est plus rapide (recherche binaire) et les éléments minimum et maximum ne sont que le premier et le dernier.
Cela dépend de ce que vous appelez "mieux". D'un point de vue théorique, vous ne pouvez pas résoudre le problème en moins de O (n) dans une machine de Turing déterministe.
L’algorithme naïf est trop en boucle et met à jour min, max. Cependant, une solution récursive nécessitera moins de comparaisons que l'algorithme naïf, si vous souhaitez obtenir simultanément min, max (ce n'est pas nécessairement plus rapide en raison de la surcharge des appels de fonctions).
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) } ;
}
La solution la plus simple serait de trier et d’obtenir le premier et le dernier élément, bien que ce ne soit évidemment pas le plus rapide;)
La meilleure solution, en termes de performances, pour rechercher le ou maximum est l'algorithme naïf que vous avez écrit (avec une seule boucle).
Math.max () est en réalité un code as3 compilé en opcodes AVM2 et, en tant que tel, n’est pas plus "natif". que tout autre code as3. Par conséquent, ce n’est pas nécessairement la mise en oeuvre la plus rapide.
En fait, étant donné que cela fonctionne sur le type Array, il est plus lent que le code soigneusement écrit usign Vector:
J'ai effectué une comparaison rapide de plusieurs implémentations naïves de Math.max dans Vector et Array, à l'aide de PerformanceTest de gskinner (Vector et Array étant remplis de nombres aléatoires identiques). L’implémentation de Vector la plus rapide semblait être plus de 3 fois plus rapide que Math.max avec un lecteur AIR SDK récent (Flash player WIN 14,0,0122 RELEASE, compilé avec AIR SDK 14):
moyenne de 3,5 ms pour 1 000 000 valeurs, comparé à la moyenne Math.max () 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;
}
La conclusion est que si les performances vous préoccupent, vous devez utiliser Vector sur Array partout où vous le pouvez et ne pas toujours vous fier aux implémentations par défaut, en particulier lorsqu'elles forcent l'utilisation de Array
PS: la même implémentation avec une boucle pour chaque () est 12x plus lente ...!
Cela dépend des exigences des applications réelles.
Si votre question est simplement hypothétique, les bases ont déjà été expliquées. C'est un problème typique de recherche contre tri. Il a déjà été mentionné que, dans ce cas, vous n'allez pas obtenir mieux que O (n) sur le plan de l'algorithme.
Cependant, si vous envisagez une utilisation pratique, les choses deviennent plus intéressantes. Vous devrez ensuite prendre en compte la taille du tableau et les processus impliqués dans l'ajout et la suppression de l'ensemble de données. Dans ces cas, il peut être préférable de prendre le «coup» informatique au moment de l'insertion / du retrait en effectuant un tri à la volée. Les insertions dans un tableau pré-trié ne coûtent pas très cher.
La réponse de requête la plus rapide à la requête Min Max sera toujours issue d'un tableau trié, car, comme d'autres l'ont mentionné, vous prenez simplement le premier ou le dernier élément, ce qui vous donne un coût O (1).
Pour un peu plus d'explications techniques sur les coûts de calcul impliqués et la notation Big O, consultez l'article de Wikipedia ici .
Nick.
Si vous créez le tableau une fois et souhaitez rechercher le maximum une seule fois, l'itération est ce que vous pouvez faire de mieux.
Lorsque vous souhaitez modifier le tableau et parfois connaître le nombre maximal d'éléments, vous devez utiliser une Priority. File d'attente . L’une des meilleures structures de données pour cela est un Fibonacci Heap , si cela est trop compliqué, utilisez Le segment binaire , qui est plus lent mais toujours bon.
Pour trouver le minimum et le maximum, créez simplement deux tas et modifiez le signe des nombres dans l'un d'entre eux.
Veuillez tenir compte du fait que le tri du tableau ne sera plus rapide que celui de la mise en boucle jusqu’à une certaine taille du tableau. Si votre tableau est petit (et ce sera comme ça à tout moment), alors votre solution est parfaite. Mais si elle devient trop grande, vous devez utiliser une condition pour utiliser l’approche de tri lorsque le tableau est petit et l’itération normale quand il est trop grand
Si vous souhaitez rechercher simultanément les valeurs min et max, la boucle peut être modifiée 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 permettre d’atteindre le bon moment.
Chemin le plus court:
Math.min.apply (null, array); // cela retournera la valeur min du tableau
Math.max.apply (null, array); // cela retournera la valeur maximale du tableau
autre moyen d'obtenir min & amp; valeur max du tableau
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;
}
Comme vous pouvez le constater, le code de ces deux fonctions est très similaire. La fonction définit une variable - max (ou min), puis parcourt le tableau avec une boucle en vérifiant chaque élément suivant. Si l'élément suivant est supérieur au courant, définissez-le sur max (ou min). En fin de compte, renvoyez le numéro.
Cela peut être fait de différentes manières.
- Force brute. Recherche linéaire pour min et max séparément. (2N comparaisons et 2N étapes)
- Itérer linéairement et vérifier chaque nombre pour les valeurs min et max. (comparaisons 2N)
- Utilisez Diviser et conquérir. (entre 2N et 3N / 2 comparaisons)
- Comparez par paires, comme expliqué ci-dessous (Comparaisons 3N / 2)
Comment trouver max. et min. dans un tableau utilisant des comparaisons minimales?
Si vous êtes vraiment paranoïaque à propos de la vitesse, exécutez & amp; nombre de comparaisons, se réfèrent également à http://www.geeksforgeeks.org/maximum-and-minimum -in-an-array /
Algorithme MaxMin (premier, dernier, max, min)
// Cet algorithme stocke l'élément le plus haut et le plus bas
// Valeurs du tableau global A dans les variables globales max et min
// tmax et tmin sont des variables globales temporaires
{
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;
}
}
}
Ci-dessous, la solution avec 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);
}
Je suis étonné que personne n'ait mentionné le parallélisme ici.
Si vous avez vraiment un très grand tableau, vous pouvez utiliser parallel-for, sur des sous-gammes. À la fin, comparez toutes les sous-gammes. Mais le parallélisme entraîne également une certaine pénalité, de sorte que cela ne serait pas optimal pour les tableaux de petite taille. Cependant, si vous avez d'énormes ensembles de données, cela commence à avoir un sens et vous obtenez une réduction de la division de temps proche du nombre de threads effectuant le test.
Rechercher les valeurs maximales dans un tableau Voyons comment obtenir des valeurs min, max en utilisant une seule fonction
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;
}
la même chose peut faire pour trouver la valeur minimale
Après avoir lu les commentaires de chacun (merci de votre intérêt), j’ai constaté que le "meilleur" Pour ce faire, il suffit de trier le tableau, puis de saisir la première valeur du tableau:
var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];
myArray.sort(Array.NUMERIC);
var minValue:int = myArray[0];
Ceci fonctionne également pour un tableau d'objets. Vous utilisez simplement la fonction Array.sortOn () et spécifiez une propriété:
// 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;
J'espère que cela aidera quelqu'un d'autre un jour!
