我一直在使用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的最后部分没有粗化步骤,则函数调用会提高大部分性能。粗化步骤将必须通过更简单的排序,插入排序或排序网络来完成。

除非您有足够大的排序空间,否则实际时间可能会淹没测量不确定性的过程。

10-06 02:05