30

我刚刚通过使用 C++11 可变参数模板在编译时对其进行评估来实现快速排序算法。但是，当数据集太大时，我会遇到性能问题。

#include <iostream>

using namespace std;

template<int... vs>
struct Seq
{}; 
template<int v1, int...vs>
struct Seq<v1, vs...>{
};


template<typename newT, typename srcT>
struct PushFront{
};
template<int vadded, int...vs>
struct PushFront<Seq<vadded>, Seq<vs...>>{
  typedef Seq<vadded, vs...> ResultType;
};

template<typename T>
struct PopFront{
};
template<int v1, int...vs>
struct PopFront<Seq<v1, vs...>>{
  typedef Seq<vs...> RemaindType;
  typedef Seq<v1>    ResultType;
};

template<typename T1, typename T2>
struct CatSeq{};
template<int...v, int...us>
struct CatSeq<Seq<v...>, Seq<us...>>{
  typedef Seq< v..., us... >  ResultType;
};


template<bool c, typename NewT, typename TrueClsT, typename FalseClsT>
struct Classify{
};
template<typename NewT, typename TrueClsT, typename FalseClsT>
struct Classify<true, NewT, TrueClsT, FalseClsT>{
  typedef typename PushFront<NewT, TrueClsT>::ResultType NewTrueClsT;
  typedef FalseClsT  NewFalseClsT;
};
template<typename NewT, typename TrueClsT, typename FalseClsT>
struct Classify<false, NewT, TrueClsT, FalseClsT>{
  typedef TrueClsT  NewTrueClsT;
  typedef typename PushFront<NewT, FalseClsT>::ResultType NewFalseClsT;
};

template<typename T1, typename T2>
struct Compare{};
template<int v1, int v2>
struct Compare<Seq<v1>, Seq<v2>>{
  static const bool result=(v1>=v2); 
};


template<typename AnchorT, typename SeqT, typename GESet, typename LSet>
struct PartitionImpl{};
template<typename GESet, typename LSet, int anchorv, int v1>
struct PartitionImpl<Seq<anchorv>, Seq<v1>, GESet, LSet>{
  static const bool isge=Compare<typename PopFront<Seq<v1>>::ResultType, Seq<anchorv>>::result;
  typedef typename Classify<isge, Seq<v1>, GESet, LSet>::NewTrueClsT  RstGESet;
  typedef typename Classify<isge, Seq<v1>, GESet, LSet>::NewFalseClsT  RstLSet;  
};
template<typename GESet, typename LSet, int anchorv, int v1, int...vs>
struct PartitionImpl<Seq<anchorv>, Seq<v1, vs...>, GESet, LSet>{
  static const bool isge=Compare<typename PopFront<Seq<v1, vs...>>::ResultType, Seq<anchorv>>::result;
  typedef typename Classify<isge, Seq<v1>, GESet, LSet>::NewTrueClsT  TmpRstGESet;
  typedef typename Classify<isge, Seq<v1>, GESet, LSet>::NewFalseClsT  TmpRstLSet;

  typedef typename PartitionImpl<Seq<anchorv>, Seq<vs...>, TmpRstGESet, TmpRstLSet>::RstGESet RstGESet;
  typedef typename PartitionImpl<Seq<anchorv>, Seq<vs...>, TmpRstGESet, TmpRstLSet>::RstLSet  RstLSet;
};


template<typename T>
struct Partition{
};
template<int v1, int v2, int...vs>
struct Partition<Seq<v1, v2, vs...>>{
  typedef Seq<v1> AnchorType;
  typedef Seq<> GESet;
  typedef Seq<> LSet;
  typedef typename PartitionImpl<AnchorType, Seq<v1, v2, vs...>, GESet, LSet>::RstGESet  RstGESet;
  typedef typename PartitionImpl<AnchorType, Seq<v1, v2, vs...>, GESet, LSet>::RstLSet   RstLSet;
};

//why introduce this? refer to Sort
template<typename SrcT, typename GESet, typename LSet, template<typename > class SortOp>
struct SortSub{  
  typedef typename SortOp<GESet>::ResultType  TmpGESet2;
  typedef typename SortOp<LSet>::ResultType   TmpLSet2;
};
template<typename SrcT, typename LSet, template<typename> class SortOp>
struct SortSub<SrcT, SrcT, LSet, SortOp>{
  typedef SrcT  TmpGESet2;
  typedef typename SortOp<LSet>::ResultType   TmpLSet2;
};
template<typename SrcT, typename GESet, template<typename> class SortOp>
struct SortSub<SrcT, GESet, SrcT, SortOp>{
  typedef typename SortOp<GESet>::ResultType  TmpGESet2;
  typedef SrcT   TmpLSet2;
};

template<typename T>
struct Sort;
template<>
struct Sort<Seq<>>{
  typedef Seq<> ResultType;
};
template<int v>
struct Sort< Seq<v> >{
  typedef Seq<v> ResultType;
};
template<int v1, int...vs>
struct Sort< Seq<v1, vs...> >{
  typedef Seq<v1, vs...> SrcType;
  typedef typename Partition< Seq<v1, vs...> >::RstGESet TmpGESet;
  typedef typename Partition< Seq<v1, vs...> >::RstLSet TmpLSet;

  //to by pass the case SrcType <==> TmpGESet or  SrcType <==> TmpLSet
  typedef typename SortSub<SrcType, TmpGESet, TmpLSet, Sort>::TmpGESet2  TmpGESet2;
  typedef typename SortSub<SrcType, TmpGESet, TmpLSet, Sort>::TmpLSet2   TmpLSet2;

  typedef typename CatSeq<TmpGESet2, TmpLSet2>::ResultType ResultType;
};


void dumpSeqTypeImpl(Seq<> ){
}
template<int v1>
void dumpSeqTypeImpl(Seq<v1> ){
  cout<<v1<<" ";
}
template<int v1, int...vs>
void dumpSeqTypeImpl(Seq<v1, vs...> ){
  cout<<v1<<" ";
  dumpSeqTypeImpl( Seq<vs...>() );
}
template<int...vs>
void dumpSeqType(Seq<vs...> ){
  cout<<"Seq type < ";
  dumpSeqTypeImpl( Seq<vs...>() );
  cout<<" >"<<endl;
}

    //test data
#include "qsort_input.txt"

int main(){
  //Seq<>  s0;// aggregate ‘Seq<> s0’ has incomplete type and cannot be defined
  Seq<1> s1;
  Seq<1, 2> s2;

  typedef Seq<5, 5, 5> TestType_SAME;
  TestType_SAME same;
  dumpSeqType( same );
  typename Partition< TestType_SAME >::RstGESet _ts1;
  typename Partition< TestType_SAME >::RstLSet _ts2;
  dumpSeqType( _ts1 );
  dumpSeqType( _ts2 );

#if 1
  typedef Seq<4, 7, 3, 9, 1, 2, 5, 5, 19, 5> TestType;
  TestType s3;
  dumpSeqType( s3 );
  typename Partition< TestType >::RstGESet ts1;
  typename Partition< TestType >::RstLSet ts2;
  dumpSeqType( ts1 );
  dumpSeqType( ts2 );

  typename Sort<TestType>::ResultType so1;
  dumpSeqType( so1 );
#endif 

#if 1
  typedef Seq<TEST_DATA_100> TAdvanceType;
  typename Sort<TAdvanceType>::ResultType soadvance;
  dumpSeqType(soadvance);
#endif

  return 0;
}

当数据集为TEST_DATA_100时，编译需要1.7s。
当数据集为 TEST_DATA_1000 时，编译器似乎停止了......

我正在使用 gcc 4.6.0。

4

2 回答 2

10

你是否也看过它的内存消耗？请注意，快速排序本身比线性更差，在更坏的情况下运行时非常糟糕。这与模板编译和实例化的某些步骤（有时是指数的）的线性运行时行为相乘。您可能应该为各种数据集绘制编译时间图，以观察代码的真正复杂性类别。通常使用如此大的数据集进行模板元编程是不可行的。

编辑： 出于好奇，我尝试了代码，发现直到 ~500 它大致遵循公式 pow(N*log(N),1.47)*0.0004+0.6 但随后开始变得慢得多，需要 155 秒700 项。同样在那个时候，它开始消耗大量内存（600 个需要 3GiB），这让我得出结论，对于 1000 个元素，它需要比大多数人更多的内存，并且需要几个小时才能编译。

进一步注意，当不是每个元素都是唯一的时，代码不起作用。

于 2011-08-25T09:50:14.343 回答
5

您正在使用递归元函数来构建您的快速排序。当您尝试将 1000 个递归实例推入编译器时，您到底期望发生什么？

仅仅因为一个函数理论上可以接受任意数量的参数并不意味着编译器实际上可以处理任意数量的参数。编译器有限制。

此外：编译时排序有什么意义？您可以离线执行此操作并将数据复制到 .cpp 文件中。或者只std::sort在程序启动时运行一次。

于 2011-08-25T09:50:06.917 回答