0

我编写了以下代码，但它没有给出正确的结果（例如，如果您输入 [-1,-1]，它会返回 [-1,-1,-1]。

import std.stdio, std.range, std.container, std.algorithm;

DList!T strandSort(T)(DList!T list) {
    static DList!T merge(DList!T left, DList!T right) {
        DList!T res;
        while (!left.empty && !right.empty) {
            if (left.front <= right.front) {
                res.insertBack(left.front);
                left.removeFront();
            } else {
                res.insertBack(right.front);
                right.removeFront();
            }
        }
        res.insertBack(left[]);
        res.insertBack(right[]);
        return res;
    }

    DList!T result, sorted;

    while (!list.empty) {
        sorted.clear();
        sorted.insertBack(list.front);
        list.removeFront();
        foreach (item; list) {
            if (sorted.back <= item) {
                sorted.insertBack(item);
                list.stableLinearRemove(list[].find(item).take(1)));
            }
        }
        result = merge(sorted, result);
    }

    return result;
}

void main() {
    auto lst = DList!int([-1,-1]);
    foreach (e; strandSort(lst))
        writef("%d ", e);
}

有时，stableLinearRemove 不会从列表中删除该项目。问题是，这是我的代码中的错误，还是 Phobos 中的错误？

另见Rosettacode.org上的讨论

编辑：我怀疑它是由 removeFront 引起的。当删除第一个节点时，它不会将第二个节点的 prev 节点指针设置为 null。当被linearRemove从列表中移除的项目恰好是第一个节点时，它不会被移除。删除功能检查“之前”和“之后”节点，“之前”仍然设置。如果我这样写，它确实有效：

if (sorted.back <= item) {
    sorted.insertBack(item);
    if (list.front == item)
        list.removeFront();
    else 
        list.stableLinearRemove(list[].find(item).take(1)));
}
4

2 回答 2

0

你是对的，这绝对是 removeFront 中的一个错误。

尽管我可能会指出，即使它应该是有效的，通过 foreach 删除迭代元素也不会有效。你需要一个范围的句柄。考虑：

auto rng = list[];
while(!rng.empty) {
    auto item = rng.front;
    if(sorted.back <= item) {
        sorted.insertBack(item);
        auto rng2 = rng.save();
        rng.popFront();
        list.stableLinearRemove(rng2.take(1)); // O(1) removal!
    }else{
        rng.popFront();
    }
}

呃，好吧。鉴于该错误，以上可能不起作用。

于 2012-08-26T04:03:37.930 回答
0

我认为这不是 Phobos 中的错误，而是一个陷阱。如果它可能是列表中的第一个元素，则不应依赖 linearRemove 来删除它。首先检查并使用 removeFront。也更有效率。

在上述情况下，更好的解决方案是复制列表：

DList!T result, sorted, leftover;

while (!list.empty) {
    leftover.clear();
    sorted.clear();
    sorted.insertBack(list.front);
    list.removeFront();
    foreach (item; list) {
        if (sorted.back <= item)
            sorted.insertBack(item);
        else
            leftover.insertBack(item);
    }
    result = merge(sorted, result);
    list = leftover;
}
于 2012-08-08T16:02:50.587 回答