0

現在、D プログラミング言語を学習しようとしています。

付属のサンプルで実行すると OutOfMemoryError を返す、この小さなクイックソート アルゴを作成しました。

import std.stdio;
import std.algorithm;

int[] qs(int[] ary) 
{
    if(ary.length <= 1)
    {
        return ary;
    }

    int pivot_pos   = 0;
    int pivot       = ary[pivot_pos];

    for(int i = 0; i < ary.length; i++) 
    {
        if(ary[i] < pivot) 
        {
            ary = ary.remove(i) ~ ary;
            pivot_pos++;
        }
        else 
        {
            ary ~= ary.remove(i);
            if(i < pivot_pos)
                pivot_pos--;
        }
    }

    return qs(ary[0..pivot_pos]) ~ qs(ary[(pivot_pos+1)..ary.length]);
}

int main() 
{

    int[] ary = [ 2, 1, 4, 1, 6, 78, 3, 5, 10, 129, 234, 3, 5 ];

    ary = qs(ary);

    foreach(int element; ary) 
    {
        printf("%d ", element);
    }

    return 0;
}

これを解決する方法やアルゴリズムの何が問題なのかヒントはありますか? Dを学ぶ方法と私が気にかけなければならないことはありますか?

4

1 に答える 1

5

連結を使用しています。これにより、毎回新しい配列が割り当てられます（割り当てられないのは、配列を超えて未割り当てのメモリがある場合のみです）。配列を分割する方法は、GCがそれらすべてをスイープできないほどの十分な部分への参照を保持します

スワップを使用する必要があります：

auto tmp=ary;
while(tmp.length) 
{
    if(tmp[0]==pivot)break;//assumes unique
    if(tmp[0]<pivot) 
    {
        tmp=tmp[1..$];
        pivot_pos++;
    }
    else 
    {
        swap(tmp[0],tmp[$-1]);
        tmp=tmp[0..$-1];
    }
}

または、std.algorithm.partitionを使用して、そのソースをここで見つけることができます

于 2013-04-27T19:37:24.230 に答える