「优化」内存池

发布于 2018-07-12  408 次阅读


实现

在c++中,我们非常喜欢使用指针。因为指针非常适合人们的思考方式。

所以我们来优化一下指针的速度。

你们想一下:嵌套7,8层数组和一些平等无嵌套的箭头,哪个更容易理解?

~~当然是前者啦~~

指针非常亲和人们的语言和思维习惯,所以被众多OIer所追求。

~~当然你做工程时写指针 throw 出一堆 Error 时当然会绝望~~

所以说,为了获得更好的指针体验,我们现在分析一下,为什么指针比较慢。

我们来回顾一下图的常规写法:

struct Node{
    struct Edge *firstEdge;
    // Other Attributes.
}node[MAXN];

struct Edge{
    Node *s,*t;
    int w;
    Edge *next;
    Edge(Node *s,Node *t,int w) : s(s), t(t), w(w), next(s->firstEdge) {}
    // Other Attributes.
};

这种方式的缺点在哪里呢?我们发现建边的时候:

inline void add(int u,int v,int w){
    node[u].firstEdge = new Edge(&node[u],&node[v],w);
    //or node[v].firstEdge = new Edge(&node[v],&node[u],w);
}

会调用1~2次new函数,我们看一看new函数的执行过程:

A* pa = new A(3);

等价于:

A* pa = (A*)malloc(sizeof(A));
pa->A::A(3);
return pa;

这是在做什么呢?它就是:获得一块内存空间、调用构造函数、返回正确的指针。

是不是很麻烦?我们能不能直接返回呢?

于是,我们手动实现new的过程。

我们这样写:

struct Node{
    struct Edge *firstEdge;
    // Other Attributes.
}node[MAXN];

struct Edge{
    Node *s,*t;
    int w;
    Edge *next;
    // Other Attributes.
}pool[MAXM * 2],*frog = pool;

Edge *New(Node *s,Node *t,int w){
    Edge *ret = ++frog;
    frog->s = s;frog->t = t;
    frog->w = w;frog->next = s->firstEdge;
    return ret;
}

这样我们在调用的时候只需:

inline void add(int u,int v,int w){
    node[u].firstEdge = New Edge(&node[u],&node[v],w);
    // or node[v].firstEdge = New Edge(&node[v],&node[u],w);
}

发现了吗?我们其实就是预先定义出了所有要用的边(pool),然后用一个尾指针(frog)来指向。

每次加边时,我们直接另指针后移,然后获取一个新的未被初始化过的Edge变量,对其进行初始化即可。

其他步骤和普通指针一样即可。

所以说,我们在预定义内存池时,我们必须要算好开多少空间。

那么,内存池有什么好处呢?

优点

  1. 速度比new快了不少。
  2. 我们在需要精确定位第$ i $条边时,不需要多定义一个$ num $成员变量,省下了空间和时间。

那么,我们再拿一个线段树的例子来加深理解。

线段树原实现(部分)

struct SegmentTree{
    int l,r,sum,tag;
    SegmentTree *lc,*rc;
    SegmentTree(int l,int r,SegmentTree *lc,SegmentTree *rc) : l(l), r(r), sum(0), tag(0), lc(lc), rc(rc) {};
    
    static SegmentTree *build(int l,int r){
        int mid = (l + r) >> 1;
        return (l == r) ? SegmentTree(l,r,NULL,NULL) : SegmentTree(l,r,build(l,mid),build(mid + 1,r));
    }
    
    // Other Attributes.
}*segt;

我们对new过程进行分析。

每次执行new时,我们相当于初始化一个SegmentTree类型的变量。那么我们可以如此初始化:

SegmentTree *New(int l,int r,SegmentTree *lc,SegmentTree *rc){
    SegmentTree *ret = ++frog;
    ret->l = l;ret->r = r;
    ret->lc = lc;ret->rc = rc;
    ret->sum = ret->tag = 0;
    return ret;
}

那么,现在的实现就需要这样:

struct SegmentTree;

SegmentTree *New(int,int,SegmentTree *,SegmentTree *);

struct SegmentTree{
    int l,r,sum,tag;
    SegmentTree *lc,*rc;
    
    static SegmentTree *build(int l,int r){
        int mid = (l + r) >> 1;
        return (l == r) ? New(l,r,NULL,NULL) : New(l,r,build(l,mid),build(mid + 1,r));
    }
    
    // Other Attributes.
}pool[MAXN * 4],*frog = pool,*segt;

SegmentTree *New(int l,int r,SegmentTree *lc,SegmentTree *rc){
    SegmentTree *ret = ++frog;
    ret->l = l;ret->r = r;
    ret->lc = lc;ret->rc = rc;
    ret->sum = ret->tag = 0;
    return ret;
}

好了,相信你学会了内存池,就能抛弃掉毒瘤的数组写法和超级慢的new写法,能够获得更好的指针体验。


一个OIer。