-1

所以我已经实现了一个快速排序的版本，但我不确定我是否以最佳方式做到了。我正在排序的向量中的元素是 3D 点。您会注意到，在拆分数组时，它会显示“if(level == 1), if(level == 2), etc” 这是因为取决于我何时调用快速排序，x、y 或 z 坐标点数是排序的基础。

我的代码如下。我已经测试了我的算法，它似乎正确地对点进行了排序，但是我觉得我可能有很多开销或其他东西，因为它的运行速度没有我希望的那么快，特别是因为我必须打电话此排序函数多次对多达 500,000 个元素的数组进行排序。

我可以做些什么来改进/清理/加速我的排序算法？

std::vector<Point> SortPoints(std::vector<Point> points, int level)
{
    if(points.size() <= 1) return points;
    std::vector<Point> s1, s2;
    size_t index = ((float)rand()/RAND_MAX)*(points.size()-1);
    Point pivot = points[index];
    points.erase(points.begin() + index);
    size_t size = points.size();
    for(int i = 0; i < size; i++)
    {
        if(level == 1)
        {
            if(points[i].pos.x <= pivot.pos.x) s1.push_back(points[i]);
            else s2.push_back(photons[i]);
        } else if(level == 2)
        {
            if(points[i].pos.y <= pivot.pos.y) s1.push_back(points[i]);
            else s2.push_back(photons[i]);
        } else if(level == 3)
        {
            if(points[i].pos.z <= pivot.pos.z) s1.push_back(points[i]);
            else s2.push_back(photons[i]);
        }
    }
    if(s1.size() == 0) return Concatenate(s1, pivot, s2); 
    else if(s2.size() == 0) return Concatenate(s1, pivot, s2);
    else return Concatenate(SortPoints(s1, level), pivot, SortPoints(s2, level)); 
}

std::vector<Point> Concatenate(std::vector<Point> s1, 
                                       Point p, std::vector<Point> s2)
{  
    std::vector<Point> result;
    result.reserve(s1.size()+s2.size()+1);
    result.insert(result.end(), s1.begin(), s1.end());
    result.push_back(p);
    result.insert(result.end(), s2.begin(), s2.end());
    return result;
}
4

2 回答 2

2

您的主要问题是您在分区时创建副本。在幕后进行了大量的内存分配和复制。

如果您希望它更快，则需要就地排序（并且不要按值传递大量向量）。

除非这是实现快速排序的练习，否则您应该使用std::sort自定义比较函数。

于 2012-12-05T06:39:13.327 回答
1

所以这里有一些观察：

  • 正如其他人所指出的，您应该考虑使用 std 实现作为基准。
  • 您可以预先保留要分类的向量，而不是让它们不断增长和重新分配。
  • 跳过循环中的枢轴可能会更好，而不是从向量中删除它，因为后者可能需要大量复制数据。
  • 您不必费心将数据复制到新向量中并将它们连接起来，而是就地排序。
  • 您也许可以选择比随机选择更好的支点（尤其是如果您的数据是预先排序的）。
  • 您可以更改 Point 的实现以允许索引 xyz 而不必使用 if()

从本质上讲，这似乎是一个非常幼稚的实现，您可能需要做很多工作，并利用您自己数据的专业知识，才能击败预先提供的版本。

于 2012-12-05T07:14:41.753 回答