c - 在 Windows 中使用线程对 100 万个整数进行排序

Question

我有一个任务是使用 C 编程语言(在 Windows 平台)中使用 8 线程对 100 万个随机整数进行排序。

1. 我必须创建一个二进制文件，其中包含 100 万个随机整数。 (完成)
2. 我必须将这些整数缓冲到一个数组中。 (完成)
3. 我必须创建 8 个线程。 (完成)每个线程占用数组的 1/8 并对其进行排序(算法可以是合并或快速排序)。
4. 然后合并所有子数组以构造一个完全排序的数组。

Here's a detailed description for threads.

我正在 Visual Studio 2017 上编写代码，这是我的进度:

// 1MRandomNumber.cpp : Defines the entry point for the console application.
//    
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "windows.h"
#include "time.h"
#include <tchar.h>
#include <strsafe.h>

#define MAX_THREADS 8

static int numbers[1000000];

DWORD WINAPI QuickSort(LPVOID lpParam);

//Creating a File with 1000000 random integers;
void create1MBinaryFile(){
    int i, x;
    FILE *fp = fopen("1MRandomNumbers.dat","wb");
    srand(time(NULL));
    for (i = 0; i<1000000; i++) {
        x = (rand() * rand()) % 1000001;
        fprintf(fp,"%d \n", x);
    }
    fclose(fp);
    printf("File is created\n");
}

//Buffers integers to "numbers" Array;
void loadFiletoArray() {
    int i = 0;
    char buf[128];
    FILE *fp = fopen("1MRandomNumbers.dat", "rb");
    if (fp == NULL) {
        fprintf(stderr, "Error in opening file");
        exit(1);
    }

    for (int i = 0; i < 1000000 - 1; i++) {
        fgets(buf, sizeof(buf), fp);
        sscanf_s(buf, "%d", &numbers[i]);
    }
    fclose(fp);
    printf("Numbers loaded to an array\n");
}

//Creates 8 Threads
void threadCreate() {
    DWORD   dwThreadIdArray[MAX_THREADS];
    HANDLE  hThreadArray[MAX_THREADS];

    for (int i = 0; i<MAX_THREADS -1; i++)
    {
        hThreadArray[i] = CreateThread(
            NULL,          
            0,                    
            QuickSort,      
            NULL,         
            0,                     
            &dwThreadIdArray[i]);   
        printf("Thread %d created \n", dwThreadIdArray[i]);
    } 

    WaitForMultipleObjects(MAX_THREADS, hThreadArray, TRUE, INFINITE);

    for (int i = 0; i<MAX_THREADS; i++)
    {
        CloseHandle(hThreadArray[i]);
    }
}

int main(int argv, char *argc[])
{
    create1MBinaryFile();
    loadFiletoArray();
    threadCreate();

    return 0;
}

DWORD WINAPI QuickSort(LPVOID lpParam) {

    return 0;
}

那么如何在Windows平台上创建多线程呢？在我们的讲座中，我们已经学会了在 POSIX 库中做到这一点，但我想了解如何使用 Windows 线程来实现它。

编辑:我创建了 8 个线程。这是正确的方法还是我应该改变它？另外，如何为每个线程拆分数组并对它们进行快速排序？

Answer 1

代码看起来不错，只是它创建了 7 个线程 (MAX_THREADS-1)，然后等待 8 个线程。此外，代码应使用 lpParameter 作为指向结构的指针，该结构指定要由线程排序的数组的 1/8，该结构可以是一对指针(开始和结束指针)或索引。在启动线程之前，代码应将整个文件读入数组。

要将数组分成 8 部分，则每个 1/8 的大小 = array_size/8，最后 1/8 比其他部分大(最多大 7)。如果您想要更均匀的分割，请让 remainder = array_size % 8。然后第一个 remainder 线程的大小为 (array_size/8) + 1，其余线程的大小为 (array_size/8) + 1大小为 (array_size/8)。

可选 - 您可以使用线程进行合并。将线程0到7编号，然后线程6可以等待线程7退出，然后合并部分6和7。线程4可以等待线程5，合并部分4和5，然后等待线程6，并合并合并的4 ,5 和 6,7 等等。我不确定这会比单线程 8 路合并快得多。