javascript - objetos - elementos de una matriz ejemplos
¿Manera eficiente de insertar un número en una matriz ordenada de números? (11)
Tengo una matriz de JavaScript ordenada, y quiero insertar un elemento más en la matriz, por lo que la matriz resultante permanece ordenada. Definitivamente podría implementar una función de inserción simple estilo quicksort:
var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
array.splice(locationOf(element, array) + 1, 0, element);
return array;
}
function locationOf(element, array, start, end) {
start = start || 0;
end = end || array.length;
var pivot = parseInt(start + (end - start) / 2, 10);
if (end-start <= 1 || array[pivot] === element) return pivot;
if (array[pivot] < element) {
return locationOf(element, array, pivot, end);
} else {
return locationOf(element, array, start, pivot);
}
}
console.log(insert(element, array));
[ADVERTENCIA] este código tiene un error al intentar insertar al principio de la matriz, por ejemplo, insert(2, [3, 7 ,9] ) produce errores [3, 2, 7, 9].
Sin embargo, noté que las implementaciones de la función Array.sort podrían hacer esto por mí, y de forma nativa:
var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
array.push(element);
array.sort(function(a, b) {
return a - b;
});
return array;
}
console.log(insert(element, array));
¿Hay una buena razón para elegir la primera implementación sobre la segunda?
Editar : Tenga en cuenta que, para el caso general, una inserción O (log (n)) (como se implementó en el primer ejemplo) será más rápida que un algoritmo de clasificación genérico; sin embargo, este no es necesariamente el caso de JavaScript en particular. Tenga en cuenta que:
- El mejor caso para varios algoritmos de inserción es O (n), que todavía es significativamente diferente de O (log (n)), pero no tan malo como O (n log (n)) como se menciona a continuación. Dependería del algoritmo de clasificación particular usado (ver la implementación de Javascript Array.sort? )
- El método de ordenación en JavaScript es una función nativa, por lo que es posible obtener enormes beneficios: O (log (n)) con un gran coeficiente puede ser mucho peor que O (n) para conjuntos de datos de tamaño razonable.
Aquí hay algunas ideas: en primer lugar, si realmente está preocupado por el tiempo de ejecución de su código, asegúrese de saber qué sucede cuando llama a las funciones incorporadas. No sé desde arriba en javascript, pero un google rápido de la función de empalme devolvió this , lo que parece indicar que está creando una matriz completamente nueva en cada llamada. No sé si realmente importa, pero ciertamente está relacionado con la eficiencia. Veo que Breton, en los comentarios, ya lo ha señalado, pero ciertamente es válido para cualquier función de manipulación de matrices que elijas.
De todos modos, en realidad resolver el problema.
Cuando leí que quería ordenar, ¡mi primer pensamiento es utilizar el género de inserción! . Es útil porque se ejecuta en tiempo lineal en listas ordenadas o casi ordenadas . Como sus matrices tendrán solo 1 elemento fuera de servicio, eso cuenta como casi ordenado (excepto, por ejemplo, matrices de tamaño 2 o 3 o lo que sea, pero en ese punto, vamos). Ahora, implementar el género no es tan malo, pero es una molestia con la que no querrás lidiar, y nuevamente, no sé nada sobre javascript y si será fácil o difícil o lo que sea. Esto elimina la necesidad de su función de búsqueda, y simplemente empuja (como sugirió Breton).
¡En segundo lugar, su función de búsqueda "quicksort-esque" parece ser un algoritmo de búsqueda binario ! Es un algoritmo muy agradable, intuitivo y rápido, pero con una sola pega: es notoriamente difícil de implementar correctamente. No me atrevería a decir si el tuyo es correcto o no (¡espero que lo sea, por supuesto! :)), pero desconfía si quieres usarlo.
De todos modos, resumen: usar "push" con ordenación de inserción funcionará en tiempo lineal (suponiendo que el resto de la matriz esté ordenada) y evite cualquier requisito de algoritmo de búsqueda binaria desordenado. No sé si esta es la mejor manera (la implementación subyacente de las matrices, quizás una función loca incorporada lo hace mejor, quién sabe), pero me parece razonable. :) - Agor.
Aquí hay una comparación de cuatro algoritmos diferentes para lograr esto: https://jsperf.com/sorted-array-insert-comparison/1
Algoritmos
- Ingenuo: solo presiona y ordena () luego
- Lineal: iterar sobre la matriz e insertar cuando corresponda
- Búsqueda binaria: tomada de https://.com/a/20352387/154329
- "Quick Sort Like": la solución refinada de syntheticzero ( https://.com/a/18341744/154329 )
Naive es siempre horrible. Parece que para tamaños de matriz pequeños, los otros tres no difieren demasiado, pero para arreglos más grandes, los últimos 2 superan al enfoque lineal simple.
Como un solo punto de datos, para las patadas lo probé insertando 1000 elementos aleatorios en una matriz de 100.000 números ordenados previamente utilizando los dos métodos que usan Chrome en Windows 7:
First Method:
~54 milliseconds
Second Method:
~57 seconds
Por lo tanto, al menos en esta configuración, el método nativo no lo compensa. Esto es cierto incluso para conjuntos de datos pequeños, insertando 100 elementos en una matriz de 1000:
First Method:
1 milliseconds
Second Method:
34 milliseconds
Hay un error en tu código. Debe leer:
function locationOf(element, array, start, end) {
start = start || 0;
end = end || array.length;
var pivot = parseInt(start + (end - start) / 2, 10);
if (array[pivot] === element) return pivot;
if (end - start <= 1)
return array[pivot] > element ? pivot - 1 : pivot;
if (array[pivot] < element) {
return locationOf(element, array, pivot, end);
} else {
return locationOf(element, array, start, pivot);
}
}
Sin esta corrección, el código nunca podrá insertar un elemento al comienzo de la matriz.
Muy buena y notable pregunta con una discusión muy interesante! También estaba usando la función Array.sort() después de empujar un solo elemento en una matriz con algunos miles de objetos.
Tuve que ampliar su función locationOf para mi propósito debido a tener objetos complejos y, por lo tanto, la necesidad de una función de comparación como en Array.sort() :
function locationOf(element, array, comparer, start, end) {
if (array.length === 0)
return -1;
start = start || 0;
end = end || array.length;
var pivot = (start + end) >> 1; // should be faster than dividing by 2
var c = comparer(element, array[pivot]);
if (end - start <= 1) return c == -1 ? pivot - 1 : pivot;
switch (c) {
case -1: return locationOf(element, array, comparer, start, pivot);
case 0: return pivot;
case 1: return locationOf(element, array, comparer, pivot, end);
};
};
// sample for objects like {lastName: ''Miller'', ...}
var patientCompare = function (a, b) {
if (a.lastName < b.lastName) return -1;
if (a.lastName > b.lastName) return 1;
return 0;
};
No vuelva a clasificar después de cada artículo, es excesivo.
Si solo hay un elemento para insertar, puede encontrar la ubicación para insertar utilizando la búsqueda binaria. Luego use memcpy o similar para copiar a granel los elementos restantes para dejar espacio para el insertado. La búsqueda binaria es O (log n), y la copia es O (n), dando O (n + log n) total. Usando los métodos de arriba, está haciendo un reordenamiento después de cada inserción, que es O (n log n).
¿Importa? Digamos que estás insertando aleatoriamente elementos k, donde k = 1000. La lista ordenada es de 5000 elementos.
-
Binary search + Move = k*(n + log n) = 1000*(5000 + 12) = 5,000,012 = ~5 million ops -
Re-sort on each = k*(n log n) = ~60 million ops
Si los k elementos para insertar llegan cada vez, entonces debe hacer la búsqueda + mover. Sin embargo, si le dan una lista de k elementos para insertar en una matriz ordenada, antes de tiempo, puede hacerlo aún mejor. Ordene los elementos k, por separado de la matriz n ya ordenada. A continuación, realice una ordenación por barrido, en la que mueva hacia abajo ambas matrices ordenadas simultáneamente, fusionando una en la otra. - Tipo de combinación en un solo paso = k log k + n = 9965 + 5000 = ~ 15,000 ops
Actualización: con respecto a su pregunta.
First method = binary search+move = O(n + log n) . Second method = re-sort = O(n log n) Explica exactamente los tiempos que estás recibiendo.
Para una pequeña cantidad de artículos, la diferencia es bastante trivial. Sin embargo, si está insertando muchos elementos o trabajando con una matriz muy grande, llamar .sort () después de cada inserción causará una gran cantidad de sobrecarga.
Terminé escribiendo una función de búsqueda / inserción binaria bastante elegante para este propósito exacto, así que pensé en compartirla. Dado que utiliza un ciclo while en lugar de recursión, no se escuchan las llamadas a funciones adicionales, por lo que creo que el rendimiento será incluso mejor que cualquiera de los métodos publicados originalmente. Y emula el Array.sort() predeterminado Array.sort() de forma predeterminada, pero acepta una función de comparador personalizado si lo desea.
function insertSorted(arr, item, comparator) {
if (comparator == null) {
// emulate the default Array.sort() comparator
comparator = function(a, b) {
if (typeof a !== ''string'') a = String(a);
if (typeof b !== ''string'') b = String(b);
return (a > b ? 1 : (a < b ? -1 : 0));
};
}
// get the index we need to insert the item at
var min = 0;
var max = arr.length;
var index = Math.floor((min + max) / 2);
while (max > min) {
if (comparator(item, arr[index]) < 0) {
max = index;
} else {
min = index + 1;
}
index = Math.floor((min + max) / 2);
}
// insert the item
arr.splice(index, 0, item);
};
Si está abierto para usar otras bibliotecas, lodash proporciona funciones sortedIndex y sortedLastIndex , que podrían usarse en lugar del ciclo while. Las dos desventajas potenciales son 1) el rendimiento no es tan bueno como mi método (pensé que no estoy seguro de cuánto peor es) y 2) no acepta una función de comparación personalizada, solo un método para obtener el valor para comparar (usando el comparador predeterminado, supongo).
Sé que esta es una vieja pregunta que ya tiene una respuesta, y hay otras respuestas decentes. Veo algunas respuestas que proponen que puede resolver este problema buscando el índice de inserción correcto en O (log n); puede, pero no puede insertarlo en ese momento, porque la matriz debe ser parcialmente copiada para hacer espacio.
En pocas palabras: si realmente necesita O (log n) inserta y elimina en una matriz ordenada, necesita una estructura de datos diferente, no una matriz. Deberías usar un B-Tree . Las mejoras de rendimiento que obtendrá al usar un B-Tree para un gran conjunto de datos, eclipsarán cualquiera de las mejoras que se ofrecen aquí.
Si debe usar una matriz. Ofrezco el siguiente código, basado en la ordenación por inserción, que funciona, si y solo si la matriz ya está ordenada. Esto es útil para el caso en que necesite recurrir después de cada inserción:
function addAndSort(arr, val) {
arr.push(val);
for (i = arr.length - 1; i > 0 && arr[i] < arr[i-1]; i--) {
var tmp = arr[i];
arr[i] = arr[i-1];
arr[i-1] = tmp;
}
return arr;
}
Debería funcionar en O (n), que creo que es lo mejor que puede hacer. Sería mejor si js admitiera asignaciones múltiples. aquí hay un ejemplo para jugar:
Actualizar:
esto podría ser más rápido:
function addAndSort2(arr, val) {
arr.push(val);
i = arr.length - 1;
item = arr[i];
while (i > 0 && item < arr[i-1]) {
arr[i] = arr[i-1];
i -= 1;
}
arr[i] = item;
return arr;
}
Simple ( Demo ):
function sortedIndex(array, value) {
var low = 0,
high = array.length;
while (low < high) {
var mid = (low + high) >>> 1;
if (array[mid] < value) low = mid + 1;
else high = mid;
}
return low;
}
Su función de inserción asume que la matriz dada está ordenada, busca directamente la ubicación donde se puede insertar el nuevo elemento, generalmente con solo mirar algunos de los elementos en la matriz.
La función de clasificación general de una matriz no puede tomar estos atajos. Obviamente, al menos tiene que inspeccionar todos los elementos en la matriz para ver si ya están correctamente ordenados. Este solo hecho hace que el género general sea más lento que la función de inserción.
Un algoritmo de clasificación genérico suele ser, en promedio, O (n ⋅ log (n)) y, dependiendo de la implementación, podría ser el peor de los casos si la matriz ya está ordenada, lo que lleva a complejidades de O (n 2 ) . La búsqueda directa de la posición de inserción solo tiene una complejidad de O (log (n)) , por lo que siempre será mucho más rápido.
function insertOrdered(array, elem) {
let _array = array;
let i = 0;
while ( i < array.length && array[i] < elem ) {i ++};
_array.splice(i, 0, elem);
return _array;
}