5

Assume I have a vector<int> intVec and a vector<vector<double> > matrix. I want to sort intVec and reorder the first dimension of matrix correspondingly in C++. I realize this question has been asked several times before, but this case has a twist. A vector<double> is expensive to copy, so e.g. copying both intVec and matrix to a vector<pair<int, vector<double> >, sorting that and copying them back is even more inefficient than usual.

Short of rolling my own custom sorting algorithm, how can I sort intVec and reorder the first dimension of matrix in lockstep without copying any element of matrix and invoking vector's copy constructor?

4

7 回答 7

4

Avector<double>的复制成本很高，因此例如将 intVec 和 matrix 复制到 a vector<pair<int, vector<double> >，对其进行排序并将它们复制回来甚至比平时效率低下。

获得所需优化的最简单方法是将源的元素交换vector<vector<double>>到临时的vector<pair<int, vector<double>>，对其进行排序，然后将它们交换回原始向量中的新位置。

仍然会有比严格必要的更多的开销（例如构造和销毁空向量）。但是，从未复制任何向量，并且代码与您已有的代码非常相似。因此，如果您正确地认为问题是复制成本，那么问题就解决了。

在 C++11 中，您可以双向移动而不是交换。我怀疑使用空向量移动和交换之间存在很大的性能差异，但我不确定是否存在。

于 2012-12-27T19:20:30.697 回答
1

根据你两个之间的空间>，我猜你使用的是 pre-C++11 C++。在 C++11 中，std::sort似乎尽可能移动元素而不是复制。

您可以将自定义比较器传递给std::sort. 然而，即使你这样做，你也在做pair<int, vector<double> >'s 的 Theta(n log n) 副本。

我猜，基于没有实际尝试，你应该排序 a pair<int, vector<double> *>（或者pair<int, int>如果int足够大），使用第二个int作为索引）而不是获得适当的排列，然后使用vector'sswap成员函数应用排列以避免复制矢量内容。

于 2012-12-27T18:46:10.240 回答
1

一个选项：创建一个std::vector<std::pair<int,size_t>>，其中第一个元素是 intVec 中的 int，第二个元素是该元素的原始索引。然后对该新向量进行排序。然后将您的矩阵和 intVec 打乱到由对的第二个元素指示的顺序（例如，一次通过，进行交换）。

于 2012-12-27T18:49:01.587 回答
0

我很确定——当你使用一些最新的编译器（比如 gcc 4.4 及更高版本）——没有真正被复制：现在 C++ 标准库容器中的对象（大部分）总是被移动。因此恕我直言，无需担心昂贵的副本。

看看下面的例子——它是在 Debian 下使用 gcc 4.4.6 编写的。如您所见，在“重新排序”阶段，没有调用复制构造函数，也没有调用“operator=(... & other)”。

#include <vector>
#include <iostream>
#include <iomanip>

class VeryExpensiveToCopy {
public:
   explicit VeryExpensiveToCopy(long i) : id(i) { ++cnt_normal_cstr; }

   // Just to be sure this is never used.
   VeryExpensiveToCopy & operator=(VeryExpensiveToCopy & other) = delete;
   VeryExpensiveToCopy(VeryExpensiveToCopy & other) = delete;

   VeryExpensiveToCopy(VeryExpensiveToCopy && other) : id(other.id) {
      ++cnt_move_cstr;
   }
   VeryExpensiveToCopy & operator=(VeryExpensiveToCopy && other) {
      id = other.id; ++cnt_op_as_move; return *this;
   }

   long get_id() const { return id; }

   static void print_stats(std::string const & lref) {
      std::cout << "[" << std::setw(20) << lref << "] Normal Cstr [" 
                << cnt_normal_cstr 
                << "] Move Cstr [" << cnt_move_cstr
                << "] operator=(&&) [" << cnt_op_as_move << "]" << std::endl;
   }

private:
   long id;

   static long cnt_normal_cstr;
   static long cnt_move_cstr;
   static long cnt_op_as_move;
};

// Counts the number of calls.
long VeryExpensiveToCopy::cnt_normal_cstr { 0 };
long VeryExpensiveToCopy::cnt_move_cstr { 0 };
long VeryExpensiveToCopy::cnt_op_as_move { 0 };

int main() {
   std::vector<VeryExpensiveToCopy> v;

   VeryExpensiveToCopy::print_stats("Start");
   for(auto i(0); i<100000; ++i) {
      v.emplace_back(i);
   }
   VeryExpensiveToCopy::print_stats("After initialization");
   for(auto i(0); i<100000-1; ++i) {
      v[i] = std::move(v[i+1]);
   }
   VeryExpensiveToCopy::print_stats("After moving");
   for(auto i(0); i<100000-1; ++i) {
      if(v[i].get_id() != i+1) { abort(); }
   }
   VeryExpensiveToCopy::print_stats("After check");

   return 0;
}

输出：

[               Start] Normal Cstr [0] Move Cstr [0] operator=(&&) [0]
[After initialization] Normal Cstr [100000] Move Cstr [131071] operator=(&&) [0]
[        After moving] Normal Cstr [100000] Move Cstr [131071] operator=(&&) [99999]
[         After check] Normal Cstr [100000] Move Cstr [131071] operator=(&&) [99999]
于 2012-12-27T20:40:50.170 回答
0

如果您不想复制vector<double>项目向量，则为项目创建一个指针或索引向量vector<double>。将其与主向量一起排序。

但是，您是否会获得性能提升尚不清楚，因此我建议您同时测量直接排序和智能排序，并进行比较。

例子：

#include    <algorithm>
#include    <vector>
#include    <iostream>
using namespace std;

struct Mat
{
    vector< vector< double > >  items;

    Mat( int const size )
        : items( size, vector< double >( size ) )
    {}
};

struct KeyAndData
{
    int                     key;
    vector< double > const* data;

    friend bool operator<( KeyAndData const& a, KeyAndData const& b )
    {
        return a.key < b.key;
    }
};

int main()
{
    int const       data[]  = {3, 1, 4, 1, 5};
    Mat             m( 5 );
    vector<int>     v( 5 );

    for( int i = 0;  i < 5;  ++i )
    {
        m.items[i][i] = v[i] = data[i];
    }

    vector< KeyAndData >        sorted( 5 );
    for( int i = 0;  i < 5;  ++i )
    {
        sorted[i].key = v[i];
        sorted[i].data = &m.items[i];
    }

    sort( sorted.begin(), sorted.end() );
    for( int i = 0;  i < 5;  ++i )
    {
        cout << sorted[i].key << ":  ";

        vector< double > const& r = *sorted[i].data;
        for( int x = 0;  x < 5;  ++x )
        {
            cout << r[x] << " ";
        }
        cout << endl;
    }
}
于 2012-12-27T18:41:15.400 回答
0

显而易见的答案是将您的两个向量重组为一个向量vector<pair<int, vector<double> >（因为数据显然是紧密耦合的区域）。

如果这真的不是一个选项，那么创建另一个索引向量并对其进行排序，而不是 vec 和矩阵。

于 2012-12-27T19:15:30.990 回答
0

由于std::vector::swap在恒定时间内运行，您可以使用一种排序算法，该算法通过一系列交换（如快速排序）进行排序intVec，同时在 上执行相同的交换matrix：

#include <iostream>
#include <vector>
#include <algorithm>

// Sorts intVec in [low, high) while also performing identical swaps on matrix.
void iqsort(std::vector<int> &intVec, std::vector<std::vector<double>> &matrix,
            int low, int high) {
  if (low >= high) return;
  int pivot = intVec[low];
  int nLow = low + 1;
  int nHigh = high - 1;
  while (nLow <= nHigh) {
    if (intVec[nLow] <= pivot) {
      ++nLow;
    } else {
      std::swap(intVec[nLow], intVec[nHigh]);
      std::swap(matrix[nLow], matrix[nHigh]);
      --nHigh;
    }   
  }
  std::swap(intVec[low], intVec[nHigh]);
  std::swap(matrix[low], matrix[nHigh]);

  iqsort(intVec, matrix, low, nHigh);
  iqsort(intVec, matrix, nLow, high);
}

int main() {
  std::vector<int> intVec = {10, 1, 5}; 
  std::vector<std::vector<double>> matrix = {{33.0}, {11.0}, {44.0}};  
  iqsort(intVec, matrix, 0, intVec.size());
  // intVec is {1, 5, 10} and matrix is {{11.0}, {44.0}, {33.0}}
}
于 2012-12-27T19:28:49.763 回答