4

min-heap作为 Dijkstra 算法的一部分，我正在用 C 语言编写 a的实现。我已经把所有细节都写下来了，我的测试程序通过了 valgrind 测试，但它在这个过程中分配了荒谬的内存量。最后的测试是在一个网格上INT_MAX（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;
}

我所有的其他功能都一次性进行内存管理，在功能中进行，或者根本不进行。在这种情况下，初始大小是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 个整数并用复制 1 个指针替换它的成本，但是复制速度很快，并且只发生 log2(N) 次。

相反，每个struct elt都是单独的 malloc'd。无需四处寻找 malloc'd 块的实际大小，我们可以估计，平均而言这将浪费 N/2 sizeof(struct elt) （实际上，我认为它在我的机器上更糟）。

它还可能创建不连续的内存块（通过将小块放在较大的块之间），因此 realloc 必须始终分配更大的块，因此更难重用以前的块。在这种特定情况下，我认为这并不像由于内部碎片或大量 malloc 调用造成的浪费那么重要。

它还可能创建一个“缓存破坏者”。实际值分布在整个内存中，并且由于 malloc 结构 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'ing 的数量： 

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'ed 和 free'd 的内存量。

从本质上讲，应该只有（大约）log2(N) 次 realloc 调用。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应该使用floatDown它添加到堆中的每个元素，而不是heapify.

于 2012-04-11T22:49:43.583 回答