5

vector<int> intVec私がとを持っていると仮定しvector<vector<double> > matrixます。C++intVecで対応する最初の次元を並べ替えて並べ替えたいと思います。matrixこの質問は以前にも何度か聞かれたことがあると思いますが、この場合はひねりがあります。Avector<double>はコピーにコストがかかるため、たとえば、との両方をコピーし、それintVecをmatrix並べvector<pair<int, vector<double> >替えてコピーし直すのは、通常よりもさらに非効率的です。

独自のカスタム並べ替えアルゴリズムを使用する以外に、の要素をコピーしてのコピーコンストラクターを呼び出さずに、ロックステップintVecでの最初の次元を並べ替えて並べ替えるにはどうすればよいですか？matrixmatrixvector

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

2つの間のスペースに基づいて、>C ++11より前のC++を使用していると思います。C ++ 11std::sortでは、コピーする代わりに、可能な限り要素を移動するようです。

カスタムコンパレータをに渡すことができますstd::sort。ただし、これを行っても、'のTheta（n log n）コピーを実行していることになりますpair<int, vector<double> >。

pair<int, vector<double> *>実際に試していないことに基づいて、適切な順列を取得する代わりに（または十分に大きい場合は、2番目をインデックスとして使用してpair<int, int>）並べ替えてから、のメンバー関数を使用して順列を適用して回避する必要があると思いますベクターの内容をコピーします。intintvectorswap

于 2012-12-27T18:46:10.240 に答える
1

1つのオプション：std::vector<std::pair<int,size_t>>最初の要素がintVecからのintであり、2番目の要素がその要素の元のインデックスであるaを作成します。次に、その新しいベクトルを並べ替えます。次に、行列とintVecを、ペアの2番目の要素で示される順序にシャッフルします（たとえば、シングルパスでスワップを実行します）。

于 2012-12-27T18:49:01.587 に答える
0

明白な答えは、2つのベクトルを1つとして再構築することですvector<pair<int, vector<double> >（データは明らかに緊密に結合されているため）。

それが本当にオプションではない場合は、インデックスの別のベクトルを作成し、vecと行列の代わりにそれを並べ替えます。

于 2012-12-27T19:15:30.990 に答える
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

一定時間で動作するため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 に答える
0

---最新のコンパイラ（たとえばgcc 4.4以降）を使用すると、実際には何もコピーされないと確信しています。現在、C ++標準ライブラリコンテナ内のオブジェクトは（ほとんど）常に移動されます。したがって、私見では、高価なコピーを心配する必要はありません。

次の例を見てください-Debianでgcc4.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 に答える