performance - 单链表的并行排序

Question

是否有任何算法可以使链表的并行排序值得？

众所周知Merge Sort是用于对 linked list 进行排序的最佳算法.

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

但是链表没有“中途”点；一个链表一直到它结束:

Head → [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)，我认为 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)     

该算法是为具有任意索引访问的数组设计的，也意味着它。为了使其适用于链表，必须对其进行修改。

链表合并排序算法

这是(单线程)单链表，归并排序，我目前用来对单链表进行排序的算法。它来自 Gonnet + Baeza Yates Handbook of Algorithms

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

A Pascal implementation会是:

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

因此我们可以通过调用生成一个包含 300,000 个随机项目的列表:

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)

红利阅读

• 计算器:What's the fastest algorithm for sorting a linked list?
• 计算器:Merge Sort a Linked List
• Mergesort For Linked Lists
• Parallel Merge Sort O(log n) pdf, 1986
• 计算器:Parallel Merge Sort (关闭，以典型的 SO nerd-rage 方式)
• Parallel Merge Sort 博士多布斯，2012 年 3 月 24 日
• Eliminate False Sharing 博士多布斯，2009 年 3 月 14 日
• Mergesort For Linked Lists , Simon Tatham(因 Putty 而出名)

Answer 1

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

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

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 是两个大小大致相同的列表。连接它们将产生原始列表。当然，fast = fast->next->next需要进一步注意；这只是为了演示一般原则。