medir - length javascript español
¿El mejor algoritmo para determinar lo alto y lo bajo en una matriz de números? (14)
Estoy usando pseudo-código aquí, pero esto está en JavaScript. Con el algoritmo más eficiente posible, estoy tratando de encontrar el alto y el bajo dado un conjunto de números enteros positivos. Esto es lo que se me ocurrió, pero no creo que sea probablemente lo mejor, y me preguntaba si alguien tiene alguna otra sugerencia.
var low = 1;
var high = 1;
for ( loop numbers ) {
if ( number > high ) {
high = number;
}
if ( low == 1 ) {
low = high;
}
if ( number < low ) {
low = number;
}
}
En Python:
>>> seq = [1, 2, 3, 4, 5, 6, 7]
>>> max(seq)
7
>>> min(seq)
1
La única optimización adicional que sugeriría es optimizar el circuito en sí. Es más rápido contar hacia atrás que contar en JavaScript.
Si la lista es pequeña (donde "pequeño" es menor que unos pocos miles de elementos) y no lo hace mucho (donde "mucho" es menos de unos miles de veces) no importa. Haga un perfil de su código primero para encontrar el cuello de botella real antes de preocuparse por la optimización de sus algoritmos de máximo / mínimo.
Ahora para responder la pregunta que hiciste.
Debido a que no hay forma de evitar mirar cada elemento de la lista, una búsqueda lineal es el algoritmo más eficiente. Lleva N tiempo, donde N es la cantidad de elementos en la lista. Hacerlo todo en un ciclo es más eficiente que llamar a max () y luego a min () (que toma 2 * N tiempo). Entonces, su código es básicamente correcto, aunque no da cuenta de los números negativos. Aquí está en Perl.
# Initialize max & min
my $max = $list[0];
my $min = $list[0];
for my $num (@list) {
$max = $num if $num > $max;
$min = $num if $num < $min;
}
Ordenando y luego agarrando el primer y último elemento es el menos eficiente. Toma N * log (N) donde N es la cantidad de elementos en la lista.
El algoritmo mínimo / máximo más eficiente es aquel en el que se recalcula min / max cada vez que se agrega o quita un elemento de la lista. En efecto, almacenar en caché el resultado y evitar una búsqueda lineal cada vez. El tiempo dedicado a esto es el número de veces que se cambia la lista. Toma, a lo sumo, M hora, donde M es el número de cambios sin importar cuántas veces lo llame.
Para hacer eso, podrías considerar un árbol de búsqueda que mantenga sus elementos en orden. Obtener el min / max en esa estructura es O (1) u O (log [n]) dependiendo del estilo de árbol que use.
Su ejemplo es prácticamente el algoritmo más eficiente, pero obviamente no funcionará cuando todos los números sean menores que 1 o mayores que 1. Este código funcionará en esos casos:
var low = numbers[0]; // first number in array
var high = numbers[0]; // first number in array
for ( loop numbers ) {
if ( number > high ) {
high = number;
}
if ( number < low ) {
low = number;
}
}
Suponiendo que la lista no está ya ordenada, es lo mejor que puedes hacer. Puede ahorrarse una comparación haciendo lo siguiente (en pseudocódigo):
low = +INFINITY
high = -INFINITY
for each n in numbers:
if n < low:
low = n
if n > high:
high = n
Esta es una operación O (n), que es básicamente lo mejor que puede hacer.
var numbers = [1,2,5,9,16,4,6];
var maxNumber = Math.max.apply(null, numbers);
var minNumber = Math.min.apply(null, numbers);
inicialice el elemento alto y bajo para ser el primero. tiene mucho más sentido que elegir un número arbitrariamente "alto" o "bajo".
var myArray = [...],
low = myArray[0],
high = myArray[0]
;
// start looping at index 1
for (var i = 1, l = myArray.length; i < l; ++i) {
if (myArray[i] > high) {
high = myArray[i];
} else if (myArray[i] < low) {
low = myArray[i];
}
}
o, evitando la necesidad de buscar la matriz varias veces:
for (var i = 1, val; (val = myArray[i]) !== undefined; ++i) {
if (val > high) {
high = val;
} else if (val < low) {
low = val;
}
}
Al probar estos fragmentos de verdad en V8, el algoritmo de Drew Hall se ejecuta en 2/3 del tiempo de nickf, como se predijo. Al hacer que el bucle baje la cuenta en lugar de subir, se reduce a aproximadamente el 59% del tiempo (aunque eso depende más de la implementación). Solo ligeramente probado:
var A = [ /* 100,000 random integers */];
function minmax() {
var low = A[A.length-1];
var high = A[A.length-1];
var i, x, y;
for (i = A.length - 3; 0 <= i; i -= 2) {
y = A[i+1];
x = A[i];
if (x < y) {
if (x < low) {
low = x;
}
if (high < y) {
high = y;
}
} else {
if (y < low) {
low = y;
}
if (high < x) {
high = x;
}
}
}
if (i === -1) {
x = A[0];
if (high < x) {
high = x;
} else if (x < low) {
low = x;
}
}
return [low, high];
}
for (var i = 0; i < 1000; ++i) { minmax(); }
Pero hombre, es bastante feo.
El algoritmo de nickf no es la mejor manera de hacer esto. En el peor de los casos, el algoritmo de nickf hace 2 comparaciones por número, para un total de 2n - 2.
Podemos hacerlo un poco mejor. Cuando comparas dos elementos a y b, si a> b sabemos que a no es el mínimo, yb no es el máximo. De esta manera usamos toda la información disponible para eliminar tantos elementos como podamos. Por simplicidad, supongamos que tenemos un número par de elementos.
Divídelas en pares: (a1, a2), (a3, a4), etc.
Compárelos, dividiéndolos en un grupo de ganadores y perdedores, esto toma n / 2 comparaciones, dándonos dos conjuntos de tamaño n / 2. Ahora encuentra el máximo de los ganadores y el mínimo de los perdedores.
Desde arriba, encontrar el mínimo o el máximo de n elementos toma n-1 compara. Por lo tanto, el tiempo de ejecución es: n / 2 (para las comparaciones iniciales) + n / 2 - 1 (máximo de ganadores) + n / 2 - 1 (min de los perdedores) = n / 2 + n / 2 + n / 2 -2 = 3n / 2 - 2. Si n es impar, tenemos un elemento más en cada uno de los conjuntos, por lo que el tiempo de ejecución será 3n / 2
De hecho, podemos demostrar que este es el más rápido que este problema puede ser posiblemente resuelto por cualquier algoritmo.
Un ejemplo:
Supongamos que nuestra matriz es 1, 5, 2, 3, 1, 8, 4 Divida en pares: (1,5), (2,3) (1,8), (4, -). Comparar. Los ganadores son: (5, 3, 8, 4). Los perdedores son (1, 2, 1, 4).
Escaneando los ganadores da 8. Escaneando los perdedores da 1.
Los arrays de Javascript tienen una función de clasificación nativa que acepta una función para usar en la comparación. Puede ordenar los números y simplemente tomar la cabeza y la cola para obtener el mínimo y el máximo.
var sorted = arrayOfNumbers.sort(function(a, b) { return a - b; }),
,min = sorted[0], max = sorted[sorted.length -1];
De forma predeterminada, el método de clasificación se ordena lexicográficamente (orden de diccionario), por lo que debe pasar una función para que se utilice para ordenar de forma numérica. La función que pasa debe devolver 1, -1 o 0 para determinar el orden de clasificación.
// standard sort function
function sorter(a, b) {
if (/* some check */)
return -1; // a should be left of b
if (/*some other check*/)
return 1; // a should be to the right of b
return 0; // a is equal to b (no movement)
}
En el caso de los números, simplemente puede restar el segundo del primer parametro para determinar el orden.
var numbers = [5,8,123,1,7,77,3.14,-5];
// default lexicographical sort
numbers.sort() // -5,1,123,3.14,5,7,77,8
// numerical sort
numbers.sort(function(a, b) { return a - b; }) // -5,1,123,3.14,5,7,77,8
este algoritmo funciona para O (n) y no se necesita más memoria adicional para almacenar elementos ...
enter code here
int l=0,h=1,index,i=3;
if(a[l]>a[h])
swap(&a[l],&a[h]);
for(i=2;i<9;i++)
{
if(a[i]<a[l])
{
swap(&a[i],&a[l]);
}
if(a[i]>a[h])
{
swap(&a[i],&a[h]);
}
}
printf("Low: %d High: %d",a[0],a[1]);
Aunque todavía es un algoritmo O (n), puede hacerlo un 25% más rápido (es decir, la constante de proporcionalidad es 3/2 frente a 2) comparando los elementos adyacentes primero por pares, luego comparando los más pequeños con los mínimos y los mayores con los máximos. No sé javascript, pero aquí está en C ++:
std::pair<int, int> minmax(int* a, int n)
{
int low = std::numeric_limits<int>::max();
int high = std::numeric_limits<int>::min();
for (int i = 0; i < n-1; i += 2) {
if (a[i] < a[i+i]) {
if (a[i] < low) {
low = a[i];
}
if (a[i+1] > high) {
high = a[i+1];
}
}
else {
if (a[i] > high) {
high = a[i];
}
if (a[i+1] < low) {
low = a[i+1];
}
}
}
// Handle last element if we''ve got an odd array size
if (a[n-1] < low) {
low = a[n-1];
}
if (a[n-1] > high) {
high = a[n-1];
}
return std::make_pair(low, high);
}
Tienes que hacerlo en el tiempo O(n) porque necesitas recorrer todos ( n ) los elementos para verificarlos porque cualquiera de los elementos puede ser el mínimo o el máximo. (A menos que ya estén clasificados)
En otras palabras, necesita recorrer todos los elementos y hacer la comprobación máxima y mínima como lo hizo.
La clasificación suele ser, en el mejor de los casos, O(n*log(n)) . Por lo tanto, es más lento que un solo barrido ( O(n) ).
Haciéndolo de la manera ES6 usando la sintaxis extendida :
var arrNums = [1, 2, 3, 4, 5];
Math.max(...arrNums) // 5
Math.min(...arrNums) // 1