Re: Breakthrough

On Mon, 04 Jun 2012 22:42:28 +0200
jacob navia <jacob@spamsink.net> wrote:


This is with my inplace qsort with bidirectional
iterators:

bmaxa@maxa:~/jacob/ccl$ time ./cpplist1
sort time 1.480
Sum = 10738138201479754

real 0m2.105s
user 0m1.936s
sys 0m0.168s
bmaxa@maxa:~/jacob/ccl$ time ./testlist
sort time 3.130
Sum = 10738138201479754

real 0m4.265s
user 0m4.128s
sys 0m0.136s
bmaxa@maxa:~/jacob/ccl$ cat QSort.h
#include <algorithm>

namespace VLib{
using std::swap;

template <typename T,typename F>
void qsort(T begin, T end, unsigned size, F f)
{
  if(begin == end)return;

  T high = end;
  if(!size)
  {
   T tmp = begin;
   while(tmp!=end){ high=tmp++;++size; }
  }
  else
  {
   --high;
  }

  if(size == 1)return;

  T low = begin;
  ++low;

  unsigned counthigh = 0,countlow = 0;
  do
  {
    while(high != low && f(*begin,*high)){ --high;++counthigh; }
    while(low != high && f(*low,*begin)){ ++low;++countlow; }
    
    if(low != high && !f(*low,*begin) && !f(*begin,*low) && !f(*begin,*high) && !f(*high,*begin))
    {
     while(high != low && !f(*high,*low) && !f(*low,*high)){ --high;++counthigh; }
    }
    
    swap(*low,*high);
  }while(low != high);
  swap(*low,*begin);
  T i = low;
  
  while(++i != end && !f(*i,*low) && !f(*low,*i) )--counthigh;
  
   VLib::qsort(begin,low,countlow,f);
   VLib::qsort(i,end,counthigh,f);
}

template <typename T>
inline void qsort(T begin, T end, unsigned size = 0)
{
 VLib::qsort(begin,end,size,std::less<typename std::iterator_traits<T>::value_type>());
}

}
bmaxa@maxa:~/jacob/ccl$ cat cpplist1.cpp
#include <list>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include "QSort.h"

#define N 10000000

int main()
{
  std::list<int> L1;
  long long sum=0,newSum=0;
  for(int i = 0; i < N; ++i)
  {
    int d = rand();
    sum+=d;
    L1.push_back(d);
  }
  
  clock_t t = clock();
  VLib::qsort(L1.begin(),L1.end());
  clock_t et = clock();
  printf("sort time %.3f\n",float(et - t)/CLOCKS_PER_SEC);
  
  for(auto it : L1)
  {
    newSum+= it;
  }
  
  if (sum != newSum)
          printf("Failed\n");
  else printf("Sum = %lld\n",sum);
                                   
}