Qual è il modo migliore per ottenere il valore minimo o massimo da una matrice di numeri?
https://stackoverflow.com/questions/424800
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Diciamo che ho una matrice di numeri: [2,3,3,4,2,2,5,6,7,2<
Qual è il modo migliore per trovare il valore minimo o massimo in quell'array?
In questo momento, per ottenere il massimo, sto eseguendo il loop attraverso l'array e reimpostando una variabile sul valore se è maggiore del valore esistente:
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;
}
Questo non sembra proprio il modo migliore per farlo (cerco di evitare loop ogni volta che è possibile).
Soluzione
Le risposte teoriche di tutti gli altri sono tutte pulite, ma siamo pragmatici. ActionScript fornisce gli strumenti necessari per non dover nemmeno scrivere un ciclo in questo caso!
Innanzitutto, si noti che Math.min () e Math.max () possono accettare qualsiasi numero di argomenti. Inoltre, è importante comprendere il metodo apply () disponibile per gli oggetti Function . Ti permette di passare argomenti alla funzione usando un Array . Approfittiamo di entrambi:
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);
Ecco la parte migliore: il " loop " viene effettivamente eseguito utilizzando il codice nativo (all'interno di Flash Player), quindi è più veloce della ricerca del valore minimo o massimo utilizzando un loop ActionScript puro.
Altri suggerimenti
Non esiste un modo affidabile per ottenere il minimo / massimo senza testare ogni valore. Non vuoi provare un ordinamento o qualcosa del genere, camminare attraverso l'array è O (n), che è meglio di qualsiasi algoritmo di ordinamento può fare nel caso generale.
Se
- L'array non è ordinato
- La ricerca di min e max viene eseguita contemporaneamente
Quindi c'è un algoritmo che trova il minimo e il massimo in 3n / 2 numero di confronti. Ciò che si deve fare è elaborare gli elementi dell'array in coppie. Il più grande della coppia dovrebbe essere confrontato con il massimo corrente e il più piccolo della coppia dovrebbe essere confrontato con il minimo corrente. Inoltre, è necessario prestare particolare attenzione se l'array contiene un numero dispari di elementi.
Nel codice c ++ (prendendo in prestito del codice da 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;
}
È molto facile vedere che il numero di confronti che richiede è 3n / 2. Il ciclo viene eseguito n / 2 volte e in ciascuna iterazione vengono eseguiti 3 confronti. Questo è probabilmente quello ottimale che si può ottenere. In questo momento, non posso indicare una fonte definita di ciò. (Ma penso di averne visto una prova da qualche parte.)
La soluzione ricorsiva fornita da Mehrdad sopra, probabilmente raggiunge anche questo numero minimo di confronti (l'ultima riga deve essere cambiata). Ma con lo stesso numero di confronti una soluzione iterativa batterà sempre una soluzione ricorsiva a causa dell'overhead nella chiamata di funzione di cui ha parlato. Tuttavia, se uno si preoccupa solo di trovare min e max di alcuni numeri (come fa Eric Belair), nessuno noterà alcuna differenza nel computer di oggi con uno degli approcci sopra. Per un array di grandi dimensioni, la differenza potrebbe essere significativa.
Sebbene questa soluzione e la soluzione data da Matthew Brubaker abbiano una complessità O (n), in pratica si dovrebbero valutare attentamente le costanti nascoste coinvolte. Il numero di confronti nella sua soluzione è 2n. Lo speedup ottenuto con la soluzione con confronti 3n / 2 rispetto ai confronti 2n sarebbe evidente.
A meno che l'array non sia ordinato, questo è il migliore che otterrai. Se è ordinato, prendi solo il primo e l'ultimo elemento.
Ovviamente, se non è ordinato, allora l'ordinamento per primo e il primo e l'ultimo sono garantiti per essere meno efficienti di un semplice ciclo una volta. Anche i migliori algoritmi di ordinamento devono guardare ogni elemento più di una volta (una media di O (log N) volte per ogni elemento. Questo è O (N * Log N) totale. Una semplice scansione una volta attraverso è solo O (N).
Se desideri un accesso rapido all'elemento più grande in una struttura di dati, dai un'occhiata a heap per un modo efficiente per mantenere gli oggetti in una sorta di ordine.
Devi passare in rassegna l'array, nessun altro modo per controllare tutti gli elementi. Solo una correzione per il codice: se tutti gli elementi sono negativi, maxValue sarà 0 alla fine. È necessario inizializzarlo con il valore minimo possibile per intero.
E se hai intenzione di cercare l'array molte volte è una buona idea ordinarlo prima, quindi la ricerca è più veloce (ricerca binaria) e gli elementi minimo e massimo sono solo il primo e l'ultimo.
Dipende da ciò che chiami "migliore". Da un punto di vista teorico, non è possibile risolvere il problema in meno di O (n) in una macchina di Turing deterministica.
L'algoritmo ingenuo è troppo loop e aggiorna min, max. Tuttavia, una soluzione ricorsiva richiederà meno confronti rispetto all'algoritmo ingenuo, se si desidera ottenere min, max contemporaneamente (non è necessariamente più veloce a causa dell'overhead della chiamata di funzione).
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 soluzione più semplice sarebbe quella di ordinare e ottenere il primo e l'ultimo elemento, anche se ovviamente non è il più veloce;)
La migliore soluzione, dal punto di vista delle prestazioni, per trovare il minimo o massimo è l'algoritmo ingenuo che hai scritto (con un singolo ciclo).
Math.max () è in realtà un codice as3 compilato in codici operativi AVM2 e come tale non è più "nativo" di qualsiasi altro codice as3. Di conseguenza, non è necessariamente l'implementazione più rapida.
In realtà, dato che funziona sul tipo di array, è più lento del codice scritto con attenzione usign Vector:
Ho fatto un rapido confronto comparativo tra diverse implementazioni Vector e Array ingenue di Math.max, usando PerformanceTest di gskinner (Vector e Array sono riempiti con identici numeri casuali). L'implementazione Vector più veloce sembrava essere più di 3 volte più veloce di Math.max con il recente AIR SDK / release player (flash player WIN 14,0,0,122 RELEASE, compilato con AIR SDK 14):
media 3,5 ms per 1.000.000 di valori, rispetto alla media Math.max () di 11ms:
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 conclusione è che se sei preoccupato per le prestazioni, dovresti usare Vector over Array ovunque tu sia in primo luogo, e non sempre fare affidamento su implementazioni predefinite, specialmente quando forzano l'uso dell'array
PS: la stessa implementazione con un ciclo per ogni () è 12 volte più lenta ...!
Questo dipende dai requisiti di applicazione del mondo reale.
Se la tua domanda è puramente ipotetica, le basi sono già state spiegate. È un tipico problema di ricerca vs. ordinamento. È già stato menzionato che algoritmicamente non otterrai risultati migliori di O (n) per quel caso.
Tuttavia, se stai cercando un uso pratico, le cose diventano più interessanti. Dovresti quindi considerare quanto è grande l'array e i processi coinvolti nell'aggiunta e nella rimozione dal set di dati. In questi casi, può essere meglio prendere il "colpo" computazionale al momento dell'inserimento / rimozione ordinando al volo. Gli inserimenti in un array preordinato non sono così costosi.
La risposta alla query più rapida alla richiesta Min Max proviene sempre da un array ordinato, perché come altri hanno già detto, prendi semplicemente il primo o l'ultimo elemento, dandoti un costo O (1).
Per un po 'più di una spiegazione tecnica sui costi computazionali coinvolti e notazione Big O, consulta l'articolo di Wikipedia qui .
Nick.
Se stai creando l'array una volta e vuoi trovare il massimo una sola volta, l'iterazione è il meglio che puoi fare.
Quando si desidera modificare l'array e occasionalmente si desidera conoscere l'elemento massimo, è necessario utilizzare una Priorità coda . Una delle migliori strutture di dati per questo è un Fibonacci Heap , se questo è troppo complicato usa un Heap binario che è più lento ma comunque buono.
Per trovare il minimo e il massimo, basta creare due cumuli e cambiare il segno dei numeri in uno di essi.
Tieni presente che l'ordinamento dell'array sarà solo più veloce del looping fino a determinate dimensioni dell'array. Se il tuo array è piccolo (e lo sarà in qualsiasi momento), la tua soluzione andrà benissimo. Ma se potrebbe diventare troppo grande, dovresti usare un condizionale per usare l'approccio di ordinamento quando l'array è piccolo e l'iterazione normale quando è troppo grande
Se si desidera trovare contemporaneamente il minimo e il massimo, il ciclo può essere modificato come segue:
int min = int.maxValue;
int max = int.minValue;
foreach num in someArray {
if(num < min)
min = num;
if(num > max)
max = num;
}
Questo dovrebbe ottenere il tempismo O (n).
Modo più breve:
Math.min.apply (null, array); // questo restituirà il valore minimo dall'array
Math.max.apply (null, array); // questo restituirà il valore massimo dall'array
altrimenti di ottenere min & amp; valore massimo dall'array
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;
}
Come puoi vedere, il codice in entrambe queste funzioni è molto simile. La funzione imposta una variabile - max (o min) e quindi esegue l'array con un ciclo, controllando ogni elemento successivo. Se l'elemento successivo è superiore alla corrente, impostalo su max (o min). Alla fine, restituisci il numero.
Esistono diversi modi per farlo.
- Forza bruta. Ricerca lineare per min e max separatamente. (2N confronti e passaggi 2N)
- Iterate in modo lineare e controllate ogni numero per min e max. (confronti 2N)
- Usa Dividi e conquista. (tra confronto 2N e 3N / 2)
- Confronta per coppie spiegate di seguito (3N / 2 confronti)
Come trovare max. e min. nell'array usando confronti minimi?
Se sei veramente paranoico su velocità, runtime e amp; numero di confronti, fare riferimento anche a http://www.geeksforgeeks.org/ma maximum-and-minimum -in-un-array /
Algorithm MaxMin (primo, ultimo, massimo, min)
// Questo algoritmo memorizza l'elemento più alto e più basso
// Valori dell'array globale A nelle variabili globali max e min
// tmax e tmin sono variabili globali temporanee
{
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;
}
}
}
Di seguito è la soluzione con 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);
}
Qui nessuno stupisce del parallelismo menzionato.
Se hai davvero un array enorme, puoi usare parallel-for, su sub range. Alla fine confronta tutti i sotto-intervalli. Ma il parallelismo comporta anche una certa penalità, quindi questo non ottimizzerebbe su array di piccole dimensioni. Tuttavia, se disponi di enormi set di dati, inizia ad avere senso e ottieni una riduzione della divisione del tempo vicino alla quantità di thread che eseguono il test.
Trova valori massimi da un array Vediamo come ottenere valori minimi e massimi utilizzando un'unica funzione
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 stessa cosa può fare per trovare il valore minimo
Dopo aver letto i commenti di tutti (grazie per l'interesse), ho scoperto che il "migliore" il modo (meno quantità di codice, le migliori prestazioni) per fare ciò era semplicemente ordinare l'array e quindi prendere il primo valore nell'array:
var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];
myArray.sort(Array.NUMERIC);
var minValue:int = myArray[0];
Funziona anche con una matrice di oggetti: basta usare la funzione Array.sortOn () e specificare una proprietà:
// 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;
Spero che questo possa aiutare qualcun altro un giorno!
