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

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

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). Теоретически ведро сортировки должно быть быстрее, чем quicksort для больших размеров для 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]);
}

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

Ответ 1

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.

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

Ответ 2

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

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

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

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

Ответ 3

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

Ответ 4

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

Рассмотрим вход {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 миллиарда списков.

Ответ 5

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

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

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

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

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