调试归并 [英] Debugging mergesort

问题描述

我需要排序双向链表。根据全能维基百科，归并是去的方式。

I need to sort a doubly-linked list. According to the almighty wikipedia, mergesort is the way to go for that.

递归算法工作得相当好，但我正在写一个通用的实现，性能可能是一个问题。

The recursive algorithm works reasonably well, but as I'm writing a general-purpose implementation, performance might be an issue.

移植数组迭代版本将杀死性能重新扫描列表中把它分成子列表缓慢;对于任何有兴趣 - 这里的code：

Porting the iterative version for arrays will kill performance as rescanning the list to divide it into sublists is slow; for anyone interested - here's the code:

static void sort(struct linked_list *list,
    int (*cmp)(const void *, const void *))
{
    size_t slice_size = 1;
    for(; slice_size < list->size; slice_size *= 2)
    {
        struct node *tail = list->first;
        while(tail)
        {
            struct node *head = tail;

            size_t count = slice_size;
            while(tail && count--) // performance killer
                tail = tail->next;

            count = slice_size;
            while(head != tail && tail && count)
            {
                if(cmp(head->data, tail->data) <= 0)
                    head = head->next;
                else
                {
                    struct node *node = tail;
                    tail = tail->next;
                    remove_node(node, list);
                    insert_before(node, list, head);
                    --count;
                }
            }

            while(tail && count--) // performance killer
                tail = tail->next;
        }
    }
}

但有使用基于堆栈的方法的另一个版本迭代：

But there's another iterative version using a stack-based approach:

struct slice
{
    struct node *head;
    size_t size;
};

static void sort(struct linked_list *list,
    int (*cmp)(const void *, const void *))
{
    if(list->size < 2) return;

    struct slice stack[32];
    size_t top = -1;
    struct node *current = list->first;

    for(; current; current = current->next)
    {
        stack[++top] = (struct slice){ current, 1 };
        for(; top && stack[top-1].size <= stack[top].size; --top)
            merge_down(list, cmp, stack + top);
    }

    for(; top; --top)
        merge_down(list, cmp, stack + top);
}

这将推动大小1列出入堆栈，只要顶端列表比其predecessor大于或等于大小的合并向下

This will push size 1 lists onto the stack and merges down as long as the top list is of greater or equal size than its predecessor.

不幸的是，有一个错误的地方，作为一些输入列表， merge_down（）将无法进行仔细的检查：

Unfortunately, there's a bug somewhere as for some input lists, merge_down() will fail a sanity check:

static void merge_down(struct linked_list *list,
    int (*cmp)(const void *, const void *), struct slice *top)
{
    struct node *right = top->head;
    size_t count = top->size;

    --top;

    struct node *left = top->head;
    top->size += count;

{
    // sanity check: count nodes in right list
    int i = count;
    struct node *node = right;
    for(; i--; node = node->next) if(!node)
    {
        puts("too few right nodes");
        exit(0);
    }
}

    // determine merged list's head
    if(cmp(left->data, right->data) <= 0)
    {
        top->head = left;
        left = left->next;
    }
    else
    {
        top->head = right;
        struct node *node = right;
        right = right->next;
        remove_node(node, list);
        insert_before(node, list, left);
        --count;
    }

    while(left != right && count)
    {
        if(cmp(left->data, right->data) <= 0)
            left = left->next;
        else
        {
            struct node *node = right;
            right = right->next;
            remove_node(node, list);
            insert_before(node, list, left);
            --count;
        }
    }
}

链表实现可能是相关的，以及：

The linked list implementation might be relevant as well:

struct node
{
    struct node *prev;
    struct node *next;
    long long data[]; // use `long long` for alignment
};

struct linked_list
{
    struct _list _list; // ignore
    size_t size;
    struct node *first;
    struct node *last;
};

static void insert_before(struct node *node, struct linked_list *list,
    struct node *ref_node)
{
    if(ref_node)
    {
        node->next = ref_node;
        node->prev = ref_node->prev;
        if(ref_node->prev) ref_node->prev->next = node;
        else list->first = node;
        ref_node->prev = node;
    }
    else // empty list
    {
        node->next = NULL;
        node->prev = NULL;
        list->first = node;
        list->last = node;
    }
    ++list->size;
}

static void remove_node(struct node *node, struct linked_list *list)
{
    if(node->prev) node->prev->next = node->next;
    else list->first = node->next;
    if(node->next) node->next->prev = node->prev;
    else list->last = node->prev;
    --list->size;
}

我是什么在这里失踪？

What am I missing here?

推荐答案

我找到了自己的错误：

for(; current; current = current->next)
{
    stack[++top] = (struct slice){ current, 1 };
    for(; top && stack[top-1].size <= stack[top].size; --top)
        merge_down(list, cmp, stack + top);
}

下面的下一个值电流被确定的在调用 merge_down（），这可能会左右移动节点，即电流 - ＆gt;接着将不再指向正确的节点

Here, the next value of current gets determined after the call to merge_down(), which might move the node around, ie current->next will no longer point to the correct node.

花事解决了这个问题：

while(current)
{
    stack[++top] = (struct slice){ current, 1 };
    current = current->next;
    for(; top && stack[top-1].size <= stack[top].size; --top)
        merge_down(list, cmp, stack + top);
}

由于PMG的努力：我增加了一些票为

Thanks to pmg for the effort: I added some votes for that.

这篇关于调试归并的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！