Replace vector using index vector

Question

I would like to reorder the elements in the vector using a different vector to indicate the order:

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

The following is an inefficient implementation that requires copying a vector:

 void reorder_naive(vector<char>& vA, const vector<size_t>& 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] ]; } 

Is there a more efficient way, for example, that uses swap ()?

Answer 1

I improved the chmike algorithm. This feature is consistent with it for all 11! permutations (0..10) passed as a reordering vector. Also, it does not change the reordering vector.

 template< class T > void reorder(vector<T> &v, vector<size_t> 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] ); } } 

Here's a version of the STL style that I put a little more effort into. This is about 47% faster (i.e., almost twice as fast (0.10)!), Because he makes all swaps as early as possible, and then returns. The reordering vector consists of several orbits, and each orbit is reordered upon reaching its first term. This is faster if the last few elements do not contain an orbit.

 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; } } } 

And finally, just to answer the question once and for all, an option that destroys the reordering vector. (It fills -1.) This is about 16% faster than the previous version. This one uses the ugly type, but handle it. It spans 11! ~ = 40 mil permutations of 11 characters in 4.25 seconds, not counting the overhead, on my 2.2 GHz laptop.

 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; } } 

Answer 2

Here is the correct code

 void REORDER(vector<char>& vA, vector<size_t>& 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] ); } } } 

note that you can save one test, because if n-1 elements are in place, the last n-th element is definitely in place.

On exit, vA and vOrder are properly ordered.

This algorithm performs no more than n-1 exchanges, since each swap moves an element to its final position. And we need to do no more than 2N tests on vOrder.

Answer 3

If it’s normal to change the ORDER array, then the implementation that sorts the ORDER vector and with each sort operation also changes the values ​​that, it seems to me, can use the vector elements of the value vector.

Answer 4

It seems to me that vOrder contains a set of indexes in the right order (for example, sorting by index). The code example here follows the “loops” in vOrder, where after a subset (maybe all of vOrder) the indexes will cycle through the subset, ending back with the first subset index.

Wiki article on "cycles"

https://en.wikipedia.org/wiki/Cyclic_permutation

In the following example, each swap places at least one element in its place. This code example effectively reorders vA according to vOrder, while “disordering” or “not rearranging” vOrder back to its original state (0 :: n-1). If vA contained values ​​from 0 to n-1 in order, then after reordering vA would end where vOrder started.

 template <class T> void reorder(vector<T>& vA, vector<size_t>& 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 proper place while( vOrder[i] != vOrder[vOrder[i]] ) { swap( vA[vOrder[i]], vA[vOrder[vOrder[i]]] ); swap( vOrder[i], vOrder[vOrder[i]] ); } } } 

---

It can also be implemented more efficiently using moves instead of swaps. A temporary object is required to hold the element during moves. Sample C code, reorders A [] according to the indices in i [], also sorts 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; } } } 

Answer 5

Never prematurely optimize. Meassure, and then determine where you need to optimize and what. You can complete complex code that is difficult to maintain and error prone in many places where performance is not a problem.

With that said, don't start pessimizing. Without changing the code, you can delete half of your copies:

  template <typename T> void reorder( std::vector<T> & data, std::vector<std::size_t> const & order ) { std::vector<T> 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 } 

This code creates and is empty (large enough) a vector in which one copy is executed in order. At the end, the ordered and original vectors are swapped. This will reduce the number of copies, but still require additional memory.

If you want to execute moves in place, a simple algorithm could be:

 template <typename T> void reorder( std::vector<T> & data, std::vector<std::size_t> 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] ); } } 

This code needs to be checked and debugged. In simple words, the algorithm at each step positions the element in the i-th position. First, we determine where the source element for this position is now placed in the data vector. If the initial position was already affected by the algorithm (it is located to the i-th position), then the original element was replaced by the order of the [original] position. Again, this item can already be moved ...

This algorithm is approximately equal to O (N ^ 2) in the number of whole operations and, therefore, is theoretically worse at runtime compared to the original O (N) algorithm. But it can compensate if N ^ 2 replacement operations (the worst case) cost less than N copy operations or if you are really limited by the memory position.

Answer 6

You can do it recursively, I think - something like this (untested, but it gives an idea):

 // Recursive function template<typename T> void REORDER(int oldPosition, vector<T>& vA, const vector<int>& vecNewOrder, vector<bool>& 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 at the next // position. Instead, we first move what 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<typename T> void REORDER(vector<T>& vA, const vector<int>& newOrder) { // Initialise vecVisited with false values vector<bool> vecVisited(vA.size(), false); for (int x = 0; x < vA.size(); x++) { REORDER(x, vA, newOrder, vecVisited); } } 

Of course, you have vecVisited overhead. Thoughts on such an approach, anyone?

Answer 7

Your code does not work. You cannot assign vA , and you need to use the template options.

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

The above is somewhat more efficient.

Answer 8

To iterate over the vector, the operation O (n) is performed. Its varieties are hard to beat.

Answer 9

The name and question are unclear whether the vector should be ordered with the same steps that are required to order vOrder, or if vOrder already contains indices of the desired order. The first interpretation is already a satisfactory answer (see Chmike and Potatoswatter), I add some thoughts about the latter. If the value of creating and / or copying an object T is relevant

 template <typename T> void reorder( std::vector<T> & data, std::vector<std::size_t> & 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]); } } } 

If the cost of creating your object is small and memory is not a concern (see dribeas):

 template <typename T> void reorder( std::vector<T> & data, std::vector<std::size_t> const & order ) { std::vector<T> 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 } 

Note that the two pieces of code in dribeas respond to different things.

Answer 10

I tried to use the @Potatoswatter solution to sort several vectors of the third and got very confused as a result of using the above functions in the index vector output from Armadillo sort_index . To switch from vector output from sort_index (below arma_inds vector) to one that can be used with @Potatoswatter ( new_inds below), you can do the following:

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

Answer 11

This is an interesting intellectual exercise for reordering with O (1) space, but in 99.9% of cases a simpler answer will meet your needs:

 void permute(vector<T>& values, const vector<size_t>& indices) { vector<T> 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); } 

Besides the memory requirements, the only way I can think that it is slower will be because the out memory is on a different cache page than in values and indices .

Answer 12

I came up with this solution that has O(max_val - min_val + 1) spatial complexity, but it can be integrated with std::sort and takes advantage of std::sort O(n log n) decent time complexity.

 std::vector<int32_t> dense_vec = {1, 2, 3}; std::vector<int32_t> order = {1, 0, 2}; int32_t max_val = *std::max_element(dense_vec.begin(), dense_vec.end()); std::vector<int32_t> 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];}); 

The following assumptions were made when writing this code:

• Vector values ​​start from zero.
• The vector does not contain duplicate values.
• We have enough memory to donate to use std::sort

Answer 13

This should avoid copying the vector:

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