Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, Serginio1, Вы писали:


S>> Правда для реальных наборов вероятность достаточно мала, да и алгоритмы с выбором едианы из трех значении, с досортировкой малых диапозонов другими алогритмами сводят вероятность неудобоваримых наборов на нет.

_DA>Досортировка малых диапазонов применяется для оптимизации по скорости. А для того, чтобы не существовали, например, median-of-3 killer sequences, при достижении некоторой глубины рекурсии переключаются на другой алгоритм с вычислительной сложностью в худшем случае O(nlogn), heapsort обычно. В результате получается алгоритм с оценкой O(nlogn) для худшего случая. Такой алгоритм описан тут http://en.wikipedia.org/wiki/Introsort

Здесь разговор не об этом. Лучше взять сортировку слиянием она быстрее хип сорта и медленне квиксорта на 5-20%, а с памятью проблем обычно нет, да и не имеет неудобоваримых наборов.
Просто получить неудобоваримый набор для квиксорта достаточно сложно и весь смысл в уменьшении вероятности этого набора.
Как правило тактго рода оптимизации приведенные тобой значительно тормозят алгоритм (правда все относительно)

Здравствуйте, Serginio1, Вы писали:

S>Здравствуйте, _DAle_, Вы писали:

_DA>>Здравствуйте, Serginio1, Вы писали:


S>>> Правда для реальных наборов вероятность достаточно мала, да и алгоритмы с выбором едианы из трех значении, с досортировкой малых диапозонов другими алогритмами сводят вероятность неудобоваримых наборов на нет.

_DA>>Досортировка малых диапазонов применяется для оптимизации по скорости. А для того, чтобы не существовали, например, median-of-3 killer sequences, при достижении некоторой глубины рекурсии переключаются на другой алгоритм с вычислительной сложностью в худшем случае O(nlogn), heapsort обычно. В результате получается алгоритм с оценкой O(nlogn) для худшего случая. Такой алгоритм описан тут http://en.wikipedia.org/wiki/Introsort

S> Здесь разговор не об этом. Лучше взять сортировку слиянием она быстрее хип сорта и медленне квиксорта на 5-20%, а с памятью проблем обычно нет, да и не имеет неудобоваримых наборов.
Introsort тоже не имеет неудобоваримых наборов.

S> Просто получить неудобоваримый набор для квиксорта достаточно сложно и весь смысл в уменьшении вероятности этого набора.
Сложно, но возможно, и зная, какой варант quicksort используется в программе, можно эту программу грубо говоря "завалить".

S> Как правило тактго рода оптимизации приведенные тобой значительно тормозят алгоритм (правда все относительно)
Расскажи это создателям многочисленных библиотек, тем же авторам SGI C++ STL Introsort так же, как и Mergesort имеет сложностную оценку O(nlogn) в худшем случае и в отличие от слияния не требует дополнительной памяти, да и по скорости не проигрывает. Единственное, что Introsort — это не stable sort. Вот в случаях, когда нужна stable sort используется Mergesort.

Здравствуйте, _DAle_, Вы писали:

По сути мы говорим об одном и том же.
Просто нужно еще учитывать железо, а там не все однозначно. Универсальных методов не бывает и лучше делать выбор по месту, благо выбор большой.

Здравствуйте, McSeem2, Вы писали:

К сожалению у меня сейчас на машине нет студии 2003.

Мои попытки поиграть с настройками хотя и дали кое чего, но не много. Все же /O2.

А какой СТЛ ты используешь? Может дело в этом?

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>Влад, выложи, пожалуйста, буквальный исходный текст своего варианта теста, плюс точные установки компилятора, которые были использованы.

Установки — Release в студии 2005 бэта 2. Код:

// SortTestCpp.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>


unsigned swap_quick_sort = 0;
unsigned cmp_quick_sort = 0;

//------------------------------------------------------------------------
enum
{
    quick_sort_threshold = 9
};


//-----------------------------------------------------------swap_elements
template<class T> inline void swap_elements(T& a, T& b)
{
    swap_quick_sort++;
    T temp = a;
    a = b;
    b = temp;
}

template<class T> inline bool qsort_less(T a, T b) 
{ 
    cmp_quick_sort++;
    return a < b; 
}

//--------------------------------------------------------------quick_sort
template<class Array>
void quick_sort(Array& arr)
{
    if(arr.size() < 2) return;

    typename Array::value_type* e1;
    typename Array::value_type* e2;

    int  stack[80];
    int* top = stack; 
    int  limit = arr.size();
    int  base = 0;

    for(;;)
    {
        int len = limit - base;

        int i;
        int j;
        int pivot;

        if(len > quick_sort_threshold)
        {
            // we use base + len/2 as the pivot
            pivot = base + len / 2;
            swap_elements(arr[base], arr[pivot]);

            i = base + 1;
            j = limit - 1;

            // now ensure that *i <= *base <= *j 
            e1 = &(arr[j]); 
            e2 = &(arr[i]);
            if(qsort_less(*e1, *e2)) swap_elements(*e1, *e2);

            e1 = &(arr[base]); 
            e2 = &(arr[i]);
            if(qsort_less(*e1, *e2)) swap_elements(*e1, *e2);

            e1 = &(arr[j]); 
            e2 = &(arr[base]);
            if(qsort_less(*e1, *e2)) swap_elements(*e1, *e2);

            for(;;)
            {
                do i++; while( qsort_less(arr[i], arr[base]) );
                do j--; while( qsort_less(arr[base], arr[j]) );

                if( i > j )
                {
                    break;
                }

                swap_elements(arr[i], arr[j]);
            }

            swap_elements(arr[base], arr[j]);

            // now, push the largest sub-array
            if(j - base > limit - i)
            {
                top[0] = base;
                top[1] = j;
                base   = i;
            }
            else
            {
                top[0] = i;
                top[1] = limit;
                limit  = j;
            }
            top += 2;
        }
        else
        {
            // the sub-array is small, perform insertion sort
            j = base;
            i = j + 1;

            for(; i < limit; j = i, i++)
            {
                for(; qsort_less(*(e1 = &(arr[j + 1])), *(e2 = &(arr[j]))); j--)
                {
                    swap_elements(*e1, *e2);
                    if(j == base)
                    {
                        break;
                    }
                }
            }
            if(top > stack)
            {
                top  -= 2;
                base  = top[0];
                limit = top[1];
            }
            else
            {
                break;
            }
        }
    }
}




unsigned SwapQuickSort = 0;
unsigned CmpQuickSort = 0;


// Swap меняет местами элементы массива. Соответствующий тип данных 
// должен поддерживать операцию <=>.
template <class T>
void Swap(T & el1, T & el2)
{
  T tmp = el1;
  el1 = el2;
  el2 = tmp;
  ++SwapQuickSort;
}


template<class T> inline bool less(T a, T b) 
{ 
    CmpQuickSort++;
    return a < b; 
}

template<class T> inline bool lessEq(T a, T b) 
{ 
    CmpQuickSort++;
    return a <= b; 
}

template<class T> inline bool greater(T a, T b) 
{ 
    CmpQuickSort++;
    return a > b; 
}


template <class T> 
void QuickSort(T & item, int left, int right)
{
    int i = left;
    int j = right;  
    typename T::value_type center = item[(left + right) / 2];

    while(i <= j)
    {
        while (less(item[i], center))
            i++;
        while (less(center, item[j]))
            j--;

        if (i <= j)
            Swap(item[i++], item[j--]);
    } 

    if(left < j)
        QuickSort(item, left, j);
    if(right > i)
        QuickSort(item, i, right);
}

// QuickSort принимает в качестве параметров массив
// и предельные значения его индексов
template <class T>
void QuickSort2(T& A, int low, int high)
{
  // локальные переменные, содержащие индекс середины - mid,
  // центральный элемент и индексы сканирования
  typename T::value_type pivot;
  int scanUp, scanDown;
  int mid;

  // если диапазон индексов не включает в себя
  // как минимум два элемента, завершить работу
  if(high - low <= 0)
    return;

  else if(high - low == 1)
  {
    // если в подсписке два элемента, сравнить их между собой
    // и поменять местами при необходимости
    if(less(A[high], A[low]))
    {
      Swap(A[low], A[high]);
    }
    return;
  }

  // Рассчитать индекс середины и поместить значение соответствующего 
  // элемента массива в переменную pivot.
  mid = (low + high)/2;
  pivot = A[mid];

  // Поменять местами центральный и начальный элементы списка.
  Swap(A[mid], A[low]);
  // Инициализировать индексы scanUp и scanDown.
  scanUp = low + 1;
  scanDown = high;

  // Искать элементы, расположенные не в тех подсписках.
  // Остановиться при scanDown < scanUp.
  do
  {
    // Продвигаться вверх по первому подсписку. Остановиться,
    // когда scanUp укажет на второй подсписок или если
    // указываемый этим индексом элемент > центрального.
    while(scanUp <= scanDown && lessEq(A[scanUp], pivot))
    {
      if(A[scanUp] > pivot) break;
      scanUp++;
    }


    // Продвигаться вниз по второму подсписку. Остановиться,
    // когда scanDown указжет на элемент >= центральному.
    while(greater(A[scanDown], pivot))
    {
      scanDown--;
    }

    // Если индексы все еще в своих подсписках, то они указывают
    // на два элемента, находящихся не в тех подсписках.
    if(scanUp < scanDown)
    {
      // Поменять их местами
      Swap(A[scanUp], A[scanDown]);
    }
  }
  while(scanUp < scanDown);

  // Скопировать элемент на который указывает точка разбиения
  // в первый элемент первого подсписка, ...
  A[low] = A[scanDown];
  // а центральный элемент в точку разбиения
  A[scanDown] = pivot;
  ++SwapQuickSort;  // This operation plus "pivot = A[mid]" above
                    // is equivalent to yet another swap! 

  // если первый подсписок (low...scanDown-1) имеет 2 или более
  // элемента, выполнить для него рекурсивный вызов QuickSort
  if(low < scanDown-1)
    QuickSort2(A, low, scanDown-1);

  // если второй подсписок (scanDown+1...high) имеет 2 или более
  // элемента, выполнить для него рекурсивный вызов QuickSort
  if(scanDown+1 < high)
    QuickSort2(A, scanDown+1, high);
}



template<class T> void check_sort(const T& v)
{
    size_t i;
    for(i = 1; i < v.size(); i++)
    {
        if(v[i-1] > v[i])
        {
            printf("Error: v[%u] > v[%u]\n", i-1, i);
            break;
        }
    }
}


int numElements = 10000000;
typedef double value_type;
value_type generate_random()
{
    return (rand() << 16) | rand();
}


/*
int numElements = 1000000;
typedef double value_type;
value_type generate_random()
{
    return (rand() << 16) | rand();
}
*/

/*
int numElements = 1000000;
struct value_type
{
    double v1,v2,v3;
    value_type(){}
    value_type(int v)
    {
        v1 = v >> 20;
        v2 = (v >> 10) & 1023;
        v3 = v & 1023;
    }
};
inline bool operator < (const value_type& a, const value_type& b)
{
    if(a.v1 != b.v1) return a.v1 < b.v1;
    if(a.v2 != b.v2) return a.v2 < b.v2;
    return a.v3 < b.v3;
}
inline bool operator > (const value_type& a, const value_type& b)
{
    if(a.v1 != b.v1) return a.v1 > b.v1;
    if(a.v2 != b.v2) return a.v2 > b.v2;
    return a.v3 > b.v3;
}
inline bool operator <= (const value_type& a, const value_type& b)
{
    return !(a > b);
}
value_type generate_random()
{
    value_type t;
    t.v1 = rand();
    t.v2 = rand();
    t.v3 = rand();
    return t;
}
*/




int main()
{
    std::vector<value_type> v;
    int i;
    clock_t t0;

    printf("\nRandom Values:\n");

    srand(1234);
    v.clear();
    for(i = 0; i < numElements; i++)
    {
        v.push_back(generate_random());
    }
    swap_quick_sort = 0;
    cmp_quick_sort = 0;
    t0 = clock();
    quick_sort(v);
    printf("agg::quick_sort: Cmp=%u, Swap=%u, Time=%u\n", cmp_quick_sort, swap_quick_sort, clock() - t0);
    check_sort(v);

    srand(1234);
    v.clear();
    for(i = 0; i < numElements; i++)
    {
        v.push_back(generate_random());
    }
    SwapQuickSort = 0;
    CmpQuickSort = 0;
    t0 = clock();
    QuickSort(v, 0, numElements-1);
    printf("RSDN QuickSort:  Cmp=%u, Swap=%u, Time=%u\n", CmpQuickSort, SwapQuickSort, clock() - t0);
    check_sort(v);



    printf("\nSorted Array:\n");

    v.clear();
    for(i = 0; i < numElements; i++)
    {
        v.push_back(value_type(i));
    }
    check_sort(v);
    swap_quick_sort = 0;
    cmp_quick_sort = 0;
    t0 = clock();
    quick_sort(v);
    printf("agg::quick_sort: Cmp=%u, Swap=%u, Time=%u\n", cmp_quick_sort, swap_quick_sort, clock() - t0);
    check_sort(v);

    v.clear();
    for(i = 0; i < numElements; i++)
    {
        v.push_back(value_type(i));
    }
    SwapQuickSort = 0;
    CmpQuickSort = 0;
    t0 = clock();
    QuickSort(v, 0, numElements-1);
    printf("RSDN QuickSort:  Cmp=%u, Swap=%u, Time=%u\n", CmpQuickSort, SwapQuickSort, clock() - t0);
    check_sort(v);


    printf("\nSorted Backward:\n");

    v.clear();
    for(i = 0; i < numElements; i++)
    {
        v.push_back(value_type(numElements-i));
    }
    swap_quick_sort = 0;
    cmp_quick_sort = 0;
    t0 = clock();
    quick_sort(v);
    printf("agg::quick_sort: Cmp=%u, Swap=%u, Time=%u\n", cmp_quick_sort, swap_quick_sort, clock() - t0);
    check_sort(v);

    v.clear();
    for(i = 0; i < numElements; i++)
    {
        v.push_back(value_type(numElements-i));
    }
    SwapQuickSort = 0;
    CmpQuickSort = 0;
    t0 = clock();
    QuickSort(v, 0, numElements-1);
    printf("RSDN QuickSort:  Cmp=%u, Swap=%u, Time=%u\n", CmpQuickSort, SwapQuickSort, clock() - t0);
    check_sort(v);


    return 0;
}

Я попытался похимичить с настройками вручную и даже кое-что плучилось (но все равно скорость ниже семерки), но сейчас нет времени. Потом попробую поколупать.

Здравствуйте, VladD2, Вы писали:

VD>А какой СТЛ ты используешь? Может дело в этом?

Самый что ни на есть рабоче-крестьянский, тот что идет вместе с компиляторами.
Ты хочешь сказать, что у вектора дорогой operator[]? Ну так можно его его вообще выкинуть. Сегодня попробую. Но 2005 студии у меня нету.

Кстати, можно тебя попросить запустить еще одну фишку на VS 2005? Займет 2-3 минуты. Надеюсь, оно умеет открывать-конвертировать старые dsp/dsw проекты?

Здравствуйте, VladD2, Вы писали:

VD>А какой СТЛ ты используешь? Может дело в этом?

Вот, заменил vector на самодельный контейнер. Результат на VC71 не пострадал.

Random Values:
agg::quick_sort: Cmp=262083609, Swap=62971807, Time=2654
RSDN QuickSort:  Cmp=316880453, Swap=56544300, Time=3015

Sorted Array:
agg::quick_sort: Cmp=208951444, Swap=2097150, Time=1001
RSDN QuickSort:  Cmp=224834201, Swap=5805696, Time=1222

Sorted Backward:
agg::quick_sort: Cmp=217118959, Swap=14999998, Time=1192
RSDN QuickSort:  Cmp=224834224, Swap=10805696, Time=1302

Кстати, извиняюсь — результаты теста в моем предыдущем сообщении даны именно для RSDN QuickSort из статьи, а не для короткого классического варианта, приведенного Владом. Я просто не доглядел, но сути дела это не меняет.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

   //---------------------------------------------------------pod_heap_array
   template<class T> class pod_heap_array
   {
   public:
      typedef T value_type;
      typedef pod_heap_array<T> self_type;

      ~pod_heap_array() { delete [] m_array; }
      pod_heap_array() : m_array(0), m_size(0) {}
      pod_heap_array(unsigned size) : m_array(new T[size]), m_size(size) {}
      pod_heap_array(const self_type& v) : 
         m_array(new T[v.m_size]), m_size(v.m_size) 
      {
         memcpy(m_array, v.m_array, sizeof(T) * m_size);
      }
      void resize(unsigned size)
      {
         delete [] m_array;
         m_array = new T[m_size = size];
      }
      const self_type& operator = (const self_type& v)
      {
         resize(v.size());
         memcpy(m_array, v.m_array, sizeof(T) * m_size);
         return *this;
      }

      unsigned size() const { return m_size; }
      const T& operator [] (unsigned i) const { return m_array[i]; }
            T& operator [] (unsigned i)       { return m_array[i]; }

      const T* data() const { return m_array; }
            T* data()       { return m_array; }
   private:
      T*       m_array;
      unsigned m_size;
   };





unsigned swap_quick_sort = 0;
unsigned cmp_quick_sort = 0;

//------------------------------------------------------------------------
enum
{
    quick_sort_threshold = 9
};


//-----------------------------------------------------------swap_elements
template<class T> inline void swap_elements(T& a, T& b)
{
    swap_quick_sort++;
    T temp = a;
    a = b;
    b = temp;
}

template<class T> inline bool qsort_less(T a, T b) 
{ 
    cmp_quick_sort++;
    return a < b; 
}

//--------------------------------------------------------------quick_sort
template<class Array>
void quick_sort(Array& arr)
{
    if(arr.size() < 2) return;

    typename Array::value_type* e1;
    typename Array::value_type* e2;

    int  stack[80];
    int* top = stack; 
    int  limit = arr.size();
    int  base = 0;

    for(;;)
    {
        int len = limit - base;

        int i;
        int j;
        int pivot;

        if(len > quick_sort_threshold)
        {
            // we use base + len/2 as the pivot
            pivot = base + len / 2;
            swap_elements(arr[base], arr[pivot]);

            i = base + 1;
            j = limit - 1;

            // now ensure that *i <= *base <= *j 
            e1 = &(arr[j]); 
            e2 = &(arr[i]);
            if(qsort_less(*e1, *e2)) swap_elements(*e1, *e2);

            e1 = &(arr[base]); 
            e2 = &(arr[i]);
            if(qsort_less(*e1, *e2)) swap_elements(*e1, *e2);

            e1 = &(arr[j]); 
            e2 = &(arr[base]);
            if(qsort_less(*e1, *e2)) swap_elements(*e1, *e2);

            for(;;)
            {
                do i++; while( qsort_less(arr[i], arr[base]) );
                do j--; while( qsort_less(arr[base], arr[j]) );

                if( i > j )
                {
                    break;
                }

                swap_elements(arr[i], arr[j]);
            }

            swap_elements(arr[base], arr[j]);

            // now, push the largest sub-array
            if(j - base > limit - i)
            {
                top[0] = base;
                top[1] = j;
                base   = i;
            }
            else
            {
                top[0] = i;
                top[1] = limit;
                limit  = j;
            }
            top += 2;
        }
        else
        {
            // the sub-array is small, perform insertion sort
            j = base;
            i = j + 1;

            for(; i < limit; j = i, i++)
            {
                for(; qsort_less(*(e1 = &(arr[j + 1])), *(e2 = &(arr[j]))); j--)
                {
                    swap_elements(*e1, *e2);
                    if(j == base)
                    {
                        break;
                    }
                }
            }
            if(top > stack)
            {
                top  -= 2;
                base  = top[0];
                limit = top[1];
            }
            else
            {
                break;
            }
        }
    }
}




unsigned SwapQuickSort = 0;
unsigned CmpQuickSort = 0;


// Swap меняет местами элементы массива. Соответствующий тип данных 
// должен поддерживать операцию <=>.
template <class T>
void Swap(T & el1, T & el2)
{
  T tmp = el1;
  el1 = el2;
  el2 = tmp;
  ++SwapQuickSort;
}


template<class T> inline bool less(T a, T b) 
{ 
    CmpQuickSort++;
    return a < b; 
}

template<class T> inline bool lessEq(T a, T b) 
{ 
    CmpQuickSort++;
    return a <= b; 
}

template<class T> inline bool greater(T a, T b) 
{ 
    CmpQuickSort++;
    return a > b; 
}


template <class T> 
void QuickSort(T & item, int left, int right)
{
    int i = left;
    int j = right;  
    typename T::value_type center = item[(left + right) / 2];

    while(i <= j)
    {
        while (less(item[i], center))
            i++;
        while (less(center, item[j]))
            j--;

        if (i <= j)
            Swap(item[i++], item[j--]);
    } 

    if(left < j)
        QuickSort(item, left, j);
    if(right > i)
        QuickSort(item, i, right);
}

// QuickSort принимает в качестве параметров массив
// и предельные значения его индексов
template <class T>
void QuickSort2(T& A, int low, int high)
{
  // локальные переменные, содержащие индекс середины - mid,
  // центральный элемент и индексы сканирования
  typename T::value_type pivot;
  int scanUp, scanDown;
  int mid;

  // если диапазон индексов не включает в себя
  // как минимум два элемента, завершить работу
  if(high - low <= 0)
    return;

  else if(high - low == 1)
  {
    // если в подсписке два элемента, сравнить их между собой
    // и поменять местами при необходимости
    if(less(A[high], A[low]))
    {
      Swap(A[low], A[high]);
    }
    return;
  }

  // Рассчитать индекс середины и поместить значение соответствующего 
  // элемента массива в переменную pivot.
  mid = (low + high)/2;
  pivot = A[mid];

  // Поменять местами центральный и начальный элементы списка.
  Swap(A[mid], A[low]);
  // Инициализировать индексы scanUp и scanDown.
  scanUp = low + 1;
  scanDown = high;

  // Искать элементы, расположенные не в тех подсписках.
  // Остановиться при scanDown < scanUp.
  do
  {
    // Продвигаться вверх по первому подсписку. Остановиться,
    // когда scanUp укажет на второй подсписок или если
    // указываемый этим индексом элемент > центрального.
    while(scanUp <= scanDown && lessEq(A[scanUp], pivot))
    {
      if(A[scanUp] > pivot) break;
      scanUp++;
    }


    // Продвигаться вниз по второму подсписку. Остановиться,
    // когда scanDown указжет на элемент >= центральному.
    while(greater(A[scanDown], pivot))
    {
      scanDown--;
    }

    // Если индексы все еще в своих подсписках, то они указывают
    // на два элемента, находящихся не в тех подсписках.
    if(scanUp < scanDown)
    {
      // Поменять их местами
      Swap(A[scanUp], A[scanDown]);
    }
  }
  while(scanUp < scanDown);

  // Скопировать элемент на который указывает точка разбиения
  // в первый элемент первого подсписка, ...
  A[low] = A[scanDown];
  // а центральный элемент в точку разбиения
  A[scanDown] = pivot;
  ++SwapQuickSort;  // This operation plus "pivot = A[mid]" above
                    // is equivalent to yet another swap! 

  // если первый подсписок (low...scanDown-1) имеет 2 или более
  // элемента, выполнить для него рекурсивный вызов QuickSort
  if(low < scanDown-1)
    QuickSort2(A, low, scanDown-1);

  // если второй подсписок (scanDown+1...high) имеет 2 или более
  // элемента, выполнить для него рекурсивный вызов QuickSort
  if(scanDown+1 < high)
    QuickSort2(A, scanDown+1, high);
}



template<class T> void check_sort(const T& v)
{
    size_t i;
    for(i = 1; i < v.size(); i++)
    {
        if(v[i-1] > v[i])
        {
            printf("Error: v[%u] > v[%u]\n", i-1, i);
            break;
        }
    }
}


int numElements = 10000000;
typedef double value_type;
value_type generate_random()
{
    return (rand() << 16) | rand();
}


/*
int numElements = 1000000;
typedef double value_type;
value_type generate_random()
{
    return (rand() << 16) | rand();
}
*/

/*
int numElements = 1000000;
struct value_type
{
    double v1,v2,v3;
    value_type(){}
    value_type(int v)
    {
        v1 = v >> 20;
        v2 = (v >> 10) & 1023;
        v3 = v & 1023;
    }
};
inline bool operator < (const value_type& a, const value_type& b)
{
    if(a.v1 != b.v1) return a.v1 < b.v1;
    if(a.v2 != b.v2) return a.v2 < b.v2;
    return a.v3 < b.v3;
}
inline bool operator > (const value_type& a, const value_type& b)
{
    if(a.v1 != b.v1) return a.v1 > b.v1;
    if(a.v2 != b.v2) return a.v2 > b.v2;
    return a.v3 > b.v3;
}
inline bool operator <= (const value_type& a, const value_type& b)
{
    return !(a > b);
}
value_type generate_random()
{
    value_type t;
    t.v1 = rand();
    t.v2 = rand();
    t.v3 = rand();
    return t;
}
*/




int main()
{
    pod_heap_array<value_type> v(numElements);
    int i;
    clock_t t0;

    printf("\nRandom Values:\n");

    srand(1234);
    for(i = 0; i < numElements; i++)
    {
        v[i] = generate_random();
    }
    swap_quick_sort = 0;
    cmp_quick_sort = 0;
    t0 = clock();
    quick_sort(v);
    printf("agg::quick_sort: Cmp=%u, Swap=%u, Time=%u\n", cmp_quick_sort, swap_quick_sort, clock() - t0);
    check_sort(v);

    srand(1234);
    for(i = 0; i < numElements; i++)
    {
        v[i] = generate_random();
    }
    SwapQuickSort = 0;
    CmpQuickSort = 0;
    t0 = clock();
    QuickSort(v, 0, numElements-1);
    printf("RSDN QuickSort:  Cmp=%u, Swap=%u, Time=%u\n", CmpQuickSort, SwapQuickSort, clock() - t0);
    check_sort(v);



    printf("\nSorted Array:\n");

    for(i = 0; i < numElements; i++)
    {
        v[i] = value_type(i);
    }
    check_sort(v);
    swap_quick_sort = 0;
    cmp_quick_sort = 0;
    t0 = clock();
    quick_sort(v);
    printf("agg::quick_sort: Cmp=%u, Swap=%u, Time=%u\n", cmp_quick_sort, swap_quick_sort, clock() - t0);
    check_sort(v);

    for(i = 0; i < numElements; i++)
    {
        v[i] = value_type(i);
    }
    SwapQuickSort = 0;
    CmpQuickSort = 0;
    t0 = clock();
    QuickSort(v, 0, numElements-1);
    printf("RSDN QuickSort:  Cmp=%u, Swap=%u, Time=%u\n", CmpQuickSort, SwapQuickSort, clock() - t0);
    check_sort(v);


    printf("\nSorted Backward:\n");

    for(i = 0; i < numElements; i++)
    {
        v[i] = value_type(numElements-i);
    }
    swap_quick_sort = 0;
    cmp_quick_sort = 0;
    t0 = clock();
    quick_sort(v);
    printf("agg::quick_sort: Cmp=%u, Swap=%u, Time=%u\n", cmp_quick_sort, swap_quick_sort, clock() - t0);
    check_sort(v);

    for(i = 0; i < numElements; i++)
    {
        v[i] = value_type(numElements-i);
    }
    SwapQuickSort = 0;
    CmpQuickSort = 0;
    t0 = clock();
    QuickSort(v, 0, numElements-1);
    printf("RSDN QuickSort:  Cmp=%u, Swap=%u, Time=%u\n", CmpQuickSort, SwapQuickSort, clock() - t0);
    check_sort(v);


    return 0;
}

Здравствуйте, McSeem2, Вы писали:

MS>Ты хочешь сказать, что у вектора дорогой operator[]?

Незнаю. Но результат явно странный. Возможно очередной глюк бэты.

Но на счет "рвет как грелку" мягко скажем это преувеличение. На интах вообще проигрыш. При увеличении размера структуры тоже. А у меня, например, и ключи целочисленные, и структуры по толще. Хотя я вообще каунтирг-сорт использую так как диапазон относительно мелкий.

MS> Ну так можно его его вообще выкинуть. Сегодня попробую. Но 2005 студии у меня нету.

Надо было вообще не вставлять никаких лишних наворотов.

MS>Кстати, можно тебя попросить запустить еще одну фишку на VS 2005?

Можно. Хотя если у тебя Интернет толстый, то можешь сам скачать Экспресс и пробовать в доволь.

MS> Займет 2-3 минуты. Надеюсь, оно умеет открывать-конвертировать старые dsp/dsw проекты?

Естественно умеет.

Здравствуйте, McSeem2, Вы писали:

Вот твои жкзешники. Это кстати еще с исходной сортировкой или с моей? В любом случае последний вариант у меня всегда рвет оптимизированный.

Интересно что будет если вернуть целочисленный ключ (не такая у ж и редкость) и увеличить размер данных. Думаю ситуация изменится на побратную. Что говорит о том. что оптимизированная версия хороша не всегда. Да и откровенно говоря это ловля блох. Вот VC 8 что-то вообще в даун ушел на обоих тестах. А много ил программистов пойдет докапываться до истины?

c:\Temp\001>SortTestCppVC6.exe

Random Values:
agg::quick_sort: Cmp=262083609, Swap=62971807, Time=2187
RSDN QuickSort:  Cmp=316880453, Swap=56544300, Time=2734

Sorted Array:
agg::quick_sort: Cmp=208951444, Swap=2097150, Time=906
RSDN QuickSort:  Cmp=224834201, Swap=5805696, Time=938

Sorted Backward:
agg::quick_sort: Cmp=217118959, Swap=14999998, Time=1016
RSDN QuickSort:  Cmp=224834224, Swap=10805696, Time=985

c:\Temp\001>SortTestCppVC71.exe

Random Values:
agg::quick_sort: Cmp=262083609, Swap=62971807, Time=2188
RSDN QuickSort:  Cmp=316880453, Swap=56544300, Time=2718

Sorted Array:
agg::quick_sort: Cmp=208951444, Swap=2097150, Time=891
RSDN QuickSort:  Cmp=224834201, Swap=5805696, Time=953

Sorted Backward:
agg::quick_sort: Cmp=217118959, Swap=14999998, Time=1016
RSDN QuickSort:  Cmp=224834224, Swap=10805696, Time=969

c:\Temp\001>SortTestCppVlad.exe

Random Values:
agg::quick_sort: Cmp=262083609, Swap=62971807, Time=3391
RSDN QuickSort:  Cmp=316880453, Swap=56544300, Time=3313

Sorted Array:
agg::quick_sort: Cmp=208951444, Swap=2097150, Time=1500
RSDN QuickSort:  Cmp=224834201, Swap=5805696, Time=1328

Sorted Backward:
agg::quick_sort: Cmp=217118959, Swap=14999998, Time=1610
RSDN QuickSort:  Cmp=224834224, Swap=10805696, Time=1375

Здравствуйте, McSeem2, Вы писали:

MS>Как выяснилось — рвет как грелку. Правда при компиляции шестеркой или 7.1.

Не сказал бы, что это можно назвать "рвет".

И, кстати, ты так и не ответил в чем ты меня собственно разоблочал? Можно об этом более конкретно?

Здравствуйте, VladD2, Вы писали:

VD>Вот твои жкзешники. Это кстати еще с исходной сортировкой или с моей?

Экжешники уже с твоей.

VD>В любом случае последний вариант у меня всегда рвет оптимизированный.

У меня тоже

VD>Интересно что будет если вернуть целочисленный ключ (не такая у ж и редкость) и увеличить размер данных. Думаю ситуация изменится на побратную. Что говорит о том. что оптимизированная версия хороша не всегда. Да и откровенно говоря это ловля блох. Вот VC 8 что-то вообще в даун ушел на обоих тестах. А много ил программистов пойдет докапываться до истины?

Не знаю, много ли. Есть принципиально разные направления в программировании. Твой вариант QuickSort (так же как и исходный QuickSort2 из статьи) никуда не годятся и место им — на помойке. Но для тебя, например, это может быть несущественно, поскольку ну упала программа и упала — бывает. Но есть области, где падения в принципе недопустимы. Если алгоритм может упасть даже с вероятностью 10 в минус 100-й, то это уже не алгоритм а фуфло. Повторю еще раз — для каких-то майнстримовых задач это может быть и несущественно.

Итак, обещанное разоблачение. Любой вариант чистого QuickSort в наихудшем случае требует O(N^2) времени и O(N)
памяти. Как ни выбирай pivot, все равно такая последовательность может найтись. Совершеннто не имеет значения, какова вероятность такого события. Важно то, что она отлична от нуля. Если находится хоть один случай, на котором алгоритм падает, то он не является работоспособным. Понимаешь, это как математическое доказательство. Andrew Wiles доказал таки великую теорему Ферма. Но если бы нашелся хоть один случай, при котором равенство Ферма выполняется, все — вся теорема была бы опровергнута. Понимаешь, в чем фишка? "Достаточно одной таблэтки" из всегомножества чисел. То же самое с сортировкой (спасибо Serginio1):

Random Values:
agg::quick_sort: Cmp=21976178, Swap=5527606, MaxStack=13, Time=200
RSDN QuickSort:  Cmp=28517873, Swap=4856698, MaxStack=55 Time=240

Horrible Sequence:
agg::quick_sort: Cmp=75073187, Swap=5304536, MaxStack=10, Time=331
RSDN QuickSort:  Cmp=2403990969, Swap=3823488, MaxStack=24325 Time=9263

Sorted Array:
agg::quick_sort: Cmp=17868945, Swap=262142, MaxStack=17, Time=80
RSDN QuickSort:  Cmp=19000019, Swap=524287, MaxStack=19 Time=91

Sorted Backward:
agg::quick_sort: Cmp=18475730, Swap=1499998, MaxStack=17, Time=80
RSDN QuickSort:  Cmp=19000036, Swap=1024286, MaxStack=19 Time=90

Это на 1M элементов. Два с лишним миллиарда сравнений на 1 миллион — это сильно. И глубина стэка в 24K — это тоже сильно. На 5 миллионах исполняем рок-балладу "скирда над рекой" (stack over flow) — (C) Синклер, если не ошибаюсь.

Такова цена твоей "красоты кода".
Но Влад, конечно же скажет, что все это — фигня и не имеет значения по жизни. Ведь гораздо важнее, чтобы код был красивым, не правда ли?

Я не уверен, можно ли завалить таким образом сортировку с отсечкой (K&R вариант). Может кто-нибудь попробовать найти killer sequence или доказать, что таковой не существует? Это для меня важно, поскольку именно этот вариант я использую. Если кто-то поможет доказать или опровергнуть — тему можно будет считать закрытой, а моя благодарность будет безграничной в разумных пределах

Вот:
http://antigrain.com/stuff/qsort/KillerSortTestCpp1M.exe
http://antigrain.com/stuff/qsort/KillerSortTestCpp5M.exe
http://antigrain.com/stuff/qsort/KillerSortTestCpp.cpp

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

   //---------------------------------------------------------pod_heap_array
   template<class T> class pod_heap_array
   {
   public:
      typedef T value_type;
      typedef pod_heap_array<T> self_type;

      ~pod_heap_array() { delete [] m_array; }
      pod_heap_array() : m_array(0), m_size(0) {}
      pod_heap_array(unsigned size) : m_array(new T[size]), m_size(size) {}
      pod_heap_array(const self_type& v) : 
         m_array(new T[v.m_size]), m_size(v.m_size) 
      {
         memcpy(m_array, v.m_array, sizeof(T) * m_size);
      }
      void resize(unsigned size)
      {
         delete [] m_array;
         m_array = new T[m_size = size];
      }
      const self_type& operator = (const self_type& v)
      {
         resize(v.size());
         memcpy(m_array, v.m_array, sizeof(T) * m_size);
         return *this;
      }

      unsigned size() const { return m_size; }
      const T& operator [] (unsigned i) const { return m_array[i]; }
            T& operator [] (unsigned i)       { return m_array[i]; }

      const T* data() const { return m_array; }
            T* data()       { return m_array; }
   private:
      T*       m_array;
      unsigned m_size;
   };





unsigned swap_quick_sort = 0;
unsigned cmp_quick_sort = 0;
int      max_stack_sort = 0;
int      stack_sort = 0;


//------------------------------------------------------------------------
enum
{
    quick_sort_threshold = 9
};


//-----------------------------------------------------------swap_elements
template<class T> inline void swap_elements(T& a, T& b)
{
    swap_quick_sort++;
    T temp = a;
    a = b;
    b = temp;
}

template<class T> inline bool qsort_less(T a, T b) 
{ 
    cmp_quick_sort++;
    return a < b; 
}



//--------------------------------------------------------------quick_sort
template<class Array>
void quick_sort(Array& arr)
{
    if(arr.size() < 2) return;

    typename Array::value_type* e1;
    typename Array::value_type* e2;

    int  stack[80];
    int* top = stack; 
    int  limit = arr.size();
    int  base = 0;

    for(;;)
    {
        int len = limit - base;

        int i;
        int j;
        int pivot;

        if(len > quick_sort_threshold)
        {
            // we use base + len/2 as the pivot
            pivot = base + len / 2;
            swap_elements(arr[base], arr[pivot]);

            i = base + 1;
            j = limit - 1;

            // now ensure that *i <= *base <= *j 
            e1 = &(arr[j]); 
            e2 = &(arr[i]);
            if(qsort_less(*e1, *e2)) swap_elements(*e1, *e2);

            e1 = &(arr[base]); 
            e2 = &(arr[i]);
            if(qsort_less(*e1, *e2)) swap_elements(*e1, *e2);

            e1 = &(arr[j]); 
            e2 = &(arr[base]);
            if(qsort_less(*e1, *e2)) swap_elements(*e1, *e2);

            for(;;)
            {
                do i++; while( qsort_less(arr[i], arr[base]) );
                do j--; while( qsort_less(arr[base], arr[j]) );

                if( i > j )
                {
                    break;
                }

                swap_elements(arr[i], arr[j]);
            }

            swap_elements(arr[base], arr[j]);

            // now, push the largest sub-array
            if(j - base > limit - i)
            {
                top[0] = base;
                top[1] = j;
                base   = i;
            }
            else
            {
                top[0] = i;
                top[1] = limit;
                limit  = j;
            }
            top += 2;
            ++stack_sort;
            if(stack_sort > max_stack_sort) max_stack_sort = stack_sort;
        }
        else
        {
            // the sub-array is small, perform insertion sort
            j = base;
            i = j + 1;

            for(; i < limit; j = i, i++)
            {
                for(; qsort_less(*(e1 = &(arr[j + 1])), *(e2 = &(arr[j]))); j--)
                {
                    swap_elements(*e1, *e2);
                    if(j == base)
                    {
                        break;
                    }
                }
            }
            if(top > stack)
            {
                --stack_sort;
                top  -= 2;
                base  = top[0];
                limit = top[1];
            }
            else
            {
                break;
            }
        }
    }
}



unsigned SwapQuickSort = 0;
unsigned CmpQuickSort = 0;
int      StackSort = 0;
int      MaxStackSort = 0;


template <class T>
void Swap(T & el1, T & el2)
{
  T tmp = el1;
  el1 = el2;
  el2 = tmp;
  ++SwapQuickSort;
}


template<class T> inline bool less(T a, T b) 
{ 
    CmpQuickSort++;
    return a < b; 
}

template<class T> inline bool lessEq(T a, T b) 
{ 
    CmpQuickSort++;
    return a <= b; 
}

template<class T> inline bool greater(T a, T b) 
{ 
    CmpQuickSort++;
    return a > b; 
}


template <class T> 
void QuickSort(T & item, int left, int right)
{
    ++StackSort;
    if(StackSort > MaxStackSort) MaxStackSort = StackSort;

    int i = left;
    int j = right;  
    typename T::value_type center = item[(left + right) / 2];

    while(i <= j)
    {
        while (less(item[i], center))
            i++;
        while (less(center, item[j]))
            j--;

        if (i <= j)
            Swap(item[i++], item[j--]);
    } 

    if(left < j)
        QuickSort(item, left, j);
    if(right > i)
        QuickSort(item, i, right);

    --StackSort;
}



// QuickSort принимает в качестве параметров массив
// и предельные значения его индексов
template <class T>
void QuickSort2(T& A, int low, int high)
{
  ++StackSort;
  if(StackSort > MaxStackSort) MaxStackSort = StackSort;

  // локальные переменные, содержащие индекс середины - mid,
  // центральный элемент и индексы сканирования
  typename T::value_type pivot;
  int scanUp, scanDown;
  int mid;

  // если диапазон индексов не включает в себя
  // как минимум два элемента, завершить работу
  if(high - low <= 0)
  {
    --StackSort;
    return;
  }

  else if(high - low == 1)
  {
    // если в подсписке два элемента, сравнить их между собой
    // и поменять местами при необходимости
    if(less(A[high], A[low]))
    {
      Swap(A[low], A[high]);
    }
    --StackSort;
    return;
  }

  // Рассчитать индекс середины и поместить значение соответствующего 
  // элемента массива в переменную pivot.
  mid = (low + high)/2;
  pivot = A[mid];

  // Поменять местами центральный и начальный элементы списка.
  Swap(A[mid], A[low]);
  // Инициализировать индексы scanUp и scanDown.
  scanUp = low + 1;
  scanDown = high;

  // Искать элементы, расположенные не в тех подсписках.
  // Остановиться при scanDown < scanUp.
  do
  {
    // Продвигаться вверх по первому подсписку. Остановиться,
    // когда scanUp укажет на второй подсписок или если
    // указываемый этим индексом элемент > центрального.
    while(scanUp <= scanDown && lessEq(A[scanUp], pivot))
    {
      if(A[scanUp] > pivot) break;
      scanUp++;
    }


    // Продвигаться вниз по второму подсписку. Остановиться,
    // когда scanDown указжет на элемент >= центральному.
    while(greater(A[scanDown], pivot))
    {
      scanDown--;
    }

    // Если индексы все еще в своих подсписках, то они указывают
    // на два элемента, находящихся не в тех подсписках.
    if(scanUp < scanDown)
    {
      // Поменять их местами
      Swap(A[scanUp], A[scanDown]);
    }
  }
  while(scanUp < scanDown);

  // Скопировать элемент на который указывает точка разбиения
  // в первый элемент первого подсписка, ...
  A[low] = A[scanDown];
  // а центральный элемент в точку разбиения
  A[scanDown] = pivot;
  ++SwapQuickSort;  // This operation plus "pivot = A[mid]" above
                    // is equivalent to yet another swap! 

  // если первый подсписок (low...scanDown-1) имеет 2 или более
  // элемента, выполнить для него рекурсивный вызов QuickSort
  if(low < scanDown-1)
    QuickSort2(A, low, scanDown-1);

  // если второй подсписок (scanDown+1...high) имеет 2 или более
  // элемента, выполнить для него рекурсивный вызов QuickSort
  if(scanDown+1 < high)
    QuickSort2(A, scanDown+1, high);

    --StackSort;
}




template<class T> void check_sort(const T& v)
{
    size_t i;
    for(i = 1; i < v.size(); i++)
    {
        if(v[i-1] > v[i])
        {
            printf("Error: v[%u] > v[%u]\n", i-1, i);
            break;
        }
    }
}


template<class Array> void Horrify(Array& arr)
{
    int j = arr.size() - 1;
    int i = j / 2;
    int k = i;
    int l = 1;
    while(i >= 0)
    {
        arr[i] = j;
        arr[arr.size() - l] = j-1;
        ++l;
        --i; 
        j -= 2;
    }
}



int numElements = 1000000;
typedef int value_type;
value_type generate_random()
{
    return (rand() << 16) | rand();
}

/*
int numElements = 10000000;
typedef double value_type;
value_type generate_random()
{
    return (rand() << 16) | rand();
}
*/

/*
int numElements = 1000000;
struct value_type
{
    double v1,v2,v3;
    value_type(){}
    value_type(int v)
    {
        v1 = v >> 20;
        v2 = (v >> 10) & 1023;
        v3 = v & 1023;
    }
};
inline bool operator < (const value_type& a, const value_type& b)
{
    if(a.v1 != b.v1) return a.v1 < b.v1;
    if(a.v2 != b.v2) return a.v2 < b.v2;
    return a.v3 < b.v3;
}
inline bool operator > (const value_type& a, const value_type& b)
{
    if(a.v1 != b.v1) return a.v1 > b.v1;
    if(a.v2 != b.v2) return a.v2 > b.v2;
    return a.v3 > b.v3;
}
inline bool operator <= (const value_type& a, const value_type& b)
{
    return !(a > b);
}
value_type generate_random()
{
    value_type t;
    t.v1 = rand();
    t.v2 = rand();
    t.v3 = rand();
    return t;
}
*/


int main()
{
    pod_heap_array<value_type> v(numElements);
    int i;
    clock_t t0;

    printf("\nRandom Values:\n");
    srand(1234);
    for(i = 0; i < numElements; i++)
    {
        v[i] = generate_random();
    }
    swap_quick_sort = 0;
    cmp_quick_sort = 0;
    stack_sort = 0;
    max_stack_sort = 0;
    t0 = clock();
    quick_sort(v);
    printf("agg::quick_sort: Cmp=%u, Swap=%u, MaxStack=%u, Time=%u\n", 
           cmp_quick_sort, swap_quick_sort, max_stack_sort, clock() - t0);
    check_sort(v);

    srand(1234);
    for(i = 0; i < numElements; i++)
    {
        v[i] = generate_random();
    }
    SwapQuickSort = 0;
    CmpQuickSort = 0;
    StackSort = 0;
    MaxStackSort = 0;
    t0 = clock();
    QuickSort(v, 0, numElements-1);
    printf("RSDN QuickSort:  Cmp=%u, Swap=%u, MaxStack=%d Time=%u\n", 
           CmpQuickSort, SwapQuickSort, MaxStackSort, clock() - t0);
    check_sort(v);



    printf("\nHorrible Sequence:\n");
    Horrify(v);
    swap_quick_sort = 0;
    cmp_quick_sort = 0;
    stack_sort = 0;
    max_stack_sort = 0;
    t0 = clock();
    quick_sort(v);
    printf("agg::quick_sort: Cmp=%u, Swap=%u, MaxStack=%d, Time=%u\n", 
           cmp_quick_sort, swap_quick_sort, max_stack_sort, clock() - t0);
    check_sort(v);

    Horrify(v);
    SwapQuickSort = 0;
    CmpQuickSort = 0;
    StackSort = 0;
    MaxStackSort = 0;
    t0 = clock();
    QuickSort(v, 0, numElements-1);
    printf("RSDN QuickSort:  Cmp=%u, Swap=%u, MaxStack=%d Time=%u\n", 
           CmpQuickSort, SwapQuickSort, MaxStackSort, clock() - t0);
    check_sort(v);



    printf("\nSorted Array:\n");

    for(i = 0; i < numElements; i++)
    {
        v[i] = value_type(i);
    }
    check_sort(v);
    swap_quick_sort = 0;
    cmp_quick_sort = 0;
    stack_sort = 0;
    max_stack_sort = 0;
    t0 = clock();
    quick_sort(v);
    printf("agg::quick_sort: Cmp=%u, Swap=%u, MaxStack=%d, Time=%u\n", 
           cmp_quick_sort, swap_quick_sort, max_stack_sort, clock() - t0);
    check_sort(v);

    for(i = 0; i < numElements; i++)
    {
        v[i] = value_type(i);
    }
    SwapQuickSort = 0;
    CmpQuickSort = 0;
    StackSort = 0;
    MaxStackSort = 0;
    t0 = clock();
    QuickSort(v, 0, numElements-1);
    printf("RSDN QuickSort:  Cmp=%u, Swap=%u, MaxStack=%d Time=%u\n", 
           CmpQuickSort, SwapQuickSort, MaxStackSort, clock() - t0);
    check_sort(v);


    printf("\nSorted Backward:\n");

    for(i = 0; i < numElements; i++)
    {
        v[i] = value_type(numElements-i);
    }
    swap_quick_sort = 0;
    cmp_quick_sort = 0;
    stack_sort = 0;
    max_stack_sort = 0;
    t0 = clock();
    quick_sort(v);
    printf("agg::quick_sort: Cmp=%u, Swap=%u, MaxStack=%d, Time=%u\n", 
           cmp_quick_sort, swap_quick_sort, max_stack_sort, clock() - t0);
    check_sort(v);

    for(i = 0; i < numElements; i++)
    {
        v[i] = value_type(numElements-i);
    }
    SwapQuickSort = 0;
    CmpQuickSort = 0;
    StackSort = 0;
    MaxStackSort = 0;
    t0 = clock();
    QuickSort(v, 0, numElements-1);
    printf("RSDN QuickSort:  Cmp=%u, Swap=%u, MaxStack=%d Time=%u\n", 
           CmpQuickSort, SwapQuickSort, MaxStackSort, clock() - t0);
    check_sort(v);


    return 0;
}

Здравствуйте, McSeem2, Вы писали:

MS>Не знаю, много ли. Есть принципиально разные направления в программировании. Твой вариант QuickSort (так же как и исходный QuickSort2 из статьи) никуда не годятся и место им — на помойке. Но для тебя, например, это может быть несущественно, поскольку ну упала программа и упала — бывает.

Что касается "помойки": В худшем случае классика на 20% хуже отптимизированной версси. А при некотором стечении обстоятельств и вовсе лидирует (я уже говорил, что целочисленный ключь и жирный объект хранящийся в массиве по месту — это довольно частый случай).

Что касается "несущественно, поскольку ну упала программа и упала" это уже точно демогогия и к тому же оскорбительная.

MS>Но есть области, где падения в принципе недопустимы. Если алгоритм может упасть даже с вероятностью 10 в минус 100-й, то это уже не алгоритм а фуфло. Повторю еще раз — для каких-то майнстримовых задач это может быть и несущественно.

Этот алгоритм упадет только на гипотетических данных коих в придоре не встречается. Тут прийдется раздобыть огромный массив специально хитро упорядочинных данных. Ну, а параноидальный подход нужен разве что в ядерных реакторах и суровом риалтайме.

MS>Итак, обещанное разоблачение. Любой вариант чистого QuickSort в наихудшем случае требует O(N^2) времени и O(N)
MS>памяти.

Я где-то утверждал обратное?

MS> Как ни выбирай pivot, все равно такая последовательность может найтись. Совершеннто не имеет значения, какова вероятность такого события. Важно то, что она отлична от нуля. Если находится хоть один случай, на котором алгоритм падает, то он не является работоспособным.

Это параноя. Эдак вндовс вообще пользоваться нельзя, так как есть море случаев когда передав в параметры некоторой АПИ-функции что-нить странное упадет или данная задача, или вся винда.

MS>Такова цена твоей "красоты кода".
MS>Но Влад, конечно же скажет, что все это — фигня и не имеет значения по жизни. Ведь гораздо важнее, чтобы код был красивым, не правда ли?

Я скажу, что на этом форуме надо начинать боросться с демагогими и разоблачителями. И похоже начинать нажно с тебя.

MS>Я не уверен, можно ли завалить таким образом сортировку с отсечкой (K&R вариант). Может кто-нибудь попробовать найти killer sequence или доказать, что таковой не существует?

Сортировка вставками вроде как квадратичный алгоритм. Так что если основной алгоритм станет квадротичным, то и общая эффетивность тоже. Так что для K&R-варианта последовательность тоже есть. Просто она явно более сложная.

Заметь в K&R-варианте скорость тоже упала на треть.

Если нужны стабильные показатели, то надо использовать тот же мердж-сорт или хип-сорт. Им плевать на любые последовательности. Однако при прочих равных они будут стабильно более медленны. Далее каждый решает сам. Нужна ли ему параноидальная стабильность или же он хочет иметь большую скорость в общем случае.

Кстити, в большинстве библиотек используется совсем другая оптимизация. При превышении некоторого уровня рекурсии алгоритм переходит с quicksort на heapsort (который имеет стабильную функцию O(n log n)). Называется это Introsort. К слову в половине СТЛ используется именно он. Так что можешь просто подствить его и потестировать на каверзных вариантах.

MS> Это для меня важно, поскольку именно этот вариант я использую.

Какой? Тот что со специально подобранной последовательностью?


ЗЫ

В общем, еще раз обращусь к своему сообщению которое ты полез разоблачать:
Re[8]: Как уже правильно заметили

Автор: VladD2
Дата: 26.04.05

Так что ты в нем разоблачешь то?

Здравствуйте, VladD2, Вы писали:

VD>Что касается "помойки": В худшем случае классика на 20% хуже отптимизированной версси.

Это как так?! Я тебе продемонстрировал худший случай, на котором "классика" более чем в 30 раз хуже отптимизированной версии. Не веришь — запусти.

VD>А при некотором стечении обстоятельств и вовсе лидирует (я уже говорил, что целочисленный ключь и жирный объект хранящийся в массиве по месту — это довольно частый случай).

Как ты собираешься однозначно вычислять целочисленный ключ для строки? В общем случае это нереально — можешь поверить.
Хеш-функция тебя здесь не спасет.

MS>>Но есть области, где падения в принципе недопустимы. Если алгоритм может упасть даже с вероятностью 10 в минус 100-й, то это уже не алгоритм а фуфло. Повторю еще раз — для каких-то майнстримовых задач это может быть и несущественно.

VD>Этот алгоритм упадет только на гипотетических данных коих в придоре не встречается. Тут прийдется раздобыть огромный массив специально хитро упорядочинных данных. Ну, а параноидальный подход нужен разве что в ядерных реакторах и суровом риалтайме.

Внутри Oracle, например. Или даже MS SQL.
Программист, который заранее уверен в том, что его код никогда не будет использоваться в каких-либо критических приложениях — это не программист, а так халтурщик-аникейщик. Я не утверждаю, что это относится к тебе, но на всякий случай не говори больше подобных вещей — это тебя дискредитирует.

Хорошо, переходим снова на уровень объяснений на пальцах. Есть такое понятие, как "доказательство". Есть способ доказательства от противного, когда надо найти случай, однозначно опровергающий утверждение. Заметь, что достаточно одного-единственного случая. Итак, утверждение — "классический рекурсивный алгоритм быстрой сортировки является работоспособным". Опровержение — подготовить набор данных, на которой он падает. Что я и сделал. Одного единственного случая достаточно, чтобы доказать обратное — а именно то, что алгоритм не является работоспособным. Все нормальные люди называют это основами элементарной логики, Влад называет паранойей. Ну да ладно.

VD>Это параноя. Эдак вндовс вообще пользоваться нельзя, так как есть море случаев когда передав в параметры некоторой АПИ-функции что-нить странное упадет или данная задача, или вся винда.

Ты меня все больше разочаровываешь.

VD>"упадет или данная задача, или вся винда" "когда в параметры некоторой АПИ-функции что-нить странное упадет".

Вот именно! Это значит, что входные данные не являются валидными! В случае же сортировки, последовательность, приводящая к падению — полностью валидна. Пример невалидных данных для сортировки — имеем массив из 100 элементов, но говорим сортиворке, что у нас их 1000.


VD>Сортировка вставками вроде как квадратичный алгоритм. Так что если основной алгоритм станет квадротичным, то и общая эффетивность тоже. Так что для K&R-варианта последовательность тоже есть. Просто она явно более сложная.

Сможешь привести строгое доказательство? Здесь — взаимодействие двух методов сортировки. И если они обе по отдельности являются квадратичными, то это ни в коем случае не означает, что и вместе они являются квадратичным алгоритмом. Просто наихудшие случаи для них — разные.

VD>Заметь в K&R-варианте скорость тоже упала на треть.

Разумеется! В том-то и фишка, что для оптимизированного алгоритма эта последовательность тоже является наихудшей — медиана-то выбирается точно так же посередке. Но "оптимизация" спасает от сваливания в пропасть O(N^2). Но спасает ли она абсолютно надежно? Вот что я хочу выяснить. Так что сущность именно в защите от наихудшего случая, ну и как побочный эффект — некая дополнительная оптимизация.

MS>>Итак, обещанное разоблачение. Любой вариант чистого QuickSort в наихудшем случае требует O(N^2) времени и O(N)
MS>>памяти.

VD>Я где-то утверждал обратное?
VD>Так что ты в нем разоблачешь то?

Ты утверждал, что quick sort вообще не требует памяти. Ссылку на это твое сообщение дать?
И вообще, декламируешь этот алгоритм как однозначный рулез, а я тебе демонстрирую, что это не так. Вот и все дела. Попутно хочу выяснить, является ли алгоритм с отсечкой абсолютно надежным. Кто возьмется сочинить последовательность, которая его "завалит"? Пока что для меня не очевидно, что такая последовательность имеется. Не очевидно и обратное.

Здравствуйте, McSeem2, Вы писали:


MS>Я не уверен, можно ли завалить таким образом сортировку с отсечкой (K&R вариант). Может кто-нибудь попробовать найти killer sequence или доказать, что таковой не существует? Это для меня важно, поскольку именно этот вариант я использую. Если кто-то поможет доказать или опровергнуть — тему можно будет считать закрытой, а моя благодарность будет безграничной в разумных пределах

Если под словом отсечка имеется ввиду просто переход на insertion sort, то это ничего не дает. Сложность сортировки в худшем случае остается O(n^2). Переход на такую сортировку уменьшает возможную глубину дерева рекурсии на константу, в то время, как высота этого дерева может стать линейной. Поэтому (я уже выше об этом говорил) для того, чтобы не допустить линейной высоты дерева, применяют переход на тот же heapsort при достижении некоторой глубины. В результате получают алгоритм с оценкой в худшем случае O(nlogn) и сравнимый по скорости с обычным quicksort в среднем. Что-то я устал одно и то же писать.

Здравствуйте, McSeem2, Вы писали:

MS>Это как так?! Я тебе продемонстрировал худший случай, на котором "классика" более чем в 30 раз хуже отптимизированной версии. Не веришь — запусти.

Ты продемонстрировал вырожденный случай. Он встречается в основном только в тестовых примерах.

А нормальный худший случай — это просто не упорядоченные данные.

MS>Как ты собираешься однозначно вычислять целочисленный ключ для строки?

Хороший вопрос. Но лишний. Вообще-то методы есть, но они тут не причем.

MS> В общем случае это нереально — можешь поверить.

Немогу, так как сам в свое время делал подобные вещи.

MS>Хеш-функция тебя здесь не спасет.

Естествнно. Но если набор строк фиксированный, то для них можно банально сгенерировать идентификаторы. Но опять же это уже другой разговор. Не только строки используются в качестве ключей.

Случаи бывают разные.


VD>>Ну, а параноидальный подход нужен разве что в ядерных реакторах и суровом риалтайме.

MS>Внутри Oracle, например. Или даже MS SQL.

Приехали. В них родимых и быструю то сортировку фиг встретишь. Там все больше индексы. Да и у них тоже нет проблем с вырожденными последовательностями.

MS>Программист, который заранее уверен в том, что его код никогда не будет использоваться в каких-либо критических приложениях — это не программист, а так халтурщик-аникейщик.

Ну, ну. Все делим на черное и белое. Скажи, а ты в курсе, что кроме O(...) есть еще и некоторый X и Y? Ну, то что n может оказаться настолько большим, что даже алгоритм с линейной временной характеристикой окажется слабым местом? Или о том, что адеже очень шустрый код работающий на очень маленьких объемах данный может оказаться узким местом, так как он вызывается Х раз, а это самое Х велико?

И ты серьезно закладывашся на такие случаи? А ведь твой алгоритм теменуемо упадет или никогда не завершится.

Так что ты халтурщик?

Пойми, я в данном случае скорее согласен с тобой. Я тоже считаю, что нужно меньше оставлять на авось и т.п. Но всему есть предел. Разговоры о вырожденных случаях квиксорта — это чистой воды сражение с ветренными мельницами.

MS> Я не утверждаю, что это относится к тебе, но

... намекаю...

MS> на всякий случай не говори больше подобных вещей — это тебя дискредитирует.

Можно всетаки узнать какие вещи? И не нужно приклеивать ярлыки. Я попросту не боюсь ошибаться. Даже если я ошибаюсь, то делаю это от чистого сердца и измению свою точку зрения если получу достаточно для этого информации. В данном же случае я с тобой не согласен. И это нисколько меня не дескридитирует. Причем ни в каком случае.

MS>Хорошо, переходим снова на уровень объяснений на пальцах. Есть такое понятие, как "доказательство". Есть способ доказательства от противного, когда надо найти случай, однозначно опровергающий утверждение. Заметь, что достаточно одного-единственного случая. Итак, утверждение — "классический рекурсивный алгоритм быстрой сортировки является работоспособным". Опровержение — подготовить набор данных, на которой он падает.

Это не опровержение. Это попытка привести в качестве доказательств рассуждения о халтурности и т.п. Думаю как это классифицируется ты знашь.

Понимашь ли эдак можно доказать, что почти все бытовые электрические приборы на этой планете неработоспособны, так как если их поставить рядом с мощьным генератором электро-магнитного излучения или просто подать пару киловолт вместо 220, то они не будут работать. Ну, и соотвественно, что все кто не экранирует корпусы этих устройств и не делает сложных схем предотвращения поражение током высокой силы халтурщики. Но они не хатлурщики. Они просто разумные люди. Таких условий в реальных условиях не будет. А злобные буратины создавшие таки условия намереянно сами во всем будут виноваты.

MS> Что я и сделал. Одного единственного случая достаточно, чтобы доказать обратное — а именно то, что алгоритм не явля7ется работоспособным. Все нормальные люди называют это основами элементарной логики, Влад называет паранойей. Ну да ладно.

Т.е. мы продолжаем обсуждение в том же духе. Делим лдей на нормальных и Влада. Ясно. Давай ка ты оставишь свои классификации людей, для тех у кого с логикой настолько плохо, что они не способны замечать подобных вещей.

VD>>Это параноя. Эдак вндовс вообще пользоваться нельзя, так как есть море случаев когда передав в параметры некоторой АПИ-функции что-нить странное упадет или данная задача, или вся винда.

MS>Ты меня все больше разочаровываешь.

Я теб и не хотел очаровывать.

VD>>"упадет или данная задача, или вся винда" "когда в параметры некоторой АПИ-функции что-нить странное упадет".

MS>Вот именно! Это значит, что входные данные не являются валидными! В случае же сортировки, последовательность, приводящая к падению — полностью валидна. Пример невалидных данных для сортировки — имеем массив из 100 элементов, но говорим сортиворке, что у нас их 1000.

А ты уверен, что уже при 200 элементах ты вообще дождешся окончания сортировки при квадратичном то алгоритме? И будет ли это вылетом?

В общем, это все разговоры в пользу бедных. Если уж ты так бошся то вибирай точку разделения рандомом. Тогда никакая последовательность не окажется квадратичной. Но скорость упадет.


VD>>Сортировка вставками вроде как квадратичный алгоритм. Так что если основной алгоритм станет квадротичным, то и общая эффетивность тоже. Так что для K&R-варианта последовательность тоже есть. Просто она явно более сложная.

MS>Сможешь привести строгое доказательство?

Мне не нужно. Пусть этим занимаются Кнуты и езе с ними. Им за это деньги платят.

MS> Здесь — взаимодействие двух методов сортировки.

Бесспорно.

MS> И если они обе по отдельности являются квадратичными,

От это не правда. Быстрая сортировка в 99% случаев логорифмична.

MS> то это ни в коем случае не означает, что и вместе они являются квадратичным алгоритмом. Просто наихудшие случаи для них — разные.

Т.е. хочешь скзать, что соеденение двух квадратичных алгоритмов дает что-то более быстрое нежели квадратичный алгоритм? Вот это действительно было бы не плохо доказать.

VD>>Заметь в K&R-варианте скорость тоже упала на треть.

MS>Разумеется! В том-то и фишка, что для оптимизированного алгоритма эта последовательность тоже является наихудшей — медиана-то выбирается точно так же посередке. Но "оптимизация" спасает от сваливания в пропасть O(N^2). Но спасает ли она абсолютно надежно? Вот что я хочу выяснить. Так что сущность именно в защите от наихудшего случая, ну и как побочный эффект — некая дополнительная оптимизация.

Я уже говорил. Есть абсолютно надежные и доказанные методы вроде применения того же хип- или мердж-сортра при привышении некоего предела вложенности.

VD>>Я где-то утверждал обратное?
VD>>Так что ты в нем разоблачешь то?

MS>Ты утверждал, что quick sort вообще не требует памяти. Ссылку на это твое сообщение дать?

Дополнительной! Да не требует. И в не вырожденном случае расходы стэка тоже мизерны. Открой вики http://en.wikipedia.org/wiki/In-place_algorithm.

MS>И вообще, декламируешь этот алгоритм как однозначный рулез, а я тебе демонстрирую, что это не так.

Алгоритм действительно лучший в общем случае. А ты всего лишь демонстрируешь, что он поддается оптимизации которая сводится в основном к обходу его зуких мест. Дык я и не говорил, что он "The best" или вообще не имеет проблем. Вот только его оптимизация пузырьком — это не самое разумное решение. Это было плохим решением и во времена когда рекурсия стоила очень дорого. А сейчас уже и по давно.

MS> Вот и все дела. Попутно хочу выяснить, является ли алгоритм с отсечкой абсолютно надежным. Кто возьмется сочинить последовательность, которая его "завалит"? Пока что для меня не очевидно, что такая последовательность имеется. Не очевидно и обратное.

Боюсь, что твой алгоритм завалится даже на той же последовательности если дать по больше n. И это при том, что есть действительно O(n log n) алгоритмы.

Здравствуйте, McSeem2, Вы писали:
Ребята, я, честно говоря, не очень понимаю, на какую тему спор. Что, лень открыть Кнута III и посмотреть асимптотику средних и наихудших затрат для разных алгоритмов сортировки? Там их штук пятнадцать приведено. И обосновано, где и что быстрее. А также приведены алгоритмы, для которых до сих пор не установлено асимптотическое поведение.

Здравствуйте, VladD2, Вы писали:


VD>Алгоритм действительно лучший в общем случае.


Вот это надо рассказать разработчикам СУБД. .
Кстати такое подробное изучение и анализ алгоритмов сортировки обязаны именно разработчикам СУБД. Именно "в Общем случае" Merge сорт дает минимальное к — во сравнений и перестановок.

Это особенно важно и востребованно для сложных условий сравнения .


Еще раз замечу , что может quick sort обогнать у меня бв не получилось если идет речь о сортировке интов. Это надо ручками пробовать , а времени на это нету.

Здравствуйте, minorlogic, Вы писали:

M>Здравствуйте, VladD2, Вы писали:


VD>>Алгоритм действительно лучший в общем случае.


M>Вот это надо рассказать разработчикам СУБД. .
M>Кстати такое подробное изучение и анализ алгоритмов сортировки обязаны именно разработчикам СУБД. Именно "в Общем случае" Merge сорт дает минимальное к — во сравнений и перестановок.

Не совсем так, сравнений действительно меньше за счет того что одна серия закончилась а во второй еще осталось, а вот копирований n*Log(n) стабильно, именно это и беда этого алгоритма, хотя стабильного и малоуступающего квиксорту.
Кроме того для данных не умещающихся в память очень легко создать на его основе алгоритм с счтыванием данных в буффера и работы с ними.

Здравствуйте, Serginio1, Вы писали:


S> Не совсем так, сравнений действительно меньше за счет того что одна серия закончилась а во второй еще осталось, а вот копирований n*Log(n) стабильно, именно это и беда этого алгоритма, хотя стабильного и малоуступающего квиксорту.
S> Кроме того для данных не умещающихся в память очень легко создать на его основе алгоритм с счтыванием данных в буффера и работы с ними.

Да , обписался . у меня в голове все время слияние на списках работает , поэтому про масивы забываю.

Здравствуйте, minorlogic, Вы писали:

M>Здравствуйте, VladD2, Вы писали:

M>Вот это надо рассказать разработчикам СУБД. .

Расслабься, они об этом знают. Мы говорили о алгоритмах сортировки в памяти. В других условиях будут и другие алгритмы.

M>Кстати такое подробное изучение и анализ алгоритмов сортировки обязаны именно разработчикам СУБД. Именно "в Общем случае" Merge сорт дает минимальное к — во сравнений и перестановок.

Мердж-сорт требует копированиях. Этого достаточно чтобы проиграть при работе с памятью. Базы данных тут не причем. Эти алгоритмы были разработанны за долго до появления общедоступных СУБД.