编程

可利用空间表（freelist）

在一开始，我们先用 Virginia Tech 的一段文字，对可利用空间表有一个初步的了解。

链表中节点的创建与删除方法，给了使用它的人一个简单而有效的管理内存的办法。Link 类可以维护自己的可利用空间表，而不是频繁地调用 new 函数。一个可利用空间表存储着目前没有被使用的节点内存空间。当一个元素被从链表中释放的时候，它会被移至可利用空间表的头部。当把一个新元素插入链表中的时候，程序可以先检查可利用空间表中有没有可用的元素。如果有的话，会直接提取出那个元素；如果没有，再使用传统的 new 函数来申请一块空间。 所以说，可利用空间表只是链表的一种应用。

对于周期性增减的链表来说，可利用空间表尤其有用。除非链表的大小达到空间上限，可利用空间表所需的空间就永远不会增加。当链表释放元素之后，对新元素的需求可以直接由可利用空间表来处理。当一个程序使用多个链表的时候，也不妨使用可利用空间表。这样，只要这几个链表不同时变长或变短，可利用空间表就可以让节点在链表之间转移（而非重复调用 new 和 delete 函数，无端地消耗时间）。

在下面的例子中，Link 类增加了 get 和 release 函数。

弗吉尼亚理工大学的课程 数据结构与算法：可利用空间表

cpp 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Link<E> {      // 单链表节点，使用了可利用空间表
  private E e;       // 该节点的值
  private Link<E> n;    // 后继引用

  // 构造函数
  Link(E it, Link<E> inn) {e = it; n = inn;}
  Link(Link<E> inn) {e = null; n = inn;}

  E element() { return e;}                        // 返回节点的值
  E setElement(E it) {return e = it;}            // 修改节点的值
  Link<E> next() { return n;}                     // 返回后继引用
  Link<E> setNext(Link<E> inn) {return n = inn;} // 修改后继

  // 增加 freelist 支持
  private static Link freelist = null;                  // 该类的可利用空间表

  // 如果表中有可用节点，返回它
  static <E> Link<E> get(E it, Link<E> inn) {
    if (freelist == null)
      return new Link<E>(it, inn);                 // new 一个 link
    Link<E> temp = freelist;                       // 从 freelist 中取出
    freelist = freelist.next();
    temp.setElement(it);
    temp.setNext(inn);
    return temp;
  }

  // 将一个节点存入表中
  void release() {
    e = null;   // 取消对该节点的引用
    n = freelist;
    freelist = this;
  }
}

freelist 变量的声明使用了 static 关键字。它可以创建一个由所有 Link 节点共用的对象。

请注意它有多么的简单，因为它们仅需要各自在表的前端移除或添加元素。可利用空间表的 get 和 release 函数的时间复杂度都为 Θ(1) ，除非表空了，必须调用 new 函数。为了适配可利用空间表版本的节点，我们要对链表类做一些必要的改动。

弗吉尼亚理工大学的课程 数据结构与算法：可利用空间表

cpp 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

  // 在当前位置插入 “it”
  public boolean insert(E it) {
    curr.setNext(Link.get(curr.element(), curr.next())); // 得到 link
    curr.setElement(it);
    if (tail == curr) tail = curr.next();    // 新的链表尾
    listSize++;
    return true;
  }

  // 将 “it” 推到链表中
  public boolean append(E it) {
    Link<E> temp = Link.get(null, null);
    tail.setNext(temp);
    tail.setElement(it);
    tail = tail.next();
    listSize++;
    return true;
  }

  // 将当前位置的元素移除并返回
  public E remove () {
    if (curr == tail) return null;          // 没有什么能移除的
    E it = curr.element();                  // 存储元素的值
    curr.setElement(curr.next().element()); // 将下一个元素往前移一位
    if (curr.next() == tail) tail = curr;   // 要是删除了链表尾元素，还需要修改表尾
    Link<E> tempptr = curr.next();          // 存储待删除节点的位置
    curr.setNext(curr.next().next());       // 修改前一位的指针，往后指一位
    tempptr.release();                      // 将待删除结点释放
    listSize--;                             // 链表长度 - 1
    return it;                              // 返回删除的节点值
  }

使用可利用空间表能够节省多长时间，取决于你用什么语言编写代码。对于 C++ 这种语言，程序员必须使用 new 和 delete 函数来管理内存空间，从可利用空间表中取出节点只花费了使用 new 函数方法的不到十分之一时间。对于 Java 这种有垃圾清理的语言，最初似乎你使用可利用空间表不会节省多少时间，因为 Java 的 new 函数能够快速的从它的存储池中返回内存空间。然而，要是你不用可利用空间表，释放节点会产生垃圾，而这需要大量的回收垃圾的时间。

弗吉尼亚理工大学的课程 数据结构与算法：可利用空间表

仿照这种思路，我信心满满地在 Clifford A. Shaffer 的《数据结构与算法分析 第三版》链表实现线性表基础上，写成了一个可利用空间表类——很遗憾，这个并不能实现上述的多个链表之间共享节点的功能。嗯，坦白说，我并没有看懂前面的 Java 代码就开始上手写 C++ 了。

需要特别注意的是，原书中的代码有一个问题：在 moveToEnd() 之后，curr 指针指向的是 tail，而输出的时候输出的是 curr 的后继的值。已经改正。

cpp 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

//freelist.h
#include <stack>
#include "list\_adt.h"
using namespace std;
#ifndef LINK
#define LINK
template <typename E>
class Link //node 的实现
{
public:
    E element;
    Link \*next;
    Link(const E &elemval, Link \*nextval = NULL)
    {
        element = elemval;
        next = nextval;
    }
    Link(Link \*nextval = NULL)
    {
        next = nextval;
    }
};
#endif
#ifndef FREELIST\_H
#define FREELIST\_H
template <typename E>
class Freelist : public List<E>
{
private:
    stack<Link<E> \*> spareElem; // 存放暂时不用的元素地址
    Link<E> \*head;              // 头指针
    Link<E> \*tail;              // 尾指针
    Link<E> \*curr;              // 当前位置的前驱节点
    int cnt;
    Link<E> \*getNewElem() // 获取一个新元素的地址
    {
        Link<E> \*temp;
        if (spareElem.empty()) // 可利用空间表中无元素
        {
            temp = new Link<E>;
        }
        else // 还有元素，可以直接传过来地址
        {
            temp = spareElem.top();
            spareElem.pop();
        }
        return temp;
    }
    void init() // 初始化链表，只有一个 head 元素
    {
        curr = tail = head = getNewElem();
        cnt = 0;
    }
    void removeall() // 清空链表
    {
        while (head != NULL)
        {
            curr = head;
            head = head->next;
            spareElem.push(curr);
        }
    }

public:
    Freelist(int size = 65536)
    {
        init();
    }
    ~Freelist()
    {
        removeall();
    }
    void clear() // 清空链表并初始化
    {
        removeall();
        init();
    }
    void insert(const E &it) // 插入元素
    {
        curr->next = getNewElem();
        curr->next->element = it;
        tail->next->next = NULL;
        if (tail == curr)
        {
            tail = curr->next;
        }
        cnt++;
    }
    void append(const E &it) // 在最后添加元素
    {
        tail->next = getNewElem();
        tail->next->element = it;
        tail->next->next = NULL;
        tail = tail->next;
        cnt++;
    }
    E remove() // 删除当前位置的元素
    {
        E it = curr->next->element;
        Link<E> \*ltemp = curr->next;
        if (tail == curr->next)
        {
            tail = curr;
        }
        curr->next = curr->next->next;
        spareElem.push(ltemp);
        cnt--;
        return it;
    }
    void moveToStart() // 移至头部
    {
        curr = head;
    }
    void moveToEnd() // 移至尾部
    {
        curr = tail;
        prev(); //curr 最后必须是 tail 的前驱才行
    }
    void prev() // 左移一位
    {
        if (curr == head)
        {
            return;
        }
        Link<E> \*temp = head;
        while (temp->next != curr)
        {
            temp = temp->next;
        }
        curr = temp;
    }
    void next() // 右移一位
    {
        if (curr != tail)
        {
            curr = curr->next;
        }
    }
    int length() const // 返回长度
    {
        return cnt;
    }
    int currPos() const // 返回当前位置
    {
        Link<E> \*temp = head;
        int i = 1;
        for (i = 0; curr != temp; i++)
        {
            temp = temp->next;
        }
        return i;
    }
    void moveToPos(int pos) // 移动至指定位置
    {
        //Assert((pos>=0)&&(pos<=cnt),"Position Out of Range");
        curr = head;
        for (int i = 0; i < pos; i++)
        {
            curr = curr->next;
        }
    }
    const E &getValue() const // 返回当前位置的值
    {
        //Assert(curr->next!=NULL,"No Value");
        return curr->next->element;
    }
};
#endif

为了探究可利用空间表的效果，我写了一段程序进行推入、清空，再推入的操作，并测定运行时间。

cpp 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include "freelist.h"
#include "linklist.h"
using namespace std;

int main()
{
    printf("=============LINKLIST============\\n");
    LList<int> l;
    srand(time(NULL));
    clock\_t stage1, stage2, stage3;
    stage1 = clock();
    for (int i = 0; i < 10000000; i++)
    {
        l.append(0);
    }
    while (!l.empty()) // 这里将链表全部清空
    {
        l.moveToStart();
        l.remove();
    }
    stage2 = clock();
    for (int i = 0; i < 10000000; i++)
    {
        l.append(rand());
    }
    stage3 = clock();
    double dur1, dur2;
    dur1 = (stage2 - stage1) \* 1.0 / CLOCKS\_PER\_SEC;
    dur2 = (stage3 - stage2) \* 1.0 / CLOCKS\_PER\_SEC;
    printf("Append & Clear Consumption:%lf\\nRe-append Consumption:%lf\\n", dur1, dur2);
    printf("=============FREELIST============\\n");
    Freelist<int> f;
    srand(time(NULL));
    stage1 = clock();
    for (int i = 0; i < 10000000; i++)
    {
        f.append(0);
    }
    while (!f.empty())
    {
        f.moveToStart();
        f.remove();
    }
    stage2 = clock();
    for (int i = 0; i < 10000000; i++)
    {
        f.append(rand());
    }
    stage3 = clock();
    dur1 = (stage2 - stage1) \* 1.0 / CLOCKS\_PER\_SEC;
    dur2 = (stage3 - stage2) \* 1.0 / CLOCKS\_PER\_SEC;
    printf("Append & Clear Consumption:%lf\\nRe-append Consumption:%lf\\n", dur1, dur2);
}

这篇文章到这里似乎就结束了？并没有，你看到滚动条就会发现不对劲。结果很尴尬，这样的可利用空间表，比普通的链表还要慢上不少…… 这次甚至还是最快的结果。

尴尬的结果

就这样把这个问题搁了好几天，我突然想到了原因。在将元素推进可利用空间表的时候，STL <stack> 需要再 new 一个 Link 指针，指向原来的空间；推出的时候，也需要类似于 delete 的操作——这样，不仅没有省下 new 和 delete 的时间，反而徒增了赋值的时间代价。虽然我也不明白，为什么会慢这么多……

下面我画了 2 张图，以删除节点为例，来描述我的前后两种理解。

原来对可利用空间表的理解

我还意识到，闲置的结点，实际上是可以自行重新连接成链的，只需要维护一个栈顶指针即可。这样就不需要再 new 空间了。

现在的理解

少废话，上代码。

cpp 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

//freelist.h
#include "list\_adt.h"
#include <stack>
using namespace std;
#ifndef LINK
#define LINK
template <typename E>
class Link //node 的实现
{
public:
    E element;
    Link \*next;
    Link(const E &elemval, Link \*nextval = NULL)
    {
        element = elemval;
        next = nextval;
    }
    Link(Link \*nextval = NULL)
    {
        next = nextval;
    }
};
#endif
#ifndef FREELIST\_H
#define FREELIST\_H
template <typename E>
class Freelist : public List<E>
{
private:
    Link<E> \*freelist = nullptr; // 可利用空间表的栈顶指针
    Link<E> \*head;               // 头指针
    Link<E> \*tail;               // 尾指针
    Link<E> \*curr;               // 当前位置的前驱节点
    int cnt;
    Link<E> \*getNewElem() // 获取一个新元素的地址
    {
        if (freelist == nullptr) // 空的
        {
            return new Link<E>;
        }
        else
        {
            Link<E> \*temp = freelist;
            freelist = freelist->next;
            return temp;
        }
    }
    void abandonElem(Link<E> \*tgt)// 将一个元素移至可利用空间表中
    {
        tgt->next = freelist;
        freelist = tgt;
    }
    void init() // 初始化链表，只有一个 head 元素
    {
        curr = tail = head = getNewElem();
        cnt = 0;
    }
    void removeall() // 清空链表
    {
        while (head != NULL)
        {
            curr = head;
            head = head->next;
            abandonElem(curr);
        }
    }

public:
    Freelist(int size = 65536)
    {
        init();
    }
    ~Freelist()
    {
        removeall();
        Link<E> \*temp;
        while (freelist != nullptr) // 程序结束的时候析构，要把没有利用的结点也全都释放掉
        {
            temp = freelist;
            freelist = freelist->next;
            delete temp;
        }
    }
    void clear() // 清空链表并初始化
    {
        removeall();
        init();
    }
    bool empty()
    {
        if (head == tail)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    void insert(const E &it) // 插入元素
    {
        curr->next = getNewElem();
        curr->next->element = it;
        tail->next->next = NULL;
        if (tail == curr)
        {
            tail = curr->next;
        }
        cnt++;
    }
    void append(const E &it) // 在最后添加元素
    {
        tail->next = getNewElem();
        tail->next->element = it;
        tail->next->next = NULL;
        tail = tail->next;
        cnt++;
    }
    E remove() // 删除当前位置的元素
    {
        E it = curr->next->element;
        Link<E> \*ltemp = curr->next;
        if (tail == curr->next)
        {
            tail = curr;
        }
        curr->next = curr->next->next;
        abandonElem(ltemp);
        cnt--;
        return it;
    }
    void moveToStart() // 移至头部
    {
        curr = head;
    }
    void moveToEnd() // 移至尾部
    {
        curr = tail;
        prev(); //curr 最后必须是 tail 的前驱才行
    }
    void prev() // 左移一位
    {
        if (curr == head)
        {
            return;
        }
        Link<E> \*temp = head;
        while (temp->next != curr)
        {
            temp = temp->next;
        }
        curr = temp;
    }
    void next() // 右移一位
    {
        if (curr != tail)
        {
            curr = curr->next;
        }
    }
    int length() const // 返回长度
    {
        return cnt;
    }
    int currPos() const // 返回当前位置
    {
        Link<E> \*temp = head;
        int i = 1;
        for (i = 0; curr != temp; i++)
        {
            temp = temp->next;
        }
        return i;
    }
    void moveToPos(int pos) // 移动至指定位置
    {
        //Assert((pos>=0)&&(pos<=cnt),"Position Out of Range");
        curr = head;
        for (int i = 0; i < pos; i++)
        {
            curr = curr->next;
        }
    }
    const E &getValue() const // 返回当前位置的值
    {
        //Assert(curr->next!=NULL,"No Value");
        return curr->next->element;
    }
};
#endif

时间很喜人。在 Windows 下，时间对比如图，可以看到可利用空间表用时大幅度领先：

Windows benchmark

而在 Linux（Ubuntu 20.04.2，WSL2）下，优势都小了一些，但是重新添加元素过程的优势仍然十分明显。

Linux benchmark

许可证：CC BY-SA 4.0
最后更新于 Jun 14, 2023 21:05 +0800