javascript - array - sorting algorithms comparison
¿Cómo reorganizar una matriz por índices matriz? (9)
Dada una matriz arr y una matriz de ind índices, me gustaría reorganizar arr in-place para satisfacer los índices dados. Por ejemplo:
var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];
rearrange(arr, ind);
console.log(arr); // => ["B", "E", "D", "F", "A", "C"]
Aquí hay una posible solución que usa O(n) time y O(1) space, pero muta ind :
function swap(arr, i, k) {
var temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
function rearrange(arr, ind) {
for (var i = 0, len = arr.length; i < len; i++) {
if (ind[i] !== i) {
swap(arr, i, ind[i]);
swap(ind, i, ind[i]);
}
}
}
¿Cuál sería la solución óptima si estamos limitados a O(1) espacio y no está permitido mutar?
Editar: el algoritmo anterior es incorrecto. Ver esta pregunta
A continuación, se puede encontrar una solución PARCIAL para un caso cuando solo tenemos UN ciclo, es decir,
var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 2, 5, 0, 1, 3];
function rearrange( i, arr, ind, temp ){
if( temp ){
if( arr[ind[i]] ){
var temp2 = arr[ind[i]];
arr[ind[i]] = temp;
rearrange( ind[i], arr, ind, temp2 );
}
else{ // cycle
arr[ind[i]] = temp;
// var unvisited_index = ...;
// if( unvisited_index ) rearrange( unvisited_index, arr, ind, "" );
}
}
else{
if( i == ind[i] ){
if( i < arr.length ) rearrange( i + 1, arr, ind, temp );
}
else{
temp = arr[ind[i]];
arr[ind[i]]=arr[i];
arr[i] = "";
i = ind[i];
rearrange(i, arr, ind, temp );
}
}
}
rearrange( 0, arr, ind, "" );
Para que esta solución funcione para un caso general, necesitamos encontrar números totales de ciclos únicos y un índice de cada uno de ellos.
Para el ejemplo OP :
var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];
Hay 2 ciclos únicos:
4 -> 1 -> 0 -> 4
5 -> 3 -> 2 -> 5
Si uno corre
rearrange( 0, arr, ind, "" );
rearrange( 5, arr, ind, "" );
S (él) obtendrá la salida deseable para el problema OP .
Esta es la solución de "bit de signo".
Dado que esta es una pregunta de JavaScript y los literales numéricos especificados en la matriz ind se almacenan, por lo tanto, como flotantes con signo, hay un bit de signo disponible en el espacio utilizado por la entrada.
Este algoritmo recorre los elementos de acuerdo con la matriz ind y desplaza los elementos a su lugar hasta que llega al primer elemento de ese ciclo. Luego encuentra el siguiente ciclo y repite el mismo mecanismo.
La matriz ind se modifica durante la ejecución, pero se restaurará a su original al finalizar el algoritmo. En uno de los comentarios que mencionaste, esto es aceptable.
La matriz ind consta de flotantes con signo, aunque todos son no negativos (enteros). El bit de signo se usa como indicador de si el valor ya se procesó o no. En general, esto podría considerarse almacenamiento adicional ( n bits, es decir, O (n) ), pero como el almacenamiento ya está ocupado por la entrada, no es un espacio adicional adquirido. Los bits de signo de los valores ind que representan el miembro más a la izquierda de un ciclo no se modifican.
Editar: Reemplacé el uso del operador ~ , ya que no produce los resultados deseados para números iguales o superiores a 2 31 , mientras que JavaScript debe admitir números que se utilizarán como índices de matriz de hasta al menos 2 32 - 1 . Entonces, en su lugar, ahora uso k = -k-1 , que es lo mismo, pero funciona para toda la gama de flotadores que es segura para usar como enteros. Tenga en cuenta que como alternativa uno podría usar un poco de la parte fraccional del flotador (+/- 0.5).
Aquí está el código:
var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];
rearrange(arr, ind);
console.log(''arr: '' + arr);
console.log(''ind: '' + ind);
function rearrange(arr, ind) {
var i, j, buf, temp;
for (j = 0; j < ind.length; j++) {
if (ind[j] >= 0) { // Found a cycle to resolve
i = ind[j];
buf = arr[j];
while (i !== j) { // Not yet back at start of cycle
// Swap buffer with element content
temp = buf;
buf = arr[i];
arr[i] = temp;
// Invert bits, making it negative, to mark as visited
ind[i] = -ind[i]-1;
// Visit next element in cycle
i = -ind[i]-1;
}
// dump buffer into final (=first) element of cycle
arr[j] = buf;
} else {
ind[j] = -ind[j]-1; // restore
}
}
}
Aunque el algoritmo tiene un bucle anidado, todavía se ejecuta en el tiempo O (n) : el intercambio solo ocurre una vez por elemento, y también el bucle externo visita cada elemento solo una vez.
Las declaraciones de variables muestran que el uso de la memoria es constante, pero con la observación de que también se utilizan los bits de signo de los elementos ind array, en el espacio ya asignado por la entrada.
Esta propuesta utiliza la answer de Evgeny Kluev.
Hice una extensión para un procesamiento más rápido, si todos los elementos ya están tratados, pero el índice no ha llegado a cero. Esto se hace con un count variables adicional, que cuenta regresivamente para cada elemento reemplazado. Esto se usa para abandonar el ciclo principal si todos los elementos están en la posición correcta ( count = 0 ).
Esto es útil para anillos, como en el primer ejemplo con
["A", "B", "C", "D", "E", "F"]
[ 4, 0, 5, 2, 1, 3 ]
index 5: 3 -> 2 -> 5 -> 3
index 4: 1 -> 0 -> 4 -> 1
Ambos anillos son al principio dos bucles reorganizados y mientras que cada anillo tiene 3 elementos, el count ahora es cero. Esto conduce a un cortocircuito para el ciclo while externo.
function rearrange(values, indices) {
var count = indices.length, index = count, next;
main: while (count && index--) {
next = index;
do {
next = indices[next];
if (next > index) continue main;
} while (next !== index)
do {
next = indices[next];
count--;
values[index] = [values[next], values[next] = values[index]][0];
} while (next !== index)
}
}
function go(values, indices) {
rearrange(values, indices);
console.log(values);
}
go(["A", "B", "C", "D", "E", "F"], [4, 0, 5, 2, 1, 3]);
go(["A", "B", "C", "D", "E", "F"], [1, 2, 0, 4, 5, 3]);
go(["A", "B", "C", "D", "E", "F"], [5, 0, 1, 2, 3, 4]);
go(["A", "B", "C", "D", "E", "F"], [0, 1, 3, 2, 4, 5]);
Estoy usando ind como índices en su propio orden
var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];
var obj = {}
for(var i=0;i<arr.length;i++)
obj[ind[i]]=arr[i];
console.log(obj);
La matriz de índice define una permutación. Cada permutación consiste en ciclos. Podríamos reorganizar la matriz dada siguiendo cada ciclo y reemplazando los elementos de la matriz a lo largo del camino.
El único problema aquí es seguir cada ciclo exactamente una vez. Una forma posible de hacerlo es procesar los elementos de la matriz en orden y para cada uno de ellos inspeccionar el ciclo que atraviesa este elemento. Si dicho ciclo toca al menos un elemento con índice menor, los elementos a lo largo de este ciclo ya están permutados. De lo contrario, seguimos este ciclo y reordenamos los elementos.
function rearrange(values, indexes) {
main_loop:
for (var start = 0, len = indexes.length; start < len; start++) {
var next = indexes[start];
for (; next != start; next = indexes[next])
if (next < start) continue main_loop;
next = start;
var tmp = values[start];
do {
next = indexes[next];
tmp = [values[next], values[next] = tmp][0]; // swap
} while (next != start);
}
return values;
}
Este algoritmo sobrescribe cada elemento de la matriz dada exactamente una vez, no muta la matriz de índice (incluso temporalmente). Su peor complejidad es O (n 2 ). Pero para las permutaciones aleatorias, su complejidad esperada es O (n log n) (como se señala en los comentarios para la respuesta relacionada ).
Este algoritmo podría optimizarse un poco. La optimización más obvia es utilizar un conjunto de bits corto para mantener la información sobre varios índices antes de la posición actual (ya sea que ya estén procesados o no). Usar una sola palabra de 32 o 64 bits para implementar este conjunto de bits no debe violar el requisito de espacio O (1). Tal optimización daría una mejora de velocidad pequeña pero notable. Aunque no cambia el peor de los casos y las complejidades asintóticas esperadas.
Para optimizar más, podríamos usar temporalmente la matriz de índices. Si los elementos de esta matriz tienen al menos un bit de reserva, podríamos usarlo para mantener un conjunto de bits que nos permita realizar un seguimiento de todos los elementos procesados, lo que da como resultado un algoritmo de tiempo lineal simple. Pero no creo que esto pueda considerarse como un algoritmo espacial O (1). Así que supongo que esa matriz de índices no tiene bits de reserva.
Aún así, la matriz de índice podría darnos un espacio (mucho más grande que una sola palabra) para el conjunto de bits anticipado. Debido a que esta matriz define una permutación, contiene mucha menos información que una matriz arbitraria del mismo tamaño. La aproximación de Stirling para ln(n!) Proporciona n ln n bits de información, mientras que la matriz podría almacenar n log n bits. La diferencia entre los logaritmos naturales y binarios nos da aproximadamente el 30% del espacio libre potencial. También podríamos extraer hasta 1/64 = 1.5% o 1/32 = 3% de espacio libre si el tamaño de la matriz no es exactamente una potencia de dos, o en otras palabras, si el bit de orden superior solo se usa parcialmente . (Y estos 1.5% podrían ser mucho más valiosos que los garantizados 30%).
La idea es comprimir todos los índices a la izquierda de la posición actual (porque nunca los usa el algoritmo), usar parte del espacio libre entre los datos comprimidos y la posición actual para almacenar un conjunto de bits anticipado (para aumentar el rendimiento del algoritmo principal) ), use otra parte del espacio libre para aumentar el rendimiento del algoritmo de compresión en sí mismo (de lo contrario, necesitaremos solo un tiempo cuadrático para la compresión) y, finalmente, descomprimir todos los índices de nuevo en su forma original.
Para comprimir los índices, podemos usar el sistema de número factorial: escanee la matriz de índices para encontrar cuántos de ellos son menores que el índice actual, coloque el resultado en flujo comprimido y use el espacio libre disponible para procesar varios valores a la vez.
La desventaja de este método es que la mayor parte del espacio libre se produce cuando el algoritmo llega al final de la matriz, mientras que este espacio es más necesario cuando estamos en el comienzo. Como resultado, es probable que la complejidad del peor caso sea solo ligeramente menor que O (n 2 ). Esto también podría aumentar la complejidad esperada si no fuera por este simple truco: use el algoritmo original (sin compresión) mientras sea lo suficientemente barato, luego cambie a la variante "comprimida".
Si la longitud de la matriz no es una potencia de 2 (y tenemos un bit de orden alto parcialmente no utilizado), podríamos ignorar el hecho de que la matriz de índices contiene una permutación y empacar todos los índices como si fuera un sistema numérico básico. Esto permite reducir en gran medida la complejidad asintótica del peor caso, así como acelerar el algoritmo en "caso promedio".
No estoy seguro de la hora, pero la función de mapa parece hacer lo que se solicitó. Es una opción, pero como no conozco el funcionamiento interno de .map, no puedo asegurar que esto sea lo que estás buscando.
var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];
arr = ind.map(function(value)
{ return arr[value]; });
Otra solución que no usa la función de mapa podría verse más o menos así:
var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];
var temp = [];
for (var i = 0, ind_length = ind.length; i < ind_length; i++)
{
var set_index = ind[i];
temp.push(arr[set_index]);
delete arr[set_index];
}
arr = temp;
Esto hace un buen uso del espacio al usar la opción de borrar que también evita que los índices cambien. Como solo hace un ciclo, imagino que la ejecución es bastante rápida. Dado que los comandos son muy simples y básicos, esta debería ser una solución viable. No es exactamente lo que se preguntó, que era un intercambio sin espacio adicional, pero se acerca bastante. Soy nuevo para responder preguntas como esta, así que por favor ... crítica constructiva.
Prueba esto:
var result = new Array(5);
for (int i = 0; i < result.length; i++) {
result[i] = arr[ind[i]];
}
console.log(arr);
Esta respuesta ha sido actualizada para satisfacer las condiciones de OP
En esta respuesta, no hay matrices temporales y la matriz ind no se reorganiza ni se ordena por ningún medio. Todas las operaciones de reemplazo se realizan en una sola pasada. getItemIndex función getItemIndex recibe solo una porción superficial de la matriz ind para trabajar. Simplemente se hace mediante el aprovechamiento de toda la información oculta en la matriz ind .
Es clave entender que la matriz ind guarda toda la historia para nosotros.
Tenemos la siguiente información al examinar la matriz ind .
- Al mirar los elementos, encontramos el mapa de índice del elemento correspondiente en la matriz de
arr. - Cada índice de artículos nos dice cuántos canjes se hicieron antes. Obtenemos historia.
- Cada índice de artículos también indica si hubo un intercambio previo relacionado con la posición del índice actual donde fue el elemento anterior. Podemos hacer como
ind.indexOf(i); De todos modos aquí está el código;
He agregado algunas funciones como Array.prototype.swap() para hacer que el código sea más fácil de interpretar. Aquí está el código.
Array.prototype.swap = function(i,j){
[this[i],this[j]] = [this[j],this[i]];
return this;
};
function getItemIndex(a,i){
var f = a.indexOf(i);
return f !=-1 ? getItemIndex(a,f) : i;
}
function sort(arr,ind){
ind.forEach((n,i,x) => x.indexOf(i) > i ? arr.swap(i,x[i]) // item has not changed before so we can swap
: arr.swap(getItemIndex(ind.slice(0,i),i),x[i])); // item has gone to somwhere in previous swaps get it''s index and swap
return arr;
}
var arr = ["A", "B", "C", "D", "E", "F"],
ind = [4, 0, 5, 2, 1, 3];
console.log(sort(arr,ind),ind);
Ok, la última versión de este código es esto. Es muy simplificado e incluye un caso de prueba con 26 letras. Cada vez que ejecute obtendrá un mapa de índices únicos puramente aleatorio diferente.
Array.prototype.swap = function(i,j){
i !=j && ([this[i],this[j]] = [this[j],this[i]]);
return this;
};
Array.prototype.shuffle = function(){
var i = this.length,
j;
while (i > 1) {
j = ~~(Math.random()*i--);
[this[i],this[j]] = [this[j],this[i]];
}
return this;
};
var arr = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"],
ind = (new Array(arr.length)).fill("").map((e,i) => e = i).shuffle();
console.log(JSON.stringify(arr));
console.log(JSON.stringify(ind));
function getItemIndex(a,i,j){
var f = a.indexOf(i);
return f < j ? getItemIndex(a,f,j) : i;
}
function sort(arr,ind){
ind.forEach((n,i,x) => arr.swap(getItemIndex(ind,i,i),n));
return arr;
}
console.log(JSON.stringify(sort(arr,ind)));
console.log(JSON.stringify(ind));
Así que está bien, según el comentario de Trincot aquí, va con una función iterativa getItemIndex() .
Array.prototype.swap = function(i,j){
i !=j && ([this[i],this[j]] = [this[j],this[i]]);
return this;
};
Array.prototype.shuffle = function(){
var i = this.length,
j;
while (i > 1) {
j = ~~(Math.random()*i--);
[this[i],this[j]] = [this[j],this[i]];
}
return this;
};
var arr = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"],
ind = (new Array(arr.length)).fill("").map((e,i) => e = i).shuffle();
console.log(JSON.stringify(arr));
console.log(JSON.stringify(ind));
function getItemIndex(a,i){
var f = a.indexOf(i),
j;
if (f >= i) return i; // this element hasn''t been moved before.
while (f < i) { // this element has been swapped so get this elements current index
j = f;
f = a.indexOf(f);
}
return j;
}
function sort(arr,ind){
ind.forEach((n,i,x) => arr.swap(getItemIndex(ind,i),n));
return arr;
}
console.log(JSON.stringify(sort(arr,ind)));
console.log(JSON.stringify(ind));
var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];
function rearrange(arr, ind){
var map = [];
for (var i = 0; i < arr.length; i++) map[ind[i]] = arr[i];
for (var i = 0; i < arr.length; i++) arr[i] = map[i];
}
rearrange(arr, ind);
console.log(arr);
Eso funciona pero, como no soy un desarrollador inteligente, supongo que probablemente no sea el algoritmo más rápido.