min-heap
ダイクストラのアルゴリズムの一部として、Cで a の実装を書いています。すべての詳細を書き留めて、テスト プログラムは valgrind テストに合格しましたが、プロセスで途方もない量のメモリを割り当てます。最終テストはINT_MAX
byのグリッド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);
}
}
どんな助けでも大歓迎です。