4

min-heapダイクストラのアルゴリズムの一部として、Cで a の実装を書いています。すべての詳細を書き留めて、テスト プログラムは valgrind テストに合格しましたが、プロセスで途方もない量のメモリを割り当てます。最終テストはINT_MAXbyのグリッドINT_MAX(座標は単なる整数) で行われ、SIGXCPUテストするとエラーが発生します。キューにポジションを挿入16kしてすべてを削除しても、非常に長い時間がかかり、8 MB. 500 MB巨大なグリッド テスト ケースで実行すると、手動で終了する前に取得できます。何が起こっているのでしょうか？ここに私のコードの一部があります:

struct position {
    int x;
    int y
};

typedef struct elt {
    int priority;
    int distance;
    struct position p;
} *Elt;

typedef struct heap {
    int size;
    int capacity;
    Elt *elts;
} *Heap;

void heap_insert(Heap h, Elt e, int *counter) {
    if(h->capacity < (h->size + 2)) {
        h->elts = realloc(h->elts, h->capacity * sizeof(Elt) * 2);
        h->capacity *= 2;
    }
    h->elts[h->size] = malloc(sizeof(*Elt));
    elt_assign(h->elts[h->size], e);
    h->size++;
    heapify(h->size, h->elts);
    *counter = *counter + 1;
}

私の他のすべての関数は、メモリ管理を 1 回だけ実行するか、関数内で実行するか、またはまったく実行しません。この場合の初期サイズは でしたが64、 から始めて同じ効果が得られました1024。また、キューのサイズを制限しようとしましたが、役に立ちませんでした。それは私のヒープ化コードではないと確信していますが、これは念のためです

static void floatDown(int n, Elt *a, int pos) {
    Elt x = malloc(sizeof(struct elt));
    elt_assign(x, a[pos]);
    for(;;) {
        if(Child(pos, 1) < n && a[Child(pos, 1)]->priority < a[Child(pos, 0)]->priority) {
            if(a[Child(pos, 1)]->priority < x->priority) {
                elt_assign(a[pos], a[Child(pos, 1)]);
                pos = Child(pos, 1);
            } else {
                break;
            }
        } else if(Child(pos, 0) < n && a[Child(pos, 0)]->priority < x->priority) {
            elt_assign(a[pos], a[Child(pos, 0)]);
            pos = Child(pos, 0);
        } else {
            break;
        }
    }
    elt_assign(a[pos], x);
    free(x);
}

static void heapify(int n, Elt *a) {
    for(int i = n - 1; i >= 0; i--) {
        floatDown(n, a, i);
    }
}

どんな助けでも大歓迎です。

4

1 に答える 1

2

これが私の作業理論です。私は自分が間違っていることを喜んで発見しますが、残りのコードがなければ、それを計測、実行、およびテストすることはできません。

... struct heap { ... Elt *elts; } ...whenの間接化によりtypedef struct elt {...} *Elt;、4 つの int をコピーして 1 つのポインターをコピーするコストを節約できますが、コピーは高速で、log2(N) 回しか発生しません。

代わりに、everystruct eltは個別に malloc されます。malloc されたブロックの実際のサイズを探し回らなくても、平均して N/2 sizeof(struct elt) を無駄にすると推定できます (実際、私のマシンではもっと悪いと思います)。

また、（大きなブロックの間に小さなブロックを配置することによって）メモリの不連続なブロックを作成する可能性があるため、realloc は常により大きなブロックを割り当てる必要があるため、以前のブロックを再利用するのが難しくなります。この特定のケースでは、内部の断片化や malloc の多数の呼び出しによる無駄ほど重要ではないと思います。

また、「キャッシュバスター」が作成される場合もあります。実際の値はメモリ全体に分散されており、malloc された struct elt ブロックの内部フラグメンテーションのため、キャッシュ ラインは比較的まばらです。

だから置き換え：

typedef struct elt {
    int priority;
    int distance;
    struct position p;
} *Elt;

typedef struct heap {
    int size;
    int capacity;
    Elt *elts;
} *Heap;

と

typedef struct elt {
    int priority;
    int distance;
    struct position p;
} Elt;    // no longer a pointer

typedef struct heap {
    int size;
    int capacity;
    Elt *elts;
} *Heap;

そして変更：

void heap_insert(Heap h, Elt e, int *counter) {
    if(h->capacity < (h->size + 2)) {
        h->elts = realloc(h->elts, h->capacity * sizeof(Elt) * 2);
        h->capacity *= 2;
    }
    h->elts[h->size] = malloc(sizeof(*Elt));
    elt_assign(h->elts[h->size], e);
    h->size++;
    heapify(h->size, h->elts);
    *counter = *counter + 1;
}

に

void heap_insert(Heap h, Elt e, int *counter) {
    if(h->capacity < (h->size + 2)) {
        h->elts = realloc(h->elts, h->capacity * sizeof(Elt) * 2);
        h->capacity *= 2;
    }
    h->elts[h->size] = e;  // no longer need to malloc
    h->size++;
    heapify(h->size, h->elts);
    *counter = *counter + 1;
}

そのため、ヒープを保持するために malloc'd/realloc'd されたメモリの量は、およそ 2 * N * sizeof(struct elt) になります。関数/マクロ elt_assign を変更して、他の変更を隠すことができます。

次に、次のように変更して、malloc の量をさらに減らします。 

static void floatDown(int n, Elt *a, int pos) {
    Elt x = malloc(sizeof(struct elt));
    elt_assign(x, a[pos]);
...
    elt_assign(a[pos], x);
    free(x);
}

に

static void floatDown(int n, Elt *a, int pos) {
    Elt x = a[pos];
...
    a[pos] = x;
}

これにより、malloc および free されたメモリの量がさらに削減されます。

基本的に、realloc の呼び出しは (およそ) log2(N) 回のみにする必要があります。realloc がコピーではなく既存のブロックを拡張する可能性も高くなります。

編集：

heap_insertメモリ割り当てよりも大きな問題があります。

void heap_insert(Heap h, Elt e, int *counter) {
    ...
    heapify(h->size, h->elts);
    ...
}

heapifyヒープに要素が挿入されるたびに呼び出されます。つまり、heapify は N 回呼び出されます。heapifyは：

static void heapify(int n, Elt *a) {
    for(int i = n - 1; i >= 0; i--) {
        floatDown(n, a, i);
    }
}

これはfloatdown、挿入された要素ごとに、これまでのヒープ内のすべての要素を呼び出します。そのため、実行時間は約(N^2)/2 (つまり、O(N^2)) 実行時間になります。heap_insert

ではなく、ヒープに追加する各要素にheap_insert使用する必要があると思います。floatDownheapify

于 2012-04-11T22:49:43.583 に答える