Сортировать по темам

Question

У меня есть задание, и мне нужен рабочий код. Прежде чем начать, я хочу понять проблему, но я не могу понять, как ее написать.

У меня есть массив данных, возьмите это, например

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

Мне нужно разделить этот массив пополам, бросить его в пул потоков и сделать это рекурсивно, пока я не имею < = 2 элементов. Если у меня есть 2 элемента, мне нужно проверить, что меньше, и поместить их на левую сторону, а затем вернуть массив.

Что я не понимаю, так я могу объединить массив? я полагаю, чтобы разделить массив, выбросить поток в пул и заблокировать его до готовности? Как получить результаты потока? Я собираюсь предположить, что невозможно объединить массивы без блокировки?

Heres, что я до сих пор.

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; 
    } 

Примечание: Профессор сказал, что мы можем попросить других о помощи. Я думаю, я могу решить это, не спрашивая, но я хочу получить лучший ответ. Threading - моя слабость (я не все остальное, db, binary io, веб-интерфейс, просто никогда сложные потоки)

Answer 1

Это похоже на параллельную версию merge sort. Вы должны сделать так, чтобы он работал как рекурсивная последовательная версия, но, по-видимому, выполнял каждый рекурсивный вид как отдельную задачу.

В вашем API-интерфейсе задач должен быть какой-то способ дождаться завершения и, возможно, также передать результаты. При этом вы можете скопировать традиционную систему слияния довольно хорошо: для каждого вспомогательного сортирования поместите задачу в пул и дождитесь завершения двух подзадач. Затем выполните слияние и верните свой собственный результат к вашей задаче вызова.

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

Answer 2

Чтобы добавить ответ Мартина, я бы не создал меньшие копии массива. Вместо этого я бы каждый поток работал над подмножеством исходного массива.

Answer 3

Более счастлив обязать: Any multi-core sorting implementation in .NET?