0

我正在使用 linux,但多线程和单线程都需要 340 毫秒。有人可以告诉我我在做什么有什么问题吗?

这是我的代码

#include<time.h>
#include<fstream>
#define SIZE_OF_ARRAY 1000000
using namespace std;

struct parameter
{
        int *data;
        int left;
        int right;
};
void readData(int *data)
{
        fstream iFile("Data.txt");
        for(int i = 0; i < SIZE_OF_ARRAY; i++)
                iFile>>data[i];
}

int threadCount = 4;

int Partition(int *data, int left, int right)
{
        int i = left, j = right, temp;
        int pivot = data[(left + right) / 2];
        while(i <= j)
        {
                while(data[i] < pivot)
                        i++;
                while(data[j] > pivot)
                        j--;
                if(i <= j)
                {
                        temp = data[i];
                        data[i] = data[j];
                        data[j] = temp;
                        i++;
                        j--;
                }
        }
        return i;
}

void QuickSort(int *data, int left, int right)
{
        int index = Partition(data, left, right);
        if(left < index - 1)
                QuickSort(data, left, index - 1);
        if(index < right)
                QuickSort(data, index + 1, right);
}

//Multi threading code starts from here
void *Sort(void *param)
{
        parameter *param1 = (parameter *)param;
        QuickSort(param1->data, param1->left, param1->right);
        pthread_exit(NULL);
}

int main(int argc, char *argv[])
{
        clock_t start, diff;
        int *data = new int[SIZE_OF_ARRAY];
        pthread_t threadID, threadID1;
        pthread_attr_t attr;
        pthread_attr_init(&attr);
        pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
        pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
        parameter param, param1;
        readData(data);
        start = clock();
        int index = Partition(data, 0, SIZE_OF_ARRAY - 1);
        if(0 < index - 1)
        {
                param.data = data;
                param.left = 0;
                param.right = index - 1;
                pthread_create(&threadID, NULL, Sort, (void *)&param);
        }
        if(index < SIZE_OF_ARRAY - 1)
        {
                param1.data = data;
                param1.left = index + 1;
                param1.right = SIZE_OF_ARRAY;
                pthread_create(&threadID1, NULL, Sort, (void *)&param1);
        }
        pthread_attr_destroy(&attr);
        pthread_join(threadID, NULL);
        pthread_join(threadID1, NULL);
        diff = clock() - start;
        cout<<"Sorting Time = "<<diff * 1000 / CLOCKS_PER_SEC<<"\n";
        delete []data;
        return 0;
}
//Multithreading Ends here

Single thread main function
int main(int argc, char *argv[])
{
        clock_t start, diff;
        int *data = new int[SIZE_OF_ARRAY];
        readData(data);
        start = clock();
        QuickSort(data, 0, SIZE_OF_ARRAY - 1);
        diff = clock() - start;
        cout<<"Sorting Time = "<<diff * 1000 / CLOCKS_PER_SEC<<"\n";
        delete []data;
        return 0;
}
//Single thread code ends here
some of functions single thread and multi thread use same
4

3 回答 3

2

clock返回总 CPU 时间,而不是 wall 时间。

如果您有 2 个 CPU 和 2 个线程,那么在两个线程同时运行一秒钟后,clock将返回 2 秒的 CPU 时间(每个线程的 CPU 时间的总和)。

所以结果完全在意料之中。不管你有多少 CPU,所有 CPU 的总运行时间都是一样的。

于 2012-06-25T10:36:41.097 回答
1

请注意,您从主线程调用一次 Partition ...

该代码在同一个内存块上工作,当另一个 CPU 访问同一个内存块时,它会阻止 CPU 工作。除非您的数据真的很大,否则您可能会遇到很多此类点击。

最后,如果您的算法在使用一个线程运行时以内存速度运行,那么添加更多线程也无济于事。不久前我用图像数据进行了此类测试,并且拥有多个线程会降低总速度,因为该进程非常占用内存,以至于两个线程都在争夺内存……结果比根本没有线程还要糟糕。

今天真正快速的计算机真正快速运行的原因是每台计算机运行一个非常密集的进程,而不是在一台计算机上运行大量线程(或进程)。

于 2012-06-25T10:23:04.503 回答
1

构建一个带有 24 个线程的生产者-消费者队列的线程池。将您的数据分成两部分并向池发出合并排序任务对象,合并排序对象应向队列发出进一步的合并排序对并等待它们完成的信号,依此类推,直到合并排序对象发现它具有 [L1 缓存-大小数据]。然后该对象对其数据进行快速排序并向其父任务发出完成信号。

如果这在 24 核上不是很快,我将停止发布有关线程的帖子。

..它将并行处理多种排序。

..并且池可用于其他任务。

..并且没有破坏性能、产生死锁的join()、同步()(如果你除了PC队列,它只锁定足够长的时间来推送对象引用),没有线程创建开销和没有狡猾的线程停止/终止/销毁代码。就像理发师一样,没有等待——只要一个线程完成了一项任务,它就可以获得另一个任务。

没有线程微管理,没有调优,(你现在可以创建 64 个线程,为下一代盒子做好准备)。您可以使线程数可调 - 只需在运行时添加更多线程,或者通过排队毒丸来删除一些线程。

您根本不需要对线程的引用 - 只需将它们设置为关闭,(将队列作为参数传递)。

于 2012-06-25T12:56:21.047 回答