Reordena el vector usando un vector de índices

Me gustaría reordenar los elementos en un vector, usando otro vector para especificar el orden:

char A[] = { 'a', 'b', 'c' }; size_t ORDER[] = { 1, 0, 2 }; vector vA(A, A + sizeof(A) / sizeof(*A)); vector vOrder(ORDER, ORDER + sizeof(ORDER) / sizeof(*ORDER)); 
reorder_naive(vA, vOrder);
// A is now { 'b', 'a', 'c' }

La siguiente es una implementación ineficiente que requiere copiar el vector:

 void reorder_naive(vector& vA, const vector& vOrder) { assert(vA.size() == vOrder.size()); vector vCopy = vA; // Can we avoid this? for(int i = 0; i < vOrder.size(); ++i) vA[i] = vCopy[ vOrder[i] ]; } 

¿Hay una manera más eficiente, por ejemplo, que usa swap ()?

Mejoré el algoritmo de chmike. ¡Esta función concuerda con la de él para los 11! permutaciones de (0..10) pasadas como el vector de reordenamiento. Además, no modifica el vector de reordenamiento.

 template< class T > void reorder(vector &v, vector const &order ) { for ( int s = 1, d; s < order.size(); ++ s ) { for ( d = order[s]; d < s; d = order[d] ) ; if ( d == s ) while ( d = order[d], d != s ) swap( v[s], v[d] ); } } 

Aquí hay una versión de estilo STL en la que puse un poco más de esfuerzo. Es aproximadamente un 47% más rápido (es decir, casi dos veces más rápido que (0..10)!) Porque realiza todos los intercambios tan pronto como sea posible y luego regresa. El vector de reordenamiento consiste en varias órbitas, y cada órbita se reordena al llegar a su primer miembro. Es más rápido cuando los últimos elementos no contienen una órbita.

 template< typename order_iterator, typename value_iterator > void reorder( order_iterator order_begin, order_iterator order_end, value_iterator v ) { typedef typename iterator_traits< value_iterator >::value_type value_t; typedef typename iterator_traits< order_iterator >::value_type index_t; typedef typename iterator_traits< order_iterator >::difference_type diff_t; diff_t remaining = order_end - 1 - order_begin; for ( index_t s = index_t(), d; remaining > 0; ++ s ) { for ( d = order_begin[s]; d > s; d = order_begin[d] ) ; if ( d == s ) { -- remaining; value_t temp = v[s]; while ( d = order_begin[d], d != s ) { swap( temp, v[d] ); -- remaining; } v[s] = temp; } } } 

Y finalmente, solo para responder la pregunta de una vez por todas, una variante que destruye el vector de reorden. (Lo llena con -1). Es aproximadamente un 16% más rápido que la versión anterior. Este utiliza un tipo de feo, pero lidiar con eso. ¡Esto cubre 11! ~ = 40 mil permutaciones de 11 caracteres en 4.25 segundos, sin contar los gastos generales, en mi computadora portátil de 2.2 GHz.

 template< typename order_iterator, typename value_iterator > void reorder_destructive( order_iterator order_begin, order_iterator order_end, value_iterator v ) { typedef typename iterator_traits< value_iterator >::value_type value_t; typedef typename iterator_traits< order_iterator >::value_type index_t; typedef typename iterator_traits< order_iterator >::difference_type diff_t; diff_t remaining = order_end - 1 - order_begin; for ( index_t s = index_t(); remaining > 0; ++ s ) { index_t d = order_begin[s]; if ( d == (diff_t) -1 ) continue; -- remaining; value_t temp = v[s]; for ( index_t d2; d != s; d = d2 ) { swap( temp, v[d] ); swap( order_begin[d], d2 = (diff_t) -1 ); -- remaining; } v[s] = temp; } } 

Aquí está el código correcto

 void REORDER(vector& vA, vector& vOrder) { assert(vA.size() == vOrder.size()); // for all elements to put in place for( int i = 0; i < va.size() - 1; ++i ) { // while the element i is not yet in place while( i != vOrder[i] ) { // swap it with the element at its final place int alt = vOrder[i]; swap( vA[i], vA[alt] ); swap( vOrder[i], vOrder[alt] ); } } } 

tenga en cuenta que puede guardar una prueba porque si n-1 elementos están en su lugar, el último n-ésimo elemento ciertamente está en su lugar.

En la salida vA y vOrder están ordenadas correctamente.

Este algoritmo realiza como máximo intercambio n-1 porque cada intercambio mueve el elemento a su posición final. Y tendremos que hacer como máximo 2N pruebas en vOrder.

Si está bien modificar la matriz ORDER, entonces una implementación que ordena el vector ORDER y en cada operación de clasificación también intercambia los valores correspondientes, los elementos vectoriales podrían hacer el truco, creo.

Me parece que vOrder contiene un conjunto de índices en el orden deseado (por ejemplo, la salida de clasificación por índice). El ejemplo del código aquí es una variación del tipo de ciclo. Cada intercambio coloca al menos un elemento en su lugar apropiado. Este ejemplo de código reordena efectivamente vA de acuerdo con vOrder, mientras “desordena” o “no modifica” vOrder a su estado original (0 :: n-1). Si vA contenía los valores 0 a n-1 en orden, luego de reordenar, vA terminaría donde se inició vOrder.

 template  void reorder(vector& vA, vector& vOrder) { assert(vA.size() == vOrder.size()); // for all elements to put in place for( size_t i = 0; i < vA.size(); ++i ) { // while vOrder[i] is not yet in place // every swap places at least one element in it's proper place while( vOrder[i] != vOrder[vOrder[i]] ) { swap( vA[vOrder[i]], vA[vOrder[vOrder[i]]] ); swap( vOrder[i], vOrder[vOrder[i]] ); } } } 

Esto también se puede implementar de una manera más eficiente usando movimientos en lugar de intercambios. Se necesita un objeto temporal para mantener un elemento durante los movimientos. El código del ejemplo C, reordena A [] según los índices en I [], también ordena I []:

 void reorder(int *A, int *I) { int i, j, k; int tA; /* reorder A according to I */ /* every move puts an element into place */ /* time complexity is O(n) */ for(i = 0; i < sizeof(A)/sizeof(A[0]); i++){ if(i != I[i]){ tA = A[i]; j = i; while(i != (k = I[j])){ A[j] = A[k]; I[j] = j; j = k; } A[j] = tA; I[j] = j; } } } 

Nunca optimice prematuramente. Mida y luego determine dónde necesita optimizar y qué. Puede terminar con un código complejo que es difícil de mantener y propenso a errores en muchos lugares donde el rendimiento no es un problema.

Dicho eso, no pesen temprano. Sin cambiar el código, puede eliminar la mitad de sus copias:

  template  void reorder( std::vector & data, std::vector const & order ) { std::vector tmp; // create an empty vector tmp.reserve( data.size() ); // ensure memory and avoid moves in the vector for ( std::size_t i = 0; i < order.size(); ++i ) { tmp.push_back( data[order[i]] ); } data.swap( tmp ); // swap vector contents } 

Este código crea un vector vacío (lo suficientemente grande) en el que se realiza una sola copia en orden. Al final, los vectores ordenados y originales se intercambian. Esto reducirá las copias, pero aún requiere memoria extra.

Si desea realizar los movimientos en el lugar, un algoritmo simple podría ser:

 template  void reorder( std::vector & data, std::vector const & order ) { for ( std::size_t i = 0; i < order.size(); ++i ) { std::size_t original = order[i]; while ( i < original ) { original = order[original]; } std::swap( data[i], data[original] ); } } 

Este código debe ser verificado y depurado. En palabras simples, el algoritmo en cada paso posiciona el elemento en la posición i-ésima. Primero determinamos dónde se coloca el elemento original para esa posición en el vector de datos. Si la posición original ya ha sido tocada por el algoritmo (está antes de la posición i-ésima), entonces el elemento original fue cambiado a la posición [original] de la orden. Por otra parte, ese elemento ya puede haberse movido ...

Este algoritmo es aproximadamente O (N ^ 2) en el número de operaciones enteras y, por tanto, teóricamente es peor en el tiempo de rendimiento que el algoritmo inicial O (N). Pero puede compensar si las operaciones de intercambio N ^ 2 (el peor de los casos) cuestan menos que las operaciones de copia de N o si está realmente limitado por la huella de memoria.

Podrías hacerlo recursivamente, supongo – algo como esto (sin marcar, pero da la idea):

 // Recursive function template void REORDER(int oldPosition, vector& vA, const vector& vecNewOrder, vector& vecVisited) { // Keep a record of the value currently in that position, // as well as the position we're moving it to. // But don't move it yet, or we'll overwrite whatever's at the next // position. Instead, we first move what's at the next position. // To guard against loops, we look at vecVisited, and set it to true // once we've visited a position. T oldVal = vA[oldPosition]; int newPos = vecNewOrder[oldPosition]; if (vecVisited[oldPosition]) { // We've hit a loop. Set it and return. vA[newPosition] = oldVal; return; } // Guard against loops: vecVisited[oldPosition] = true; // Recursively re-order the next item in the sequence. REORDER(newPos, vA, vecNewOrder, vecVisited); // And, after we've set this new value, vA[newPosition] = oldVal; } // The "main" function template void REORDER(vector& vA, const vector& newOrder) { // Initialise vecVisited with false values vector vecVisited(vA.size(), false); for (int x = 0; x < vA.size(); x++) { REORDER(x, vA, newOrder, vecVisited); } } 

Por supuesto, usted tiene la sobrecarga de vecVisited. Pensamientos sobre este enfoque, ¿alguien?

Para iterar a través del vector está la operación O (n). Es bastante difícil de superar eso.

Tu código está roto. No se puede asignar a vA y necesita usar parámetros de plantilla.

 vector REORDER(const vector& vA, const vector& vOrder) { assert(vA.size() == vOrder.size()); vector vCopy(vA.size()); for(int i = 0; i < vOrder.size(); ++i) vCopy[i] = vA[ vOrder[i] ]; return vA; } 

Lo anterior es un poco más eficiente.

No está claro por el título y la pregunta si el vector debe ordenarse con los mismos pasos que toma ordenar vOrder o si vOrder ya contiene los índices del orden deseado. La primera interpretación ya tiene una respuesta satisfactoria (ver chmike y Potatoswatter), agrego algunas reflexiones sobre esta última. Si el costo de creación y / o copia del objeto T es relevante

 template  void reorder( std::vector & data, std::vector & order ) { std::size_t i,j,k; for(i = 0; i < order.size() - 1; ++i) { j = order[i]; if(j != i) { for(k = i + 1; order[k] != i; ++k); std::swap(order[i],order[k]); std::swap(data[i],data[j]); } } } 

Si el costo de creación de su objeto es pequeño y la memoria no es una preocupación (vea dribeas):

 template  void reorder( std::vector & data, std::vector const & order ) { std::vector tmp; // create an empty vector tmp.reserve( data.size() ); // ensure memory and avoid moves in the vector for ( std::size_t i = 0; i < order.size(); ++i ) { tmp.push_back( data[order[i]] ); } data.swap( tmp ); // swap vector contents } 

Tenga en cuenta que las dos piezas de código en dribeas responden hacen cosas diferentes.

Estaba tratando de usar la solución de @ Potatoswatter para ordenar vectores múltiples por un tercero y realmente me confundí por la salida de usar las funciones anteriores en un vector de índices de salida de sort_index de Armadillo. Para pasar de una salida vectorial de sort_index (el vector arma_inds continuación) a una que se puede usar con la solución de @ Potatoswatter ( new_inds continuación), puede hacer lo siguiente:

 vector new_inds(arma_inds.size()); for (int i = 0; i < new_inds.size(); i++) new_inds[arma_inds[i]] = i; 

Es un ejercicio intelectual interesante hacer el reordenamiento con O (1) espacio requerido pero en el 99.9% de los casos, la respuesta más simple funcionará según sus necesidades:

 void permute(vector& values, const vector& indices) { vector out; out.reserve(indices.size()); for(size_t index: indices) { assert(0 <= index && index < values.size()); out.push_back(values[index]); } values = std::move(out); } 

Más allá de los requisitos de memoria, la única forma en que puedo pensar en que esto sea más lento se debe a que la memoria está en una página de memoria caché diferente a la de values e indices .

Se me ocurrió esta solución que tiene la complejidad espacial de O(max_val - min_val + 1) , pero se puede integrar con std::sort y se beneficia de la complejidad de tiempo decente O(n log n) de std::sort .

 std::vector dense_vec = {1, 2, 3}; std::vector order = {1, 0, 2}; int32_t max_val = *std::max_element(dense_vec.begin(), dense_vec.end()); std::vector sparse_vec(max_val + 1); int32_t i = 0; for(int32_t j: dense_vec) { sparse_vec[j] = order[i]; i++; } std::sort(dense_vec.begin(), dense_vec.end(), [&sparse_vec](int32_t i1, int32_t i2) {return sparse_vec[i1] < sparse_vec[i2];}); 

Las siguientes suposiciones hechas al escribir este código:

  • Los valores vectoriales comienzan desde cero.
  • Vector no contiene valores repetidos.
  • Tenemos suficiente memoria para sacrificar para usar std::sort

Esto debería evitar copiar el vector:

 void REORDER(vector& vA, const vector& vOrder) { assert(vA.size() == vOrder.size()); for(int i = 0; i < vOrder.size(); ++i) if (i < vOrder[i]) swap(vA[i], vA[vOrder[i]]); }