这个桶排序函数为什么很慢？

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在STL中表示list<double>。

数组的内容在[0,1)范围内随机生成。理论上，桶排序对于大规模数据应该比快排更快，因为它的时间复杂度是O(n)，但是实际情况却不尽如人意，如下图所示：

我使用google-perftools对10000000个双精度浮点数进行了性能测试，结果如下：

看起来我不应该使用STL中的list，但是我想知道为什么？std_List_node_base_M_hook是用来做什么的？我应该自己编写一个list类吗？

PS: 实验和改进
我尝试只留下把元素放入桶中的代码，这表明大部分时间都用在建立桶上。
进行了以下改进： - 使用STL vector作为桶，并为其保留合理的空间。 - 使用两个辅助数组来存储用于构建桶的信息，从而避免使用链表，具体代码如下：

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”和“list,only put in”，“vector，reserve 8”和“vector，reserve 2”几乎重叠。
我将尝试使用足够多的内存保留较小的大小。

- luoq

---

O-边界是渐近定义的。在现实生活中，总是需要考虑常数因素。 - Peter G.

应该减少桶的数量吗？比如说 A.size() / some_const？或者是一个固定的数字（10，100）？ - ruslik

在这种情况下，我不会自己编写任何排序算法，而是使用目前为止看到的最快解决方案：STL的sort函数。 - Peter G.

+1 只是因为这张漂亮的图表和视觉背景：希望每个问题都能花这么多心思。 - John K

@John K：我同意，这个问题的展示方式很好。 - Matthieu M.

Answer 1

依我看，这里最大的瓶颈在于内存管理函数（例如new和delete）。

快速排序（STL可能使用了优化版本）可以原地对数组进行排序，这意味着它绝对不需要堆分配。这就是为什么它在实践中表现得如此出色。

桶排序依赖于额外的工作空间，在理论上假定该空间是随时可用的（即假定内存分配不需要任何时间）。在实践中，内存分配可能需要从（大量的）常数时间到线性时间的内存请求大小（例如，Windows在分配页面的同时需要时间来清零页面内容）。这意味着标准的链表实现将会受到影响，并支配您的排序运行时间。

尝试使用自定义列表实现，为大量项目预先分配内存，您应该会看到排序运行得更快。

- casablanca

---

我尝试使用向量作为桶（使用push_back，pop_back和为两个double保留空间），代码运行比使用列表更快，但将内容放入桶中也会消耗大部分时间。问题在于某些桶将具有较大的内容。如果为每个桶预先分配这些内容将浪费大量内存和时间。而且现在我不知道最大桶大小的分布情况。 - luoq

这些条件正是桶排序需要的，以便能够良好地执行：它假设您有足够的额外空间可供使用。 - casablanca

这也是为什么桶排序不适用于大型数据集的原因。 - casablanca

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 代码的含义。

看起来它只是用于在列表中的特定位置插入元素。应该不会花费太多时间...

- Loïc Février

---

size() 在我的环境（GCC）中似乎是恒定的，我会尝试你的第一个想法。 - luoq

即使是常量，在从列表中获取所有元素时，“正确”的方式是使用 empty/front/pop。 - Loïc Février

它无法解释那么多时间。我只是使用初始化桶（仅保留前两行）运行函数，从n=1000到4096000，运行时间为原始时间的2％-5％。 - luoq

我将尝试使用数组来存储桶的大小，并根据大小信息直接复制该数组到一个新数组中。因此，避免使用链表。然后我会检查运行时间。 - luoq

使用向量作为桶可以使代码更快，现在似乎是O(n)。 - luoq

Answer 3

链表不是数组。它们执行查找等操作明显较慢。STL排序可能有一个特定版本适用于链表，考虑到这一点并进行了优化，但您的函数盲目地忽略了它使用的容器。您应该尝试将STL向量作为您的数组使用。

- Puppy

---

STL列表仅用作桶，只使用push_back、front和pop_front，应该需要const时间。唯一的排序是insertionsort（A），其中A实际上是双精度类型的数组。 - luoq

@luoq：你正在对列表调用size()方法，这是O(N)的时间复杂度，而不是O(1)。 - Oliver Charlesworth

@Oli Charlesworth：大小的复杂度是“常数(建议)。在某些实现中是线性的。”所以这可能会使函数变慢。但是即使它是O(n)，总的额外时间也应该是O(A的大小)。无论如何，我会尽量不使用大小。 - luoq

@Loic: O(1) 的 size() 和 O(1) 的 splice() 存在冲突，因此可能是，也可能不是。GNU 实现是一个时间复杂度为 O(N) 的例子（它调用了 std::distance()）。 - Oliver Charlesworth

@Loïc Février：查看SGI文档，他们记录了函数的复杂性。如果您查看“新成员”部分，所有版本的splice，包括“range”版本都被记录为“这个函数是常数时间的”。要做到恒定时间，就不能对该范围进行迭代！请参阅http://www.sgi.com/tech/stl/List.html。 - André Caron

Answer 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 的列表进行排序，观察您的堆管理器试图创建 49 亿个列表时会发生什么。

- Eric Towers

---

数组的内容是在[0,1)范围内随机生成的。因此，只需创建numBuckets个桶，所有元素都可以放入其中。 - luoq

Answer 5

我没有真正深入了解您的代码细节，因为我在我的学习过程中还不够了解Java，尽管我有一些算法和C编程的经验，所以这是我的意见：

如果假设元素在数组上分布公平，则桶排序实际上更像是一个条件，使得您的桶排序可以在O(n)上工作。请注意，在最坏的情况下，可能会将大量元素放在一个桶中，因此在下一次迭代中，您将处理几乎与您一开始尝试修复的相同问题，这会导致性能不佳。

请注意，桶排序的实际时间复杂度为O(n+k)，其中k是桶的数量，您是否计算了桶的数量？ k = O(n)吗？

桶排序中最浪费时间的问题是在将元素划分到桶后的空桶，当连接已排序的桶时，您无法告诉桶是否为空，而必须进行实际测试。

希望我有所帮助。

- Ofek Ron