Qual é a melhor maneira de obter o valor mínimo ou máximo de uma matriz de números?
https://stackoverflow.com/questions/424800
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Vamos dizer que eu tenho uma matriz de números: [2,3,3,4,2,2,5,6,7,2]
Qual é a melhor maneira de encontrar o valor mínimo ou máximo em que matriz?
Agora, para obter o máximo, estou loop através da matriz, e redefinir uma variável para o valor se ele for maior que o valor existente:
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;
}
Isso só não parece ser a melhor maneira de executar para fazer isso (eu tento evitar loops sempre que possível).
Solução
As respostas teóricas de todos os outros são todos puro, mas vamos ser pragmáticos. ActionScript fornece as ferramentas necessárias para que você não tem sequer a escrever um loop neste caso!
Em primeiro lugar, nota que Math.min() e Math.max() pode tomar qualquer número de argumentos. Além disso, é importante compreender o método apply() disponível para objetos Function. Ele permite que você passar argumentos para a função usando um Array. Vamos tirar proveito de ambos:
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);
Aqui está a melhor parte:. O "laço" é realmente executado usando código nativo (dentro Flash Player), por isso é mais rápido do que procurar o valor mínimo ou máximo usando um loop ActionScript puro
Outras dicas
Não há qualquer maneira confiável para obter o mínimo / máximo sem testar cada valor. Você não quer tentar uma espécie ou qualquer coisa assim, andando através da matriz é O (n), que é melhor do que qualquer algoritmo de ordenação pode fazer no caso geral.
Se
- A matriz não está classificada
- Encontrar o min e max é feito simultaneamente
Em seguida, existe um algoritmo que encontra o mínimo e o máximo em 3n / 2 o número de comparações. O que se precisa fazer é processar os elementos do array em pares. Quanto maior do par deve ser comparado com a corrente máxima e o mais pequeno do par deve ser comparado com o actual min. Além disso, é preciso tomar cuidado especial, se a matriz contém número ímpar de elementos.
No código C ++ (empréstimo de algum código 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;
}
É muito fácil ver que o número de comparações que toma é 3n / 2. A execução do loop n / 2 vezes e em cada iteração três comparações são realizadas. Este é provavelmente o melhor se pode alcançar. Neste momento, não posso apontar para uma fonte definitiva de que. (Mas, eu acho que eu vi uma prova de que em algum lugar.)
A solução recursiva dado por Mehrdad acima, provavelmente, também atinge este número mínimo de comparações (das últimas necessidades de linha para ser alterado). Mas, com o mesmo número de comparações uma solução iterativa baterá sempre uma solução recursiva devido à sobrecarga na chamada de função, como ele mencionou. No entanto, se um só se preocupa em encontrar min e max de alguns números (como Eric Belair faz), ninguém vai notar qualquer diferença no computador hoje com qualquer uma das abordagens acima. Para uma grande variedade, a diferença pode ser significativo.
Embora esta solução e a solução dada por Matthew Brubaker tem o (n) complexidade, na prática, deve-se avaliar cuidadosamente as constantes escondidos envolvidos. O número de comparações em sua solução é 2n. O aumento de velocidade adquirida com a solução com 3n / 2 comparações ao contrário de comparações 2n seria perceptível.
A menos que a matriz é classificada, isso é o melhor que você vai conseguir. Se ele é classificado, basta dar o primeiro e último elementos.
É claro que, se ele não está classificado, em seguida, a classificação em primeiro lugar e agarrar o primeiro eo último é garantido para ser menos eficiente do que apenas um loop através de uma vez. Mesmo os melhores algoritmos de ordenação tem que olhar para cada elemento mais de uma vez (uma média de O (log N) vezes para cada elemento. Essa varredura de O (N * Log N) total. Um simples, uma vez completamente estão somente O (N).
Se você está querendo acesso rápido à maior elemento de uma estrutura de dados, dar uma olhada em montões de uma maneira eficiente para manter objetos em algum tipo de ordem.
Você tem que percorrer a matriz, nenhuma outra maneira de verificar todos os elementos. Apenas uma correção para o código - se todos os elementos são negativos, maxValue será 0 no final. Você deve inicializar-lo com o valor mínimo possível para número inteiro.
E se você estiver indo para procurar a matriz muitas vezes é uma boa idéia para classificá-lo em primeiro lugar, que a pesquisa é mais rápida (busca binária) e mínimo e elementos máximas são apenas o primeiro eo último.
Depende do que você chama de "melhor". De um ponto de vista teórico, você não pode resolver o problema em menos de O(n) em uma máquina de Turing determinística.
O algoritmo ingênuo é muito loop e atualização min, max. No entanto, uma solução recursiva vai exigir menos comparações do que algoritmo ingênuo, se você deseja obter min, max simultaneamente (não é necessariamente mais rápido devido à função de chamada de sobrecarga).
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) } ;
}
A solução mais simples seria a de classificar e conseguir o primeiro e último item, embora obviamente não é o mais rápido;)
A melhor solução, em termos de performance, para encontrar o mínimo ou máxima é o algoritmo ingênuo que você escreveu (com um único loop).
Math.max () é realmente código AS3 compilado para opcodes AVM2, e como tal não é mais "nativa" do que qualquer outro código AS3. Como consequência, não é necessariamente a mais rápida implementação.
Na verdade, uma vez que ele funciona em tipo Array, é mais lento do que o código cuidadosamente escrito usign Vector:
Eu fiz uma comparação de referência rápida de várias implementações Vector ingênuo e de matriz de Math.max, usando PerformanceTest de gskinner (vetor e matriz que está sendo preenchido com números aleatórios idênticos). A implementação mais rápida Vector parecia ser mais do que 3x mais rápido do que Math.max com a recente jogador AIR SDK / release (flash player WIN 14,0,0,122 RELEASE, compilado com AIR SDK 14):
média 3,5 ms para valores 1.000.000, em comparação com Math.max () média de 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;
}
A conclusão é que, se você está preocupado com o desempenho, você deve usar Vector sobre matriz em qualquer lugar você pode, em primeiro lugar, e nem sempre dependem de implementações padrão, especialmente quando eles forçam o uso de array
PS: mesma implementação com um para cada () ciclo é 12x mais lento ...
Isso depende de requisitos de aplicações do mundo real.
Se a sua questão é meramente hipotética, em seguida, os fundamentos já foram explicadas. Ele é um típico problema de pesquisa vs. tipo. Já foi mencionado que algorithmically você não vai conseguir melhor do que O (n) para esse caso.
No entanto, se você está olhando para uso prático, as coisas ficam mais interessantes. Você, então, precisa considerar o quão grande a matriz é, e os processos envolvidos na adição e remoção do conjunto de dados. Nestes casos, pode ser melhor para levar o 'hit' computacional em tempo de inserção / remoção classificando na mosca. Inserções em uma matriz pré-ordenada que não são caros.
A resposta de consulta rápida ao pedido Min Max será sempre a partir de um array ordenado, porque, como outros já mencionados, você simplesmente tomar o primeiro ou o último elemento -. Dando-lhe uma O (1) custo
Para um pouco mais de uma explicação técnica sobre os custos computacionais envolvidos e notação Big O, confira o artigo Wikipedia aqui .
Nick.
Se você está construindo a matriz uma vez e quer encontrar o máximo apenas uma vez, a iteração é o melhor que você pode fazer.
Quando você quiser modificar a matriz e, ocasionalmente, quer saber o elemento máximo, você deve usar um href="http://en.wikipedia.org/wiki/Priority_queue" rel="nofollow noreferrer"> Prioridade . Uma das melhores estruturas de dados para que seja um Fibonacci Heap , se isso é muito complicado uso de um Binary Heap que é mais lento, mas ainda bom.
Para encontrar o mínimo eo máximo, apenas construir dois montões e mudar o sinal dos números em um deles.
Por favor tenha em conta que a classificação da matriz só será mais rápido que looping até certo tamanho da matriz. Se a sua matriz é pequeno (e que será como que a qualquer momento), então sua solução é perfeitamente bem. Mas se ele pode ficar muito grande você deve usar uma condicional para usar a abordagem de classificação, quando a matriz é pequeno, e a iteração normal quando ele é muito grande
Se você quiser encontrar tanto o min e max, ao mesmo tempo, o circuito pode ser modificado da seguinte forma:
int min = int.maxValue;
int max = int.minValue;
foreach num in someArray {
if(num < min)
min = num;
if(num > max)
max = num;
}
Esta deve se alcançar O (n) de tempo.
caminho mais curto:
Math.min.apply (null, matriz); // isto irá retornar o valor min da matriz de
Math.max.apply (null, matriz); // isto irá retornar o valor máximo do array
otherway de obter min e valor máximo de 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;
}
Como você pode ver, o código em ambas as funções é muito semelhante. A função define uma variável - max (ou minutos) e, em seguida, é executado através da matriz com um ciclo, a verificação de cada elemento seguinte. Se o elemento seguinte é maior do que a actual, configurá-lo para max (ou min). No final, retornar o número.
Existem várias maneiras isso pode ser feito.
- A força bruta. busca linear tanto para min e max separadamente. (2N comparações e 2N passos)
- Itere linearmente e verificar cada número, tanto para MIN e MAX.
(2N comparações) - Use Dividir para conquistar.
(Entre 2N e 3N / 2 comparações) - Comparar por pares explicado abaixo (3N / 2 comparações)
Como encontrar a max. e min. na matriz usando comparações mínimos?
Se você é realmente paranóico sobre a velocidade, tempo de execução e número de comparações, também se referem ao http://www.geeksforgeeks.org/maximum-and-minimum -em-um-matriz /
Algoritmo MaxMin (primeiro, último, max, min)
// Este algoritmo armazena o elemento maior e menor
// Valores do array A mundial nas variáveis ??globais máximo e mínimo
// Tmax e Tmin são variáveis ??globais temporários
{
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;
}
}
}
Abaixo está Solution com 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);
}
Espantado ninguém mencionou o paralelismo aqui.
Se você tem realmente um enorme variedade, você pode usar paralela-para, em sub gamas. No final comparar todos os sub-intervalos. Mas paralelismo vem largura alguma penalidade também, então isso não seria otimizar em pequenas matrizes. No entanto, se você tem enormes conjuntos de dados que começa a fazer sentido, e você terá uma redução de divisão de tempo chegando a quantidade de tópicos realizar o teste.
Encontre max valores de um array Vamos ver como obter mínimo, valores máximo, utilizando um único funtion
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;
}
mesma coisa pode fazer para o valor achado min
Depois de ler comentários de todos (obrigado por seu interesse), descobri que a maneira "melhor" (menor quantidade de código, melhor desempenho) para fazer isso era simplesmente classificar a matriz, em seguida, pegar o primeiro valor no 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];
Isso também funciona para uma matriz de objetos - você simplesmente usar a função Array.sortOn () e especificar uma propriedade:
// 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;
Espero que isso ajude alguém algum dia!
