Заменить вектор, используя вектор индексов
Я хотел бы изменить порядок элементов в векторе, используя другой вектор, чтобы указать порядок:
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' }
Ниже приведена неэффективная реализация, требующая копирования вектора:
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] ];
}
Есть ли более эффективный способ, например, который использует swap()?
Ответы
Ответ 1
Я улучшил алгоритм chmike. Эта функция согласуется с его для всех 11! перестановки (0..10), переданные как вектор переупорядочения. Также он не изменяет вектор переупорядочения.
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] );
}
}
Здесь версия стиля STL, в которую я приложил немного больше усилий. Это примерно на 47% быстрее (то есть почти в два раза быстрее (0,10)!), Потому что он делает все свопы как можно раньше, а затем возвращается. Вектор переупорядочения состоит из нескольких орбит, и каждая орбита переупорядочивается по достижении ее первого члена. Это быстрее, если последние несколько элементов не содержат орбиты.
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;
}
}
}
И, наконец, просто чтобы ответить на вопрос раз и навсегда, вариант, который уничтожает вектор переупорядочения. (Он заполняет -1.) Это примерно на 16% быстрее, чем предыдущая версия. Этот использует уродливый тип, но справляйтесь с ним. Это охватывает 11! ~ = 40 мил перестановки 11 символов за 4,25 секунды, не считая накладных расходов, на моем 2,2 ГГц ноутбуке.
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;
}
}
Ответ 2
Вот правильный код
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] );
}
}
}
обратите внимание, что вы можете сохранить один тест, потому что, если n-1 элементов на месте, последний n-й элемент, безусловно, на месте.
При выходе vA и vOrder правильно упорядочены.
Этот алгоритм выполняет не более n-1 обмена, поскольку каждый своп перемещает элемент в конечное положение. И нам нужно сделать не более 2N тестов на vOrder.
Ответ 3
Если это нормально изменить массив ORDER, то реализация, которая сортирует вектор ORDER и при каждой операции сортировки, также меняет значения, которые, как мне кажется, могут использовать векторные элементы вектора значений.
Ответ 4
Мне кажется, что vOrder содержит набор индексов в нужном порядке (например, вывод сортировки по индексу). Пример кода здесь следует за "циклами" в vOrder, где после поднабора (может быть все из vOrder) индексов будет циклически проходить через подмножество, заканчиваясь обратно первым индексом подмножества.
Вики статья о "циклах"
https://en.wikipedia.org/wiki/Cyclic_permutation
В следующем примере каждый своп помещает в свое место хотя бы один элемент. Этот пример кода эффективно переупорядочивает vA в соответствии с vOrder, при этом "разупорядочивая" или "не переставляя" vOrder обратно в исходное состояние (0 :: n-1). Если vA содержал значения от 0 до n-1 по порядку, то после переупорядочения vA заканчивал бы там, где начинался vOrder.
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]] );
}
}
}
Это также может быть реализовано более эффективно, используя ходы вместо свопов. Временный объект необходим для удержания элемента во время ходов. Пример кода C, переупорядочивает A [] в соответствии с индексами в я [], также сортирует я []:
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;
}
}
}
Ответ 5
Никогда преждевременно не оптимизируйте. Meassure, а затем определить, где вам нужно оптимизировать и что. Вы можете завершить сложный код, который трудно поддерживать и подвержен ошибкам во многих местах, где производительность не является проблемой.
С учетом сказанного не начинайте пессимизировать. Без изменения кода вы можете удалить половину своих копий:
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
}
Этот код создает и пуст (достаточно большой) вектор, в котором одна копия выполняется в порядке. В конце упорядоченные и исходные векторы меняются местами. Это уменьшит количество копий, но все равно потребует дополнительной памяти.
Если вы хотите выполнить ходы на месте, простой алгоритм может быть:
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] );
}
}
Этот код необходимо проверить и отладить. Говоря простыми словами, алгоритм на каждом шаге позиционирует элемент в i-й позиции. Сначала мы определяем, где исходный элемент для этой позиции теперь помещен в вектор данных. Если исходное положение уже было затронуто алгоритмом (оно находится до i-й позиции), тогда исходный элемент был заменен на порядок [оригинальное] положение. Опять же, этот элемент уже может быть перемещен...
Этот алгоритм примерно равен O (N ^ 2) по числу целых операций и, следовательно, теоретически хуже во время выполнения по сравнению с исходным алгоритмом O (N). Но он может компенсировать, если операции замены N ^ 2 (наихудший случай) стоят меньше, чем N операций копирования или если вы действительно ограничены положением памяти.
Ответ 6
Вы можете сделать это рекурсивно, я думаю - что-то вроде этого (непроверено, но это дает идею):
// 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);
}
}
Конечно, у вас есть накладные расходы vecVisited. Мысли о таком подходе, кто-нибудь?
Ответ 7
Ваш код не работает. Вы не можете назначить vA, и вам нужно использовать параметры шаблона.
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;
}
Вышеуказанное несколько более эффективно.
Ответ 8
Для итерации по вектору выполняется операция O (n). Его сорта трудно превзойти.
Ответ 9
Непонятно название и вопрос, следует ли упорядочить вектор с теми же шагами, которые требуется для заказа vOrder, или если vOrder уже содержит индексы нужного порядка.
Первая интерпретация уже удовлетворительного ответа (см. Chmike и Potatoswatter), я добавляю некоторые мысли о последнем.
Если ценность создания и/или копирования объекта T релевантна
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]);
}
}
}
Если стоимость создания вашего объекта мала, и память не вызывает беспокойства (см. 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
}
Обратите внимание, что две части кода в dribeas отвечают на разные вещи.
Ответ 10
Я пытался использовать решение @Potatoswatter для сортировки нескольких векторов третьей и очень запутался в результате использования вышеуказанных функций в векторе индексов, выводимых из Armadillo sort_index. Чтобы переключиться с векторного вывода из sort_index (ниже arma_inds vector) на тот, который может использоваться с решением @Potatoswatter (new_inds ниже), вы можете сделать следующее:
vector<int> new_inds(arma_inds.size());
for (int i = 0; i < new_inds.size(); i++) new_inds[arma_inds[i]] = i;
Ответ 11
Это интересное интеллектуальное упражнение для изменения порядка с O (1) пространством, но в 99,9% случаев более простой ответ будет отвечать вашим потребностям:
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);
}
Помимо требований к памяти, единственный способ, которым я могу думать о том, что это медленнее, будет связано с тем, что память out находится на другой странице кеша, чем в values и indices.
Ответ 12
Я придумал это решение, которое имеет пространственную сложность O(max_val - min_val + 1), но оно может быть интегрировано с std::sort и имеет преимущество от std::sort O(n log n) приличной сложности времени.
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];});
Следующие предположения сделаны при написании этого кода:
- Векторные значения начинаются с нуля.
- Вектор не содержит повторяющихся значений.
- У нас достаточно памяти, чтобы пожертвовать, чтобы использовать
std::sort
Ответ 13
Этого следует избегать копирования вектора:
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]]);
}
