0

我有一个非常简单的问题，我只是无法在网上找到答案。我做了一个合并排序功能（我肯定效率低下），但我在这里询问线程。我正在使用 Windows 的 CreateThread 函数来生成线程来对给定数组的间隔进行排序。完成所有线程后，我会将这些段合并在一起以获得最终结果。我还没有实现最终的合并，因为我得到了奇怪的错误，我确定这是线程中的一个愚蠢的错误。如果您可以查看 paraMSort，我将发布我的代码。我将发布整个 MergeSort.h 文件，以便您也可以查看辅助函数。有时代码会完美地编译和运行。有时控制台会突然关闭而没有错误/异常。不应该存在互斥锁问题，因为我在数组的不同段上进行操作（完全不同的内存位置）。有人看出什么不对了吗？非常感谢。

PS。是 Windows CreateThread 的内核级别吗？换句话说，如果我在双核计算机上创建 2 个线程，它们可以同时在不同的内核上运行吗？我想是的，因为在这台计算机上，我可以用 2 个线程在 1/2 的时间内完成相同的工作（使用另一个测试示例）。

聚苯乙烯。我还看到了一些使用 Boost.Thread 解决的并行性答案。我应该只使用 boost 线程而不是 windows 线程吗？我没有使用 Boost 的经验。 

#include "Windows.h"
#include <iostream>
using namespace std;

void insert_sort(int* A, int sA, int eA, int* B, int sB, int eB)
{
   int value;
   int iterator;

   for(int i = sA + 1; i < eA; i++)
   {
       value = A[i]; // Grab the next value in the array
       iterator = i - 1; 
       // Move this value left up the list until its in the right spot
       while(iterator >= sA && value < A[iterator])
          A[iterator + 1] = A[iterator--];
       A[iterator + 1] = value; // Put value in its correct spot
   }
   for(int i = sA; i < eB; i++) 
   {
       B[i] = A[i]; // Put results in B
   }
}

void merge_func(int* a, int sa, int ea, int* b, int sb, int eb, int* c, int sc)
{
    int i = sa, j = sb, k = sc;

    while(i < ea && j < eb)
       c[k++] = a[i] < b[j] ? a[i++] : b[j++];
    while(i < ea)
      c[k++] = a[i++];
    while(j < eb)
      c[k++] = b[j++];
}

void msort_big(int* a, int* b, int s, int e, bool inA)
{
    if(e-s < 4)
    {
        insert_sort(a, s, e, b, s, e); 
        return; // We sorted (A,s,e) into (B,s,e). 
    }
    int m = (s + e)/2;
    msort_big(a, b, s, m, !inA);
    msort_big(a, b, m, e, !inA);

    // If we want to merge in A, do it. Otherwise, merge in B
    inA ? merge_func(b, s, m, b, m, e, a, s) :  merge_func(a, s, m, a, m, e, b, s);
}

void msort(int* toBeSorted, int s, int e)
// Sorts toBeSorted from [s, e+1), so just enter [s, e] and
//   the call to msort_big adds one. 
{
    int* b = new int[e - s + 1];
    msort_big(toBeSorted, b, s, e+1, true);
    delete [] b;
}

template <class T>
struct SortData_Send
{
   T* data;
   int start;
   int end;
};

DWORD WINAPI msort_para_callback(LPVOID lpParam)
{
   SortData_Send<int> dat = *(SortData_Send<int>*)lpParam;
   msort(dat.data, dat.start, dat.end);
   cout << "done! " << endl;
}

int ceiling_func(double num)
{
   int temp = (int)num;

   if(num > (double)temp)
   {
      return temp + 1;
   }
   else
   {
       return temp;
   }
}

void paraMSort(int* toBeSorted, int s, int e, int numThreads)
{
   HANDLE threads[numThreads];
   DWORD threadIDs[numThreads];
   SortData_Send<int>* sent[numThreads];

   for(int i = 0; i < numThreads; i++)
   {
      // So for each thread, make an interval and pass the pointer to the array of ints.
      //   So for numThreads = 3 and array size of 0 to 99 (100), we have 0-32, 33-65, 66-100. 
      //   100 because sort function takes [start, end). 
      sent[i] = new SortData_Send<int>;
      sent[i]->data = toBeSorted;
      sent[i]->start = s + ceiling_func(double(i)*(double)e/double(numThreads));
      sent[i]->end = ceiling_func(double(i+1)*double(e)/double(numThreads)) + ((i == numThreads-1) ? 1 : -1);
      threads[i] = CreateThread(NULL, 0, msort_para_callback, sent[i], 0, &threadIDs[i]);
   }
   WaitForMultipleObjects(numThreads, threads, true, INFINITE);
   cout << "Done waiting!" <<endl;

}
4

1 回答 1

0

假设's'是你的起点，'e'是你线程的终点不应该你的代码是这样的

sent[i]->start = s + ceiling_func(double(i)*(double)(e-s)/double(numThreads));
sent[i]->end = (i == numThreads-1) ? e : (s - 1 + ceiling_func(double(i+1)*(double)(e-s)/double(numThreads)));

这是为了以防您的函数void paraMSort(int* toBeSorted, int s, int e, int numThreads)被调用的 's' 值不等于 0？这可能会导致您读取错误的内存部分。

于 2012-06-13T16:56:34.060 回答