Объединить сортировку с четырьмя потоками в C#?

Question

Я хочу написать программу сортировки слияния в C# с четырьмя потоками. В этой программе каждый поток имеет некоторые числа, которые сортируются в их потоках. Я объясню их примером: в первом потоке есть 100 номеров. Этот поток сортирует эти числа с сортировкой слияния, а затем передает их во второй поток. Второй поток, сам имеет 100 номеров и сортирует их числа с номерами, которые были переданы из первого потока. Опять же после сортировки данных во втором потоке все 200 номеров переходят к третьему потоку, чтобы отсортировать эти числа с номерами третьего потока и, наконец, все числа в четвертом потоке, сортируются с номерами четвертого потока, и результат показан. Я знаю, что в этом случае простой последовательный метод сортировки, вероятно, быстрее, чем сортировка слияния, но я должен сделать сортировку таким образом для моего школьного проекта, а также эти 100 номеров для каждого потока были только примером, и в моем проекте каждый поток имеет более 100 номера. Я хочу сортировать числа с сортировкой слияния с четырьмя потоками. У меня особенно проблема передачи чисел между потоками. Я новичок в C#, и если это возможно, пожалуйста, помогите мне с кодом. Благодарю.

Answer 1

Из сценария, который вы объяснили, это похоже на последовательный процесс. Один поток ждет результата другой нити.

Но я думаю, что если вы действительно хотите сортировать, предположите 100 чисел, используя 4 потока, затем передайте 25 номеров каждому потоку и вызовите сортировку слияния в каждом потоке. Когда каждый поток выполняется сортировкой, в конце 1-й итерации у вас есть 4 отсортированных массива. Теперь передайте 2 отсортированных массива в каждый поток и вызовите MERGE слияния сортировки по каждой теме. (На этом этапе вы используете только 2 потока). Как только это слияние выполнено, вы остаетесь с двумя отсортированными массивами. Вы можете передать 2 отсортированных массива в любой поток и вызвать MERGE (не слияние сортировки).

Я думаю, что если вы google трудно, вы получите решение в Интернете. http://penguin.ewu.edu/~trolfe/ParallelMerge/ParallelMerge.html

Answer 2

Параллельный слияние не обязательно будет быстрее, чем простой последовательный метод сортировки. Только после того, как у вас будет большое количество элементов для сортировки (обычно это намного больше, чем подходит в кеш-памяти процессора 64 КБ, то есть десятки тысяч из 4 байтовых целых чисел), у вас есть выделенные ядра и они могут разбить данные по этим ядрам , вы начнете видеть какие-либо выгоды. Для небольших объемов данных параллельный подход будет на самом деле медленнее из-за необходимости дополнительной координации и распределения.

В C# есть встроенные методы для этого типа разбиения. PLINQ был создан специально для таких задач.

Существует несколько существующих статей/сообщений в блогах, в которых обсуждается решение параллельного сортирования слияния с использованием PLINQ, которое можно найти в googling «plinq merge sort».

Два, в частности, обеспечивают некоторые охвата глубины и включают в себя некоторые бенчмаркинг по сравнению с последовательной сортировки можно найти здесь:

http://blogs.msdn.com/b/pfxteam/archive/2011/06/07/10171827.aspx http://dzmitryhuba.blogspot.nl/2010/10/parallel-merge-sort.html