小编luo*_*uoq的帖子

该功能定义为

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 = …

是否有一个简单的工具来为递归算法生成运行时调用树？如下面的计算Fibonacci数:

更具体地说,如果算法是用C/C++实现的呢？

编辑:我希望这棵树分析递归算法的复杂性.我知道如何生成树.以前我只是在soure文件中添加一些"cout"并生成一个点文件并使用graphviz生成树.但我想知道是否有一些好的工具,这样我就可以节省编写代码的时间.

编辑:斐波纳契数的示例代码是

//fib.cpp
#include<iostream>
typedef int Int;

Int fib(Int n)
{
  if (n==0)
    return 1;
  else if (n==1)
    return 1;
  else
    return fib(n-2)+fib(n-1);
}

int main()
{
  std::cout<<fib(5)<<std::endl;
  return 0;
}

我已经尝试了valgrind这个简单的代码,但无法找到如何获取图形.我使用的命令如下:

g++ fib.cpp
valgrind --tool=callgrind ./a.out
kcachegrind callgrind.out.4343

我错过了一些选项还是什么？

我想使用堆栈来存储数组的索引,所以我使用以下typedef,其中istack是堆栈的模板类:

typedef istack<size_t> IndexStack;

并且我声明了一个堆栈

IndexStack    stack;

但是当我调用以下函数时(其中A.size()返回size_t);

stack.push_back(A.size());

GCC给出以下错误

sort.cpp: In function 'void quicksort2(Array&)':
sort.cpp:50:27: error: no matching function for call to 'istack<unsigned int>::push_back(size_t)'
iarray.h:103:8: note: candidate is: void istack<T>::push_back(T&) [with T = unsigned int]

我怎样才能使它工作？