是什么让这个桶排序功能变慢？

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);
}

STL List就list<double>在哪里.

数组的内容是随机生成的[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]);
}

结果如下图所示 使用list作为存储区的行以列表开头,使用向量作为存储区的向量开始,使用帮助程序数组启动2.最后使用默认插入排序,有些使用快速排序,因为存储桶大小很大.
注意"列表"和"列表,仅放入","向量,保留8"和"向量,保留2"几乎重叠.
我将尝试小尺寸,保留足够的内存.

Answer 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 的代码是什么。

似乎只是在列表中的给定位置插入一个元素。应该不会花很多钱..