单链表的并行排序

Question

有什么算法让它成为一个链表的并行排序值得吗？

众所周知，合并排序是用于排序链表的最佳算法。

大多数合并排序都是根据数组来解释的，每一半都是递归排序的。这将使并行化变得微不足道：对每一半独立排序，然后合并两半。

但是链表没有“中途”点；链表一直持续到结束：

头→[a]→[b]→[c]→[d]→[e]→[f]→[g]→[h]→[i]→[j]→…

我现在使用的实现遍历列表一次以获取计数，然后递归地拆分计数，直到我们将节点与它的NextNode进行比较。递归负责记住两半在哪里。

这意味着链表的MergeSort在列表中线性进展。因为它似乎要求在列表中线性进展，所以我认为它不能并行化。我能想象的唯一方法是：

• 浏览列表以获得计数O（n）
• 沿着列表的一半走到中间点O（n/2）
• 然后对每一半进行排序O（n log n）

但是，即使我们在单独的线程中并行化排序(a，b)和(c，d ),我认为在< code>NextNode重新排序期间的错误共享会扼杀并行化的任何优点。

有没有排序链表的并行算法？

下面是对数组执行合并排序的标准算法:

algorithm Merge-Sort
    input:
        an array, A (the values to be sorted)
        an integer, p (the lower bound of the values to be sorted)
        an integer, r (the upper bound of the values to be sorted)

    define variables:
        an integer, q (the midpoint of the values to be sorted)

    q ← ⌊(p+r)/2⌋
    Merge-Sort(A, p, q)   //sort the lower half
    Merge-Sort(A, q+1, r) //sort the upper half   
    Merge(A, p, q, r)     

此算法是为具有任意索引访问的数组设计的。要使其适合于链接列表，必须对其进行修改。

这是（单线程）单链表，合并排序，我目前用于对单链表进行排序的算法。它来自贡内特·巴埃萨·耶茨算法手册

algorithm sort:
    input:
        a reference to a list, r (pointer to the first item in the linked list)
        an integer, n (the number of items to be sorted)
    output:
        a reference to a list (pointer to the sorted list)

    define variables:
        a reference to a list, A (pointer to the sorted top half of the list)
        a reference to a list, B (pointer to the sorted bottom half of the list)
        a reference to a list, temp (temporary variable used to swap)

    if r = nil then
        return nil

    if n > 1 then
        A ← sort(r, ⌊n/2⌋ )
        B ← sort(r, ⌊(n+1)/2⌋ )
        return merge( A, B )

    temp ← r
    r ← r.next
    temp.next ← nil
    return temp

Pascal实现将是：

function MergeSort(var r: list; n: integer): list;
begin
   if r = nil then 
       Result := nil
   else if n > 1 then
      Result := Merge(MergeSort(r, n div 2), MergeSort(r, (n+1) div 2) )
   else
   begin
      Result := r;
      r := r.next;
      Result.next := nil;
   end
end;

如果我的代码转换工作正常，这里有一个动态C#翻译:

list function MergeSort(ref list r, Int32 n)
{
   if (r == null)
      return null;

    if (n > 1)
    {
       list A = MergeSort(r, n / 2);
       list B = MergeSort(r, (n+1) / 2);
       return Merge(A, B);
    }
    else
    {
       list temp = r;
       r = r.next;
       temp.next = null;
       return temp;
    }
}

我现在需要的是一个并行算法来排序链表。不一定是合并排序。

一些人建议复制接下来的n个项目，其中n个项目适合于单个高速缓存行，并且用这些项目产生一个任务。

algorithm GenerateSampleData
    input:
        an integer, n (the number of items to generate in the linked list)
    output:
        a reference to a node (the head of the linked list of random data to be sorted)

    define variables:
        a reference to a node, head (the returned head)
        a reference to a node, item (an item in the linked list)
        an integer, i (a counter)

    head ← new node
    item ← head        

    for i ← 1 to n do
        item.value ← Random()
        item.next ← new node
        item ← item.next

    return head

因此，我们可以通过调用以下命令生成一个包含300000个随机项目的列表：

head := GenerateSampleData(300000);

Time to generate 300,000 items    568 ms

MergeSort 
    count splitting variation   3,888 ms (baseline)

MergeSort
    Slow-Fast midpoint finding  3,920 ms (0.8% slower)

QuickSort
    Copy linked list to array       4 ms
    Quicksort array             5,609 ms
    Relink list                     5 ms
    Total                       5,625 ms (44% slower)

< li>Stackoverflow:对链表排序最快的算法是什么？ < li>Stackoverflow:合并排序链接列表 < li >链接列表的合并排序 < li >并行合并排序< code>O(log n) pdf，1986 < li>Stackoverflow:并行合并排序(封闭的，典型的书呆子风格) < li >并行合并排序Dobbs博士，2012年3月24日 < li >消除虚假分享Dobbs博士，2009年3月14日

Answer 1

有两种方法可以进行合并排序。首先将列表分成两半，然后对这两部分递归地应用合并排序并合并结果。但是还有另一种方法。你可以将列表分割成对，然后递归地合并成对，直到得到一个列表。参见数据实现的例子。ghc haskell中的List.sort。通过在开始时为一些适当数量的对生成进程(或线程),然后合并它们的结果直到有一个，可以使该算法并行。

Answer 2

合并排序是一种分而治之的算法。

数组擅长在中间划分。

链表在中间划分效率低下，所以让我们在浏览列表时划分它们。

Take the first  element and put it in list 1.
Take the second element and put it in list 2.
Take the third  element and put it in list 1.
...

现在，您已经将列表有效地分成了两半，通过自下而上的合并排序，您可以在浏览第一个列表时开始合并步骤，并将其分成赔率和赔率。

Answer 3

Mergesort非常适合并行排序。将列表分成两半，并对每一半进行并行排序，然后合并结果。如果您需要两个以上的并行排序过程，请递归执行。如果您碰巧没有无限多的CPU，您可以省略一定深度的并行化（您必须通过测试来确定）。

顺便说一句，将列表分成大小大致相同的两半的通常方法是弗洛伊德循环查找算法，也称为兔子和乌龟方法：

Node MergeSort(Node head)
{
   if ((head == null) || (head.Next == null))
      return head; //Oops, don't return null; what if only head.Next was null

   Node firstHalf = head;
   Node middle = GetMiddle(head);
   Node secondHalf = middle.Next;
   middle.Next = null; //cut the two halves

   //Sort the lower and upper halves
   firstHalf = MergeSort(firstHalf);
   secondHalf = MergeSort(secondHalf);

   //Merge the sorted halves 
   return Merge(firstHalf, secondHalf);
}

Node GetMiddle(Node head)
{
   if (head == null || head.Next == null)
       return null;

   Node slow = head;
   Node fast = head;
   while ((fast.Next != null) && (fast.Next.Next != null))
   {
       slow = slow.Next;
       fast = fast.Next.Next;
   }
   return slow;
}

之后，list和list2