Что делает эту функцию сортировки корзины медленной?

Question

Функция определяется как

void bucketsort(Array& A){
  size_t numBuckets=A.size();
  iarray<List> buckets(numBuckets);

  //put in buckets
  for(size_t i=0;i!=A.size();i++){
    buckets[int(numBuckets*A[i])].push_back(A[i]);
  }

  ////get back from buckets
  //for(size_t i=0,head=0;i!=numBuckets;i++){
  //size_t bucket_size=buckets[i].size();
  //for(size_t j=0;j!=bucket_size;j++){
  //  A[head+j] = buckets[i].front();
  //  buckets[i].pop_front();
  //}
  //head += bucket_size;
  //}
 for(size_t i=0,head=0;i!=numBuckets;i++){
   while(!buckets[i].empty()){
     A[head]          = buckets[i].back();
     buckets[i].pop_back();
     head++;
   }
 }

  //inseration sort
  insertionsort(A);
}

, где List - это просто list<double> в STL.

Содержимое массива генерируется случайным образом в [0,1). Теоретически сортировка по сегментам должна быть быстрее, чем быстрая сортировка для большого размера, для его O (n), но она не выполняется, как показано на следующем графике.

Я использую google-perftools, чтобы профилировать его в двойном массиве 10000000. Он сообщает, как следует

Кажется, мне не следует использовать список STL, но мне интересно, почему? Что делает std_List_node_base_M_hook? Должен ли я сам написать список классов?

PS: эксперимент и улучшение
Я попытался просто оставить коды для размещения ведер, и это объяснило, что большая часть времени используется для наращивания ведер.
Произведено следующее улучшение: - Используйте вектор STL в качестве сегментов и оставьте достаточно места для блоков. - Используйте два вспомогательных массива для хранения информации, используемой при построении сегментов, таким образом избегая использования связанного списка, как в следующем коде

void bucketsort2(Array& A){
  size_t    numBuckets = ceil(A.size()/1000);
  Array B(A.size());
  IndexArray    head(numBuckets+1,0),offset(numBuckets,0);//extra end of head is used to avoid checking of i == A.size()-1

  for(size_t i=0;i!=A.size();i++){
    head[int(numBuckets*A[i])+1]++;//Note the +1
  }
  for(size_t i=2;i<numBuckets;i++){//head[1] is right already
    head[i] += head[i-1];
  }

  for(size_t i=0;i<A.size();i++){
    size_t  bucket_num         = int(numBuckets*A[i]);
    B[head[bucket_num]+offset[bucket_num]] = A[i];
    offset[bucket_num]++;
  }
  A.swap(B);

  //insertionsort(A);
  for(size_t i=0;i<numBuckets;i++)
    quicksort_range(A,head[i],head[i]+offset[i]);
}

Результат на следующем графике где строка начинается со списка с использованием списка в качестве сегментов, начинается с вектора с использованием вектора в качестве сегментов, начинается с 2 с использованием вспомогательных массивов. По умолчанию используется сортировка вставки по умолчанию, а некоторые используют быструю сортировку, так как размер сегмента большой.
Обратите внимание, что «список» и «список, только вставленный», «вектор, резерв 8» и «вектор, резерв 2» почти перекрываются.
Я попробую маленький размер с достаточным количеством зарезервированной памяти.

Answer 1

На мой взгляд, самое большое узкое место здесь - это функции управления памятью (такие как new и delete).

Быстрая сортировка (из которых STL, вероятно, использует оптимизированную версию) может сортировать массив на месте, что означает, что он не требует абсолютно никаких распределений кучи. Вот почему он так хорошо работает на практике.

Сортировка сегментов основана на дополнительном рабочем пространстве, которое, как предполагается, легко доступно в теории (то есть предполагается, что выделение памяти вообще не занимает много времени). На практике выделение памяти может занимать от (большого) постоянного времени до линейного времени в размере запрошенной памяти (например, Windows потребует времени для обнуления содержимого страниц при их выделении). Это означает, что стандартные реализации связанного списка пострадают и будут доминировать во времени выполнения вашего вида.

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

Answer 2

С

iarray<List> buckets(numBuckets);

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

Попробуйте уменьшить количество сегментов.

Чтобы проверить мое утверждение, проанализируйте скорость своего кода с помощью только создания списков.

Также для перебора элементов списков вы не должны использовать .size() а точнее

//get back from buckets
for(size_t i=0,head=0;i!=numBuckets;i++)
  while(!buckets[i].empty())
  {
    A[head++] = buckets[i].front();
    buckets[i].pop_front();
  }

В некоторых реализациях .size() может быть в O (n).Вряд ли, но ...

---

После некоторых исследований я обнаружил эту страницу , объясняющую, что такое код для std :: _ List_node_base :: hook.

Кажется, этотолько для вставки элемента в определенном месте в списке.Не должно стоить много ..

Answer 3

Я думаю, что, возможно, интересный вопрос, Почему вы создаете чрезмерно большое количество сегментов?

Рассмотрите ввод {1,2,3}, numBuckets = 3.Цикл, содержащий buckets[int(numBuckets*A[i])].push_back(A[i]);, собирается развернуться до

buckets[3].push_back(1);  
buckets[6].push_back(2);  
buckets[9].push_back(3);  

Правда?Девять сегментов для трех значений ...

Подумайте, передали ли вы перестановку диапазона 1..100.Вы создали бы 10 000 ведер и использовали бы только 1% из них.... и каждый из этих неиспользованных сегментов требует создания в нем списка.... и должен быть повторен и затем отброшен в цикле считывания.

Еще более захватывающим является сортировка списка 1..70000 и наблюдение за тем, как ваш менеджер кучи взрывается, пытаясь создать 4,9 миллиарда списков.

Answer 4

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

Answer 5

Мне не удалось детально разобраться в деталях вашего кода, так как на данный момент я недостаточно разбираюсь в Java, хотя у меня был некоторый опыт работы в алгоритмах и программировании на C, поэтому вот мое мнение:

Сортировка сегментов при условии справедливого распределения элементов в массиве, что на самом деле больше похоже на условие для вашей сортировки сегментов для работы с O (n), в худшем случае обратите внимание, что вы можете поместить большое количество элементов на Таким образом, в следующей итерации вы столкнетесь почти с той же проблемой, что и пытались исправить, что приводит к плохой производительности.

Обратите внимание, что ACTUALL Time Сложность сортировки Bucket равна O (n + k), где k - количество сегментов, вы считали свои сегменты? k = O (n)?

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

надеюсь, я помог.