按线程排序 [英] Sort with threads

问题描述

我有一个作业，我需要工作代码.在我开始之前，我想了解这个问题，但是我不知道该怎么写.

I have an assignment and i need working code. Before i start i want to understand the problem but i cant figure out how to write it.

我有一个数据数组，以这个为例

I have an array of data, take this for example

var arr = new byte[] {5,3,1,7,8,5,3,2,6,7,9,3,2,4,2,1}

我需要将此数组拆分成两半，将其放入线程池中，然后递归执行，直到我有< = 2个元素.如果我有2个元素，则需要检查哪个元素更少，然后将其放在左侧，然后返回数组.

I need to split this array in half, throw it into a thread pool and do that recursively until i have <=2 elements. If i have 2 elements i need to check which is less and put it on the left side then return the array.

我不了解的是如何合并阵列?我是否应该拆分数组，将线程扔到池中并阻塞直到准备好?我如何获得线程的结果?我要假设它不可能在不阻塞的情况下合并数组?

What i don't understand is how do i merge the array? am i suppose to split the array, throw a thread into the pool and block until its ready? How do i get the results of the thread? I'm going to assume its not possible to merge the arrays without blocking?

这是我到目前为止所拥有的.

Heres what i have so far.

    static void Main(string[] args)
    {
        var arr = new byte[] { 5, 3, 1, 7, 8, 5, 3, 2, 6, 7, 9, 3, 2, 4, 2, 1 };
        var newarr = Sort(arr);
        Console.Write(BitConverter.ToString(newarr));
    }
    static byte[] Sort(byte[] arr)
    {
        if (arr.Length <= 2)
            return arr;
        if (arr.Length == 2)
        {
            if (arr[0] > arr[1])
            {
                var t = arr[0];
                arr[0] = arr[1];
                arr[1] = t;
            }
            return arr;
        }

        var arr1 = arr.Take(arr.Length / 2).ToArray();
        var arr2 = arr.Skip(arr1.Count()).ToArray();
        //??
        return arr;
    }

注意:教授确实说过我们可以向其他人寻求帮助.我想我可以不问而解决，但我想得到最好的答案.线程是我的弱点(我不做其他事情，数据库，二进制io，Web界面，永远不要复杂的线程)

Note: The prof did say we can ask others for help. I think i can solve this without asking but i want to get the best answer. Threading is my weakness (i dont everything else, db, binary io, web interface, just never complex threads)

推荐答案

这似乎是的并行版本合并排序.您应该使它像递归顺序版本一样工作，但是显然将每个递归排序作为单独的任务运行.

This appears to be a parallel version of merge sort. You should essential make it work like the recursive sequential version, but apparently run each recursive sort as a separate task.

在任务API中，应该有某种方法等待完成，甚至还可以传递结果.这样，您就可以很好地复制传统的mergesort:对于每个子分类，将一个任务放入池中，然后等待两个子任务的完成.然后执行合并，并将您自己的结果传递回给您的呼叫任务.

In your task API, there should be some way to wait for completion, and perhaps to also pass results. With that, you can copy the traditional mergesort fairly well: for each sub-sort, put a task into the pool, and wait for completion of the two subtasks. Then perform the merge, and pass back your own result to your calling tasking.

如果仅具有常规线程API(即没有真正的任务库)，则建议您在第三个数组中提供输出:每个线程将具有两个输入数组和一个输出数组.如果允许为每个任务创建新线程，则可以通过加入两个子线程来等待任务完成.

If you have a regular thread API only (i.e. no real task library), then I suggest you provide the output in a third array: each thread will have two input arrays, and one output array. If you are allowed to create fresh threads for each task, you can wait for task completion by joining the two subthreads.

这篇关于按线程排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！