我一直在使用Mac OS gcc 4.2.1和Eclipse编写一个使用简单合并排序对数字进行排序的程序。我已经对排序进行了广泛的测试,我知道它可以工作,并且我认为,也许有点天真,因为算法将列表划分的方式不同,所以我可以只将线程排序一半,将主线程排序一半,然后这将花费一半的时间,但是不幸的是,它似乎没有用。
这是主要代码:
float x = clock(); //timing
int half = (int)size/2; // size is the length of the list
status = pthread_create(thready,NULL,voidSort,(void *)datay); //start the thread sorting
sortStep(testArray,tempList,half,0,half); //sort using the main thread
int join = pthread_join(*thready,&someptr); //wait for the thread to finish
mergeStep(testArray,tempList,0,half,half-1); //merge the two sublists
if (status != 0) { std::cout << "Could not create thread.\nError: " << status << "\n"; }
if (join != 0) { std::cout << "Could not create thread.\nError: " << status << "\n"; }
float y = clock() - x; //timing
sortStep
是主要的排序功能,mergeStep
用于合并一个数组中的两个子列表(它使用占位符数组来切换数字),而voidSort
是我用来传递包含所有线程的sortStep
参数。我觉得主线程可能正在等待新线程完成,但是我不确定如何克服这个问题。非常感谢您提供的所有帮助,非常感谢!编辑:
这是合并步骤
void mergeStep (int *array,int *tempList,int start, int lengthOne, int lengthTwo) //the merge step of a merge sort
{
int i = start;
int j = i+lengthOne;
int k = 0; // index for the entire templist
while (k < lengthOne+lengthTwo) // a C++ while loop
{
if (i - start == lengthOne)
{ //list one exhausted
for (int n = 0; n+j < lengthTwo+lengthOne+start;n++ ) //add the rest
{
tempList[k++] = array[j+n];
}
break;
}
if (j-(lengthOne+lengthTwo)-start == 0)
{//list two exhausted
for (int n = i; n < start+lengthOne;n++ ) //add the rest
{
tempList[k++] = array[n];
}
break;
}
if (array[i] > array[j]) // figure out which variable should go first
{
tempList[k] = array[j++];
}
else
{
tempList[k] = array[i++];
}
k++;
}
for (int s = 0; s < lengthOne+lengthTwo;s++) // add the templist into the original
{
array[start+s] = tempList[s];
}
}
-将
最佳答案
创建线程的开销非常大,因此除非您有大量(待确定)数据来排序,否则最好不要在主线程中对其进行排序。mergeStep
也计入代码中无法堆垛的部分,请记住Amdahl's law。
如果在8-16个元素以下时,sortStep的最后部分没有粗化步骤,则函数调用会提高大部分性能。粗化步骤将必须通过更简单的排序,插入排序或排序网络来完成。
除非您有足够大的排序空间,否则实际时间可能会淹没测量不确定性的过程。