0

私のクラスで、先生は 10000 の配列で動作する C でクイックソート アルゴリズムを書くように私たちに求めましたint。私の友人と私は、疑似コードで見られるようにコードを書きました。

ランダムな値の配列をソートするときは問題なく動作しますが、ソートされた配列コードをソートするとクラッシュします。

Unhandled exception at 0x00FF2509 in ConsoleApplication1.exe: 0xC0000005: Access violation writing location 0x00330F58.

少し調べてみたところ、リンカが再帰関数用に 1MB のスタックを提供することがわかりました (ただし、間違っている可能性があります)。したがって、4 バイトの整数変数 (並べ替えられた配列が再度並べ替えられると 4x10k になります) と 10k の int 参照配列では、すべて約 200KB のスタックが必要になります。

そのため、このエラーが発生する理由がわかりませんでした。先生は、そのコードを疑似コードとして書くことは (もちろん) 可能であると教えてくれました。だから、コードで何か間違ったことをしている、そうでなければ私にはわかりません。

誰が何が間違っているのか説明してもらえますか?

void quicksort_last(int *A,int p,int r){

if(p<r){
    int q=partition(A,p,r);
    quicksort_last(A,p,q-1);
    quicksort_last(A,q+1,r);
}
}

int partition(int *A,int p, int r){
const int x=A[r];
int i=p-1;
int j=p;
int temp;

while(j<r){
    if(A[j]<=x){
        i++;
        temp=A[i];
        A[i]=A[j];
        A[j]=temp;
    }
    j++;
}
temp=A[i+1];
A[i+1]=A[r];
A[r]=temp;
return i+1;
}

編集：これはデバッグが与えるエラーです。デバッグは、パーティション関数の先頭で約 4000 回目の再帰を停止します。コードの残りはここにあります。

ConsoleApplication1.exe の 0x00BF2509 で未処理の例外: 0xC00000FD: スタック オーバーフロー (パラメーター: 0x00000001、0x002B2FA8)。

4

3 に答える 3

0

例外がアクセス違反を示している場合、スタック制限について考えるのはなぜですか? あなたのコードには確かにバグがあり、アプリケーションに属さない禁止されたメモリに書き込むことになります。デバッガで実行しましたか？少なくともどの反復でエラーが発生したかがわかります。

于 2013-10-26T14:27:59.083 に答える
0

あらすじ

アルゴリズムの書き起こしと実装は問題ないようです。問題なく動作します。

ドライバー コードを精査して、配列の境界を超えていないことを確認する必要があります。そのドライバ コードに問題が見つかる可能性があります。

分析

あなたが示すソートとパーティションのコードで少し作業したので、大きな問題はないと思います。次のテスト ケースを使用しましたが、GCC 4.8.2 を搭載した Mac OS X 10.9 でテストしていました。-std=c11これは(他のオプションの中でも特に厳格なオプションで)コンパイルされてforおり、C99 に追加された 2 つの機能 (「ループ内で変数を宣言する」機能と「必要に応じて変数を宣言する」機能) を使用しています。C99 対応のコンパイラを使用しない場合は、これらを簡単に修正できます。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static void dump_partition(char const *tag, int *array, int lo, int hi)
{
    if (lo < hi)
    {
        int i;
        printf("%s: %d..%d\n", tag, lo, hi);
        for (i = lo; i <= hi; i++)
        {
            printf(" %4d", array[i]);
            if ((i - lo) % 10 == 9)
                putchar('\n');
        }
        if ((i - lo) % 10 != 0)
            putchar('\n');
    }
}

static int partition(int *A, int p, int r)
{
    const int x=A[r];
    int i=p-1;
    int j=p;
    int temp;

    while (j < r)
    {
        if (A[j] <= x)
        {
            i++;
            temp=A[i];
            A[i]=A[j];
            A[j]=temp;
        }
        j++;
    }
    temp=A[i+1];
    A[i+1]=A[r];
    A[r]=temp;
    return i+1;
}

static void quicksort_last(int *A, int p, int r)
{
    if (p < r)
    {
        int q=partition(A, p, r);
        printf("quicksort: %p (%d..%d)\n", (void *)&q, p, r);
        //dump_partition("L-part", A, p, q-1);
        //dump_partition("R-part", A, q+1, r);
        quicksort_last(A, p, q-1);
        quicksort_last(A, q+1, r);
    }
}

int main(void)
{
    int data[] =
    {
        31, 14, 53, 45, 88,  0, 79, 59, 84,  5,
        83, 42, 61, 38, 24, 47, 86, 69,  8, 36,
    };
    enum { N_DATA = sizeof(data) / sizeof(data[0]) };

    dump_partition("Random", data, 0, N_DATA-1);
    quicksort_last(data, 0, N_DATA-1);
    dump_partition("Sorted", data, 0, N_DATA-1);

    enum { BIG_SIZE = 10000 };
    int data2[BIG_SIZE];
    srand(time(0));
    for (int i = 0; i < BIG_SIZE; i++)
        data2[i] = rand() % BIG_SIZE;

    dump_partition("Random", data2, 0, BIG_SIZE-1);
    quicksort_last(data2, 0, BIG_SIZE-1);
    dump_partition("Sorted", data2, 0, BIG_SIZE-1);

    return 0;
}

このdump_partition()機能により、パーティションの内容を監視できます。のコメントアウトされたものquicksort_last()がアクティブな場合、パーティション分割が正しく機能していることを確認できました。のprintf()アドレスを出力するqは、スタックの深さの尺度を示します。私のマシンでは、実行からの出力:

qs | grep quicksort: | sort -u -k2,2

だった：

quicksort: 0x7fff555f66f0 (3962..3963)
quicksort: 0x7fff555f6730 (3961..3963)
quicksort: 0x7fff555f6770 (3961..3965)
quicksort: 0x7fff555f67b0 (1214..1215)
quicksort: 0x7fff555f67f0 (1197..1198)
quicksort: 0x7fff555f6830 (1151..1152)
quicksort: 0x7fff555f6870 (1150..1152)
quicksort: 0x7fff555f68b0 (865..867)
quicksort: 0x7fff555f68f0 (435..436)
quicksort: 0x7fff555f6930 (433..436)
quicksort: 0x7fff555f6970 (20..21)
quicksort: 0x7fff555f69b0 (20..22)
quicksort: 0x7fff555f69f0 (20..23)
quicksort: 0x7fff555f6a30 (20..28)
quicksort: 0x7fff555f6a70 (20..29)
quicksort: 0x7fff555f6ab0 (20..30)
quicksort: 0x7fff555f6af0 (1..2)
quicksort: 0x7fff555f6b30 (1..4)
quicksort: 0x7fff555f6b70 (0..4)
quicksort: 0x7fff555f6bb0 (0..6)
quicksort: 0x7fff555f6bf0 (0..11)
quicksort: 0x7fff555f6c30 (0..18)
quicksort: 0x7fff555f6c70 (0..93)
quicksort: 0x7fff555f6cb0 (0..138)
quicksort: 0x7fff555f6cf0 (8..9)
quicksort: 0x7fff555f6d30 (7..9)
quicksort: 0x7fff555f6d70 (3..4)
quicksort: 0x7fff555f6db0 (0..1)
quicksort: 0x7fff555f6df0 (0..5)
quicksort: 0x7fff555f6e30 (0..19)

最大スタック深度は次のとおりです。

  0x7fff555f6e30
- 0x7fff555f66f0
  --------------
  0x000000000740

これは 2 KiB 未満です。スタックには 28 のレベルがあります。これは、ランダム データ (表示されているコード) を使用したものです。既にソートされたデータをソートするようにコードを修正したところ、使用されるスタックがはるかに大きくなりました — コメントで指摘したように、これはパーティショニングで非常に悪い動作につながります。

入力データが既にソートされている場合、サブ配列の最初の要素をピボット値として選択すると、二次ソートと非常に深い再帰が発生します。ピボットをランダムに選択するか、Median of Threeや関連する手法を使用することをお勧めします。

スタックには 9999 のレベルがあり、スタック位置の違いは次のとおりです。

  0x7fff5d0bde30
- 0x7fff5d021ab0
  --------------
  0x000000013074

ただし、それでも使用されるスタック スペースは 80 KiB 未満です (並べ替えコードでは、配列のスペースは余分ですが、既知の量であり、約 40 KiB です)。これらのサイズのいずれも、通常のマシンにストレスを与えるべきではありません。

したがって、問題は質問で示したコードではないことを診断する必要があります。これは意外によくあることです。

これを確認するには、私のドライバー コード (main()およびおそらくdump_partition()関数) を取得し、quicksort_last(). 私が得た結果と同様の結果が得られるはずです。その場合は、ドライバー コードの作業を開始できます。私はそれを見て、精査したくないと判断しました。実際、最初に投稿されたコードはまったくコンパイルされません。また、繰り返しコードが大量に含まれているように見えますが、これは常に悪い兆候です。警告なしでコンパイルするのに十分な作業を行ったとき (つまり、大部分は慎重に計算された時間を出力することを意味しましたが、他にも問題がありました)、得られた出力は次のようになりました。

 0.000787
 0.156366
 0.000001
 0.031464
 0.000001
 0.040427
 0.001198
 0.597619
 0.000001
 0.121826
 0.000000
 0.159727
 0.001914
 1.335059
 0.000001
 0.275667
 0.000002
 0.358740
 0.002504
 2.381662
 0.000000
 0.487816
 0.000000
 0.645867

これは%13.6f、フォーマット文字列として使用して時間を出力していました。繰り返しますが、Mac OS X 10.9 ではクラッシュしませんでした。このコードではスタック使用量を測定しませんでした。

于 2013-10-26T19:32:32.340 に答える
0

ええと、私が最後にしたことは、私が最初にすべきことでした（いつものように）

void plusplus(int a){
    printf("%d\n",a);
    plusplus(a+1);
}

int main(){
    plusplus(0);
    return 0;
}

このコードを実行すると、4700 回目の再帰でクラックします。だから私はそれを取得しています.1 mbスタックが4700番目の深さで満たされているか、制限があります(これは疑わしいです)。

お時間をありがとうございました。

于 2013-11-02T11:04:11.597 に答える