C++ сортировка

[st_pr-r]

Пытаюсь сам написать быструю сортировку. Сортирую вектор из даблов.
Вот что получилось:

vector<double>::iterator LomutoPartition(
    const vector<double>::iterator& begin_of_array,
    const vector<double>::iterator& end_of_array) {
  vector<double>::iterator first_in_greaters = begin_of_array;
  vector<double>::iterator end_of_scanned = begin_of_array;
  double pivot =
      *(begin_of_array + rand() % (end_of_array - begin_of_array)) ;
  while (end_of_scanned != end_of_array) {
    if (*end_of_scanned <= pivot) {
      swap(*end_of_scanned, *first_in_greaters);
      ++first_in_greaters;
    }
    ++end_of_scanned;
  }
  return first_in_greaters;
}

void QuickSort(
    const vector<double>::iterator& begin_of_array,
    const vector<double>::iterator& end_of_array) {
// if size is not big - use simple sort
  if (end_of_array - begin_of_array <= 10) {
    SelectionSort(begin_of_array, end_of_array);
    return;
  }

  vector<double>::iterator first_right_part =
       LomutoPartition(begin_of_array, end_of_array);
  if (first_right_part - begin_of_array < end_of_array - first_right_part) {
    QuickSort(begin_of_array, first_right_part);
    QuickSort(first_right_part, end_of_array);
  } else {
    QuickSort(first_right_part, end_of_array);
    QuickSort(begin_of_array, first_right_part);
  }
}

Но работает оочень медленно. Selection Sort - там квадратичная сортировка, которую вызываю при малых размерах.
Если делаю так же, но не с итераторами, а индексами (то есть вектор передавать как vector<double>* ?), то эффекта нет.
Говорю "медленно", потому что std::sort работает во много-много раз быстрее. Я понимаю, что она написана хорошо, но разница слишком велика.

В чем может быть проблема?

[venco]

Возможно, вы компилируете без оптимизации. При этом все операции на итераторах транслируются в прямые вызовы функций (они инлайновые, и при оптимизации был бы подставлен их код, обычно очень простой). Вообще эффективность STL сильно зависит от оптимизации, и если её выключить, то код может оказаться на порядок (десятичный) медленнее.

Рекомендую ещё передавать итераторы по значению, а не const ссылке, это поможет оптимизатору.

[Circiter]

Можно ещё попробовать вместо двойного рекурсивного вызова обойтись одним. Правда это не приводит к ускорению, а только к снижению глубины рекурсии и лишь косвенному увеличению быстродействия за счет экономии стека (с той же целью можно ещё и локальные переменные в LomutoPartition пообъявлять как static, но возможно это глупость).

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

Хм, забавный трюк с rand() % (end_of_array - begin_of_array). :) Кстати, это точно правильно работает?

[venco]

Circiter в сообщении #496503 писал(а):

Можно ещё попробовать вместо двойного рекурсивного вызова обойтись одним. Правда это не приводит к ускорению, а только к снижению глубины рекурсии и лишь косвенному увеличению бвстродействия за счет экономии стека (с той же целью можно ещё и пробовать локальные переменные в LomutoPartition пообъявлять как static).

Это оптимизатор тоже может сам сделать.

Circiter в сообщении #496503 писал(а):

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

Это свойство Lomuto Partition. Если уж менять алгоритм, то лучше использовать более эффективный Hoare Partition.

Circiter в сообщении #496503 писал(а):

Хм, забавный трюк с rand() % (end_of_array - begin_of_array). :) Кстати, это точно правильно работает?

Довольно существенный приём для Lomuto Partition, иначе пришлось бы бороться с бесконечной рекурсией.

[Circiter]

2venco

Цитата:

Это оптимизатор тоже может сам сделать.

Оптимизаторы научилсиь самостоятельно сворачивать двойную хвостовую рекурсию? Здорово. Ну насчет static'а согласен.

Цитата:

иначе пришлось бы бороться с бесконечной рекурсией.

Откуда она там возьмется-то? Вроде-бы qsort всегда завершается независимо от алгоритма выбора опорного элемента... Ok, я попробую поразбираться...

[venco]

Circiter в сообщении #496521 писал(а):

2venco

Цитата:

Это оптимизатор тоже может сам сделать.

Оптимизаторы научилсиь самостоятельно сворачивать двойную хвостовую рекурсию?

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

Circiter в сообщении #496521 писал(а):

Цитата:

иначе пришлось бы бороться с бесконечной рекурсией.

Откуда она там возьмется-то? Вроде-бы qsort всегда завершается независимо от алгоритма выбора опорного элемента... Ok, я попробую поразбираться...

В обычном qsort используется более сложное деление. А в Lomuto Partition одна из половин может оказаться нулевой длины, а другая - полного размера, и с этим надо специально бороться. Рандомизация - один из способов это обойти.

[Circiter]

2venco

Цитата:

Рандомизация - один из способов это обойти.

Ну вы же понимаете, что меня взволновала не рандомизация, а способ её осуществления: rand() % (end_of_array - begin_of_array). Я имею ввиду, что если вместо итераторов с проверкой выхода за границы будут использоваться обычные указатели, то такой случайный индекс будет указывать неизвестно куда.

[venco]

Circiter в сообщении #497024 писал(а):

2venco

Цитата:

Рандомизация - один из способов это обойти.

Ну вы же понимаете, что меня взволновала не рандомизация, а способ её осуществления: rand() % (end_of_array - begin_of_array). Я имею ввиду, что если вместо итераторов с проверкой выхода за границы будут использоваться обычные указатели, то такой случайный индекс будет указывать неизвестно куда.

Почему?
(end_of_array - begin_of_array) - количество элементов, и для random-access итераторов, и для указателей.

[Circiter]

Это меня приглючило. Я почему-то не мог понять, каким образом rand()%N никогда не достигает N. Всё, разобрался, спасибо. Спать надо больше. :)

[uggot]

Работает так медленно потому, что не производится проверка в начале QuickSort'a:

if (begin_of_array == end_of_array)
    return;
vector<double>::iterator first_right_part = LomutoPartition(begin_of_array, end_of_array);
if (first_right_part == end_of_array)
    return;

У меня сие изменение очень сильно ускорило скорость выполнения.

[guryev]

st_pr-r в сообщении #496472 писал(а):

Пытаюсь сам написать быструю сортировку. Сортирую вектор из даблов.
Вот что получилось:

А если все компоненты вектора одинаковы?

[arseniiv]

Через три года после создания темы st_pr-r непременно ответит.