2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 C++ сортировка
Сообщение27.10.2011, 15:44 
Пытаюсь сам написать быструю сортировку. Сортирую вектор из даблов.
Вот что получилось:
Код:
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 работает во много-много раз быстрее. Я понимаю, что она написана хорошо, но разница слишком велика.

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

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

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

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

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

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

 
 
 
 Re: C++ сортировка
Сообщение27.10.2011, 18:07 
Circiter в сообщении #496503 писал(а):
Можно ещё попробовать вместо двойного рекурсивного вызова обойтись одним. Правда это не приводит к ускорению, а только к снижению глубины рекурсии и лишь косвенному увеличению бвстродействия за счет экономии стека (с той же целью можно ещё и пробовать локальные переменные в LomutoPartition пообъявлять как static).
Это оптимизатор тоже может сам сделать.

Circiter в сообщении #496503 писал(а):
Можно попробовать временно использовать другую эвристику для выбора опорного элемента, без случайности. Хотя именно случайный выбор эффективней всего... Странно.
Это свойство Lomuto Partition. Если уж менять алгоритм, то лучше использовать более эффективный Hoare Partition.

Circiter в сообщении #496503 писал(а):
Хм, забавный трюк с rand() % (end_of_array - begin_of_array). :) Кстати, это точно правильно работает?
Довольно существенный приём для Lomuto Partition, иначе пришлось бы бороться с бесконечной рекурсией.

 
 
 
 Re: C++ сортировка
Сообщение27.10.2011, 18:32 
2venco
Цитата:
Это оптимизатор тоже может сам сделать.

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

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

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

 
 
 
 Re: C++ сортировка
Сообщение27.10.2011, 20:08 
Circiter в сообщении #496521 писал(а):
2venco
Цитата:
Это оптимизатор тоже может сам сделать.

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

Circiter в сообщении #496521 писал(а):
Цитата:
иначе пришлось бы бороться с бесконечной рекурсией.

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

 
 
 
 Re: C++ сортировка
Сообщение29.10.2011, 09:16 
2venco
Цитата:
Рандомизация - один из способов это обойти.

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

 
 
 
 Re: C++ сортировка
Сообщение29.10.2011, 16:42 
Circiter в сообщении #497024 писал(а):
2venco
Цитата:
Рандомизация - один из способов это обойти.

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

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

 
 
 
 Re: C++ сортировка
Сообщение19.12.2014, 23:15 
Работает так медленно потому, что не производится проверка в начале 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;

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

 
 
 
 Re: C++ сортировка
Сообщение21.12.2014, 11:35 
st_pr-r в сообщении #496472 писал(а):
Пытаюсь сам написать быструю сортировку. Сортирую вектор из даблов.
Вот что получилось:
А если все компоненты вектора одинаковы?

 
 
 
 Re: C++ сортировка
Сообщение21.12.2014, 17:59 
Через три года после создания темы st_pr-r непременно ответит. :wink:

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group