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が原因だと思います。最初のノードが削除されたときに、2番目のノードの前のノードポインタが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

これは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 に答える
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 に答える