排序优化-需要高级策略 [英] Sorting optimization - high level strategies wanted
问题描述
大家好
我今天写的一段代码对3d网格的边缘进行排序以进行处理.本质上，我已经链接了排序边缘的列表.然后，我处理一些现在变脏的边缘(列表中的乱序).然后，我使用以下代码首先从列表中删除脏边缘(留下不完整但已排序的列表).然后，我将脏边重新插入列表中的正确位置(保留完整的排序列表).然后，我对此过程进行了数千次迭代.
以下代码片段可以正常工作，但速度太慢.我进行了时间分析，发现这段代码消耗了90％以上的处理时间.使用具有15,000条边的列表进行8000次迭代时，这大约需要30秒.这是满足我需求的方法.
现在，我试图弄清楚我应该怎么做，并希望这里的一些更有经验的程序员能够为我提供有关如何加快速度的建议.一些高级指针可以帮助我优化排序算法.
我在这里问是因为我已经搜索了排序算法，并且有很多简单的算法可以工作(例如，我尝试了shell-sort算法)，但是它们似乎也太慢了.但是，也许在我在这篇文章中概述的限制内，有一些算法技巧可以加快这一过程.
任何帮助将不胜感激！
Hello everyone
I have a piece of code that I wrote today that sorts the edges of a 3d mesh for processing. Essentially, I have linked list of sorted edges. I then process some edges that now become dirty (out of order in the list). I then use the following code to first delete the dirty edges from the list (leaving an incomplete but sorted list). I then insert the dirty edges back into the list in the right position (leaving a complete sorted list). I then iterate over this process some thousands of times.
The following code snip-it works fine but is too slow. I''ve done a time analysis and found that this code consumes over 90% of the processing time. This amounts to about 30 seconds for 8000 iterations using a list with 15,000 edges. It is way to slow for my needs.
Now I''m trying to figure out what I should do and was hoping that some of the more experienced programmers here might be able to advise me on how to go about speeding this up. Some high level pointers to what I should do to optimize the sorting algorithm would be good.
I ask here because I''ve searched on sorting algorithms and there is a lot of simple algorithms that work (e.g. I''ve tried the shell-sort algorithm) but they also seem too slow. However, maybe within the constraints I''ve outlined in this post there are some algorithmic tricks to speed this up.
Any help would be appreciated!!!
//////////////////////////////////////////////////////////////////////
list<error_node> edge_head; // list of mesh edges
vector<list<error_node>::iterator> edge_map; // vector of iterators that point to each edge in egde_head
vector<error_node> sort_edge; // vector of dirty edges
struct error_node
{
float err; // error value used to sort the list
int ind; // index of edge
};
// compare function is used to std::sort
bool compare(error_node first, error_node second)
{
if (first.err >= second.err)
return false;
return true;
}
/////////////////////////////////////////////////////////////////////
// region of code that takes 90% of running time
if (!sort_edge.empty())
{
std::sort(sort_edge.begin(), sort_edge.end(), compare); // sort edges into ascending `err` values
// next for loop removes dirty edges from edge_head leaving an incomplete but sorted list
vector<error_node>::iterator vec;
for (vec=sort_edge.begin(); vec!=sort_edge.end(); vec++){
// erase edge with index ind using edge_map which is an indexing of the error_nodes in edge_head e.g. suppose (*vec).ind == 10 then edge_map[10] is an iterator to the error_node with index 10 in edge_head list
edge_head.erase(edge_map[(*vec).ind]);
}
//next bit of code inserts the dirty edges back into the list in the right order
vec=sort_edge.begin();
for (lis=edge_head.begin(); lis!=edge_head.end(); lis++){
if ((*lis).err>=(*vec).err){
lis = edge_head.insert(lis, *vec);
edge_map[(*vec).ind] = lis;
vec++;
}
if (vec==sort_edge.end())
break;
}
// now insert the remaining dirty edges at the end of the list.
while (vec!=sort_edge.end()){
edge_head.push_back(*vec);
edge_map[(*vec).ind] = (--edge_head.end());
vec++;
}
sort_edge.clear();
}
推荐答案
如果我们编写一个小程序来将您的排序与其他排序进行比较，则可以看到是否有更有效的算法.
If we make a little program to compare your sort to some others, we can see if there is a more efficient algorithm.
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <mmsystem.h> //for timeGetTime()
#include <vector>
#include <list>
#include <algorithm>
using std::vector;
using std::list;
static DWORD gs_nStartTime = 0;
#pragma comment(lib, "winmm.lib") //for mmsystem.h
void StartTimer() {
gs_nStartTime = timeGetTime();
}
void StopTimer(LPSTR szName) {
printf("%s sort took %ums\n", szName, timeGetTime() - gs_nStartTime);
}
struct error_node {
float err; // error value used to sort the list
int ind; // index of edge
};
//Create some variable types for convenience
typedef list<error_node> edge_head_t;
typedef vector<edge_head_t::iterator> edge_map_t;
typedef vector<error_node> sort_edge_t;
//This is your compare function
//Note that it is passed by value. This creates a copy of both
//"first" and "second" every time this function is called.
bool StdCompare(error_node first, error_node second) {
if (first.err >= second.err) {
return false;
}
return true;
}
int QSortCompare(const void *pElem1, const void *pElem2) {
if (((error_node *)pElem1)->err < ((error_node *)pElem2)->err) { //less than
return -1;
} else if (((error_node *)pElem1)->err > ((error_node *)pElem2)->err) { //greater than
return 1;
}
return 0; //equal
}
//This is your sorting algorithm:
void YourSort(float *pEdgesArray, unsigned nEdges, unsigned *pDirtyArray, unsigned nDirtyEdges) {
edge_head_t edge_head; // list of mesh edges
edge_map_t edge_map; // vector of iterators that point to each edge in egde_head
sort_edge_t sort_edge; // vector of dirty edges
//Setup
//edge_head
for (unsigned nEdge = 0; nEdge < nEdges; ++nEdge) {
error_node enNew;
enNew.ind = nEdge;
enNew.err = pEdgesArray[nEdge];
edge_head.insert(edge_head.end(), enNew);
}
//edge_map
for (edge_head_t::iterator iEdge = edge_head.begin(); iEdge != edge_head.end(); ++iEdge) {
edge_map.push_back(iEdge);
}
//sort_edge
for (unsigned nEdge = 0; nEdge < nDirtyEdges; ++nEdge) {
error_node enNew;
enNew.ind = pDirtyArray[nEdge];
enNew.err = pEdgesArray[enNew.ind];
sort_edge.push_back(enNew);
}
//Now start the timer and sort
StartTimer();
if (!sort_edge.empty()) {
std::sort(sort_edge.begin(), sort_edge.end(), StdCompare); // sort edges into ascending `err` values
// next for loop removes dirty edges from edge_head leaving an incomplete but sorted list
sort_edge_t::iterator vec;
for (vec = sort_edge.begin(); vec != sort_edge.end(); ++vec){ //NOTE: ++vec is faster than vec++, especially for iterators
// erase edge with index ind using edge_map which is an indexing of the error_nodes in edge_head e.g. suppose (*vec).ind == 10 then edge_map[10] is an iterator to the error_node with index 10 in edge_head list
edge_head.erase(edge_map[(*vec).ind]);
}
//next bit of code inserts the dirty edges back into the list in the right order
vec = sort_edge.begin();
for (edge_head_t::iterator lis = edge_head.begin(); lis != edge_head.end(); ++lis){
if ((*lis).err >= (*vec).err){
lis = edge_head.insert(lis, *vec);
edge_map[(*vec).ind] = lis;
++vec;
}
if (vec == sort_edge.end()) {
break;
}
}
// now insert the remaining dirty edges at the end of the list.
while (vec != sort_edge.end()){
edge_head.push_back(*vec);
edge_map[(*vec).ind] = (--edge_head.end());
++vec;
}
sort_edge.clear();
}
StopTimer("Your");
}
//Just a simple vector with no insert/remove
void SimpleStdVectorSort(float *pEdgesArray, unsigned nEdges) {
sort_edge_t sort_edge; // vector of ALL edges
//Setup
//sort_edge
for (unsigned nEdge = 0; nEdge < nEdges; ++nEdge) {
error_node enNew;
enNew.ind = nEdge;
enNew.err = pEdgesArray[nEdge];
sort_edge.push_back(enNew);
}
//Now start the timer and sort
StartTimer();
std::sort(sort_edge.begin(), sort_edge.end(), StdCompare); // sort edges into ascending `err` values
StopTimer("std::vector");
}
//Using the ANSI qsort
void QSort(float *pEdgesArray, unsigned nEdges) {
//Setup
error_node *pNodes = new error_node[nEdges];
for (unsigned nEdge = 0; nEdge < nEdges; ++nEdge) {
pNodes[nEdge].ind = nEdge;
pNodes[nEdge].err = pEdgesArray[nEdge];
}
//Now start the timer and sort
StartTimer();
qsort(pNodes, nEdges, sizeof(error_node), &QSortCompare);
StopTimer("qsort");
delete []pNodes;
}
//Testing
int SetupCompare(const void *pElem1, const void *pElem2) {
if (*(float *)pElem1 < *(float *)pElem2) { //less than
return -1;
} else if (*(float *)pElem1 > *(float *)pElem2) { //greater than
return 1;
}
return 0; //equal
}
int main() {
printf("Setting up. Please wait.\n");
//This is how many elements will be sorted.
//You should change this to what you would expect to be your common case.
//Results may vary widely if your common case is only 500, or 1,000,000
const int nElements = 15000;
//This is how many "dirty" elements will be in the array.
//You should change this to what you would expect to be your common case.
//Results may vary widely if your common case is 1% of the array or 95% of the array.
const int nRandomElements = 1000; //1000 elements will be randomised again after the initial sort
float *pSortArray = new float[nElements];
unsigned *pDirtyArray = new unsigned[nRandomElements];
for (int nElement = 0; nElement < nElements; ++nElement) {
pSortArray[nElement] = rand() * 4.0f / RAND_MAX; //generate a bunch of random numbers in the range [0.0, 4.0)
}
qsort(pSortArray, nElements, sizeof(float), &SetupCompare);
//We now have a completly sorted array.
//Now inject a bit of randomness.
for (int nElement = 0; nElement < nRandomElements; ++nElement) {
bool bAlreadyExists;
do {
bAlreadyExists = false;
pDirtyArray[nElement] = rand() % nElements;
for (int nTest = 0; nTest < nElement; ++nTest) {
if (pDirtyArray[nElement] == pDirtyArray[nTest]) {
bAlreadyExists = true;
break;
}
}
} while (bAlreadyExists);
pSortArray[pDirtyArray[nElement]] = rand() * 4.0f / RAND_MAX; //generate a bunch of random numbers in the range [0.0, 4.0)
}
printf("Starting sorts\n");
YourSort(pSortArray, nElements, pDirtyArray, nRandomElements);
SimpleStdVectorSort(pSortArray, nElements);
QSort(pSortArray, nElements);
delete []pDirtyArray;
delete []pSortArray;
return 0;
}
以上在我的计算机上的输出是:
The output of the above on my computer was:
Setting up. Please wait.
Starting sorts
Your sort took 63ms
std::vector sort took 154ms
qsort sort took 4ms
这些结果是在15,000个元素的数组上，其中有1,000个脏"元素随机分布在整个数据中.时间仅用于排序，不用于设置或预处理数据.
您应该使用不同大小和不同数量的脏元素的数组进行测试，这些数组将围绕您期望的算法常见情况.
另外，我不确定您的情况，如果您严重依赖标准库，那么qsort可能不是最佳选择.
令我惊讶的是，您的算法实际上比普通的std::vector排序要快得多，但是被qsort击败了16倍.
您可以考虑添加其他比较，例如二叉树或前面提到的红黑树.
These results were on an array of 15,000 elements with 1,000 "dirty" elements randomly spread throughout the data. The times were only for sorting only, not setting up or pre-processing the data.
You should test with arrays of different sizes and different numbers of dirty elements that would be around what you expect to be a common case for your algorithm.
Also, I''m not sure on your situation, if you are heavily relying on the standard library, then qsort may not be the best option.
To my amazement, your algorithm was actually much faster than the plain std::vector sort, however it was beaten by qsort by a factor of 16.
You may consider adding in other comparisons such as a Binary Tree, or the earlier mentioned Red-Black Tree.
在为std放弃std :: sort之前，您可能要尝试以下几件事: :: qsort ...
-不要将函数用作谓词，而应使用函子.在快速测试中，我使用了您的数据结构，发现使用谓词使函子加快了排序速度，使其在qsort上的时间为21/41.在结构定义中实现operator <时，我得到了相同的加速.将函数与std :: sort一起使用仍比qsort快38/41倍.
-不要将值传递给谓词.通过const引用传递.这打开了一个充满优化的整个独轮车，当编译器内联函子时，编译器可以为您提供优化.
-为您的结构实现交换方法.对于实现交换的对象，某些编译器的std :: sort重载，如果您有点狡猾，可以删除副本.但是，它们通常对POD执行相同的操作，因此您可能一无所获-值得一试.
到目前为止，第一个是最重要的.可以使用函子的时候不要使用函数.即使编译器可以完成整个程序的编译，它们仍然经常无法通过函数指针优化调用-这是双重的，因此从库代码中调用函数指针时会出现这种情况.
干杯，
灰
A couple of things you might like to try before abandoning std::sort for std::qsort...
- Don''t use a function as the predicate, use a functor. In a quick test I knocked up using your data structure I found that making the predicate a functor sped up the sort so it completed in 21/41 of the time over qsort. I got the same speedup implementingoperator <in the structure definition. Using a function with std::sort still completed 38/41 times faster than qsort.
- Don''t pass by value to the predicate. Pass by const reference. This opens up a whole wheelbarrow full of optimisations the compiler can give you when it inlines the functor.
- Implement a swap method for your structure. Some compilers have an overload of std::sort for objects that implement swap, which if you''re a bit cunning can remove a copy. However they usually do the same thing for PODs so you might not get anything - it could be worth a try though.
The first one is by far the most important. Don''t use functions when you can use functors. Even when compilers can do whole program compilation they still often can''t optimise calls through function pointers - and this is doubly so when the function pointer is called from library code.
Cheers,
Ash
两种方法
1不要使用链表.使用某种排序树.经过一次处理后，对其进行排序.
2处理后，将边缘插入正确的位置以使其顺序整齐.
第二个似乎对您来说更容易实现.
处理时，您有一点指的是边缘.因此您可以将前言或后退.处理后，您可以计算是否将边缘前移或向后移动以按顺序排列列表.保存指向边的点，并向前或向后移动，以找到插入边并插入边的正确位置.
这样可以节省迭代整个列表以删除脏边缘并迭代插入的时间.
Two method
1 don''t use linked list. use some kind of sorting tree. Once after process make it sorted.
2 Once after process insert the edge in the right place to make it in order.
the second seem more easy for you to implemented.
When process you have a point refer to the edge. so you can move foreword or backward. After processing, you can calculate whether move the edge foreword or backward to make the list in order. save the point refer to the edge and move foreword or backward to find the correct place to insert the edge and insert it.
this will save the time for iterating the whole list to delete the dirty edge and iterating to insert.
这篇关于排序优化-需要高级策略的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
