Unity中的資源管理-對象池技術(2)

本文分享Unity中的資源管理-對象池技術(2)

在上一篇文章中, 我們一起學習了普通類的對象池, 這種實作有一定的特點和适用範圍:

• 隻能存放相同類型的對象
• 所有對象都一視同仁, 在産生和回收後都需要額外的操作, 比如産生後需要初始化, 回收後需要重置資訊

今天要介紹一種更加通用和靈活的實作方式: 這種對象池隻負責存取對象, 而這些對象不拘泥類型且不需要額外的操作就能使用和回收.

簡單說就是上一個對象池實作特點的反面.

對象池? 容器?

可能有些同學會有疑問, 如果隻是需要一個存取對象的容器, 那麼我用

ArrayList

,

List

, 或者

Dictionary

不就行了麼, 為什麼還需要單獨做一個對象池呢?

其實這些容器都可以看做是這種對象池的某種實作, 至于可以存放各種類型對象, 我們隻需要讓這些容器存放的是

object

類型即可. 也就是說你可以把這些容器都稱為對象池. 對象池的觀點其實很寬泛, 隻要能存放大量對象, 并提供對應的産生和回收接口即可.

今天要介紹的實作方式就是這樣一種容器, 能夠存放各種類型的對象, 而且可以及其快速的存取.

大家肯定第一個就能想到, 支援及其快速存取的就是數組, 存取都是

O(1)

. 沒錯, 這種對象池就是基于數組, 是在一定程度上優化了數組的缺點的實作.

數組的缺點及其優化方式有:

• 容量大小固定
  • 通過動态擴容和縮容解決

  • List

    就是在數組的基礎上進行這種優化的容器
• 隻能存放同一個類型的對象
  • 通過存放

    object

    類型的對象解決

  • ArrayList

    就是在數組的基礎上進行這種優化的容器
  • 但是

    ArrayList

    在删除元素時會移動删除位置之後的所有的元素
• 隻能通過整型索引對象
  • 通過将其它類型的索引轉換為整型解決

  • Dictionary

    就是通過将其它類型的索引通過計算hash值轉換為整型索引的容器

總之, 數組是一個非常基礎的容器, 但是有各種各樣的缺陷, 但是我們可以通過解決各種缺陷來産生新的容器, 這些容器繼承了數組的快速存取而克服了部分缺陷. 我們日常中使用的大部分容器在底層都是通過數組實作的, 比如

ArrayList, Stack, Queue, List, Dictionary, HashMap

等等.

今天要介紹的對象池和

ArrayList

的實作有些類似, 但是克服了其需要在删除元素時移動元素的缺點. 其支援的特性如下:

• 支援極其快速存取對象, 且不用移動對象
• 支援存放任意類型的對象
• 支援動态擴容縮容
• 使用整型索引對象

這就是

Xlua

中對象池的實作,

Xlua

使用這種對象池管理所有

lua

引用的

C#

對象.

實作原理

首先其底層容器是一個數組, 因為要記錄位置資訊, 是以需要的是一個二級結構, 這個結構存放了下一個可用位置的資訊, 并且持有了真正需要存取的對象.

const int LIST_END = -1;
const int ALLOCED = -2;

// 位置插槽, 用于描述位置資訊, 用類也可以
struct Slot
{
    // 如果是正值代表下一個可用位置, 如果為-2(ALLOCED)代表目前位置已被占用, -1代表這個位置是最後一個可用位置
    public int next;
    
    // 持有對象
    public object obj;
}

// 底層容器
private Slot[] list = new Slot[512];
           

然後, 我們需要一個字段來記錄目前使用的插槽數量:

private int count = 0

.

再然後, 我們需要一個連結清單将所有可用位置串連, 當然, 我們不是使用真正的連結清單, 而是使用

Slot

的

next

字段結合一個表頭索引來串連:

private int freelist = LIST_END

. 一旦這個索引指向了一個确切的位置, 那麼代表我們擁有了至少一個可用位置, 至于有沒有更多可用的位置, 那麼需要檢視該位置的

next

字段是否為正值. 這裡純粹使用語言來描述比較讓人迷惑, 大家隻需要有一個簡單的印象就行了. 總之, 表頭索引指向可用位置, 通過可用位置的

next

串連下一個可用位置.

最後, 我們來描述詳細的算法:

• 初始狀态下,

  freelist = LIST_END

  , 代表現在沒有可用位置.
• 當添加一個對象時, 發現沒有可用位置, 那麼向對象池申請一個新的位置:

  index = count++

  , 也就是說可用位置為0, 并且将

  count++

• 使用該位置存儲對象, 并将

  next

  字段置為已被占用的狀态:

  list[index].obj = obj; list[index].next = ALLOCED

  , 并傳回索引.
• 此時池中有一個對象(位置

  index = 0; count = 1

  ), 可用位置依然為0(

  freelist = LIST_END

  )
• 當删除一個對象時, 通過對象的索引查找到位置并情況位置持有的對象:

  list[index].obj = null

• 将目前位置的置為可用狀态, 且按照頭插法插入可用連結清單:

  list[index].next = freelist; freelist = index;

• 最後傳回已經删除的對象
• 此時池中沒有對象, 有一個可用位置(位置

  index = 0; count = 1; freelist = 0; list[0].next = -1

  )
• 再次添加一個對象, 發現有可用位置(

  freelist = 0

  ), 直接使用該位置, 并在頭部将位置從可用位置連結清單中移除:

  list[0].obj = obj; freelist = list[0].next;

  , 最後将位置的狀态設定為已占用:

  list[0].next = ALLOCED;

• 最後傳回索引

以上就是整個算法的核心實作了. 這個算法十分巧妙, 但是也讓人特别迷惑, 建議對連結清單不熟悉的同學先溫習一下連結清單的基礎知識, 看的頭暈就不要吐槽作者了喲.

下面貼出添加和删除還有擴容部分的完整代碼, 這裡作者做了一些修改以便更容易了解.

// 申請一個新的大小為原始數組兩倍大小的數組作為底層容器, 并被将原始數組的内容複制到新的數組
void extend_capacity()
{
    Slot[] new_list = new Slot[list.Length * 2];
    for (int i = 0; i < list.Length; i++)
    {
        new_list[i] = list[i];
    }
    
    list = new_list;
}

public int Add(object obj)
{
    // 沒有可用位置, 向對象池申請
    if (freelist == LIST_END) {
        if (count == list.Length)
        {
            // 對象池中已經沒有更多位置, 需要擴容
            extend_capacity();
        }

        // 申請一個新的位置
        var newSlotIndex = count++;
        ref var slot = ref list[newSlotIndex]; // 因為struct是值類型, 需要引用

        // 使用該位置并置占用狀态
        slot.obj = obj;
        slot.next = ALLOCED;
        return newSlotIndex;
    }

    // 從頭部取出第一個可用位置, 将該位置從可用連結清單中移除 
    var freeSlotIndex = freelist;
    ref var freeSlot = ref list[freeSlotIndex];
    freelist = freeSlot.next;

    // 使用該位置并置占用狀态
    freeSlot.obj = obj;
    freeSlot.next = ALLOCED;
    return freeSlotIndex;
}

public object Remove(int index)
{
    if (index < 0 || index >= count || list[index].next != ALLOCED)
        return null;

    // 找到位置, 取出對象并清空
    ref var slot = ref list[index];
    object o = slot.obj;
    slot.obj = null;

    // 使用頭插法将位置插入可用連結清單
    slot.next = freelist;
    freelist = index;

    return o;
}
           

注釋已經寫的比較清晰明了了, 相信隻要熟悉連結清單知識的同學基本毫無壓力.

這裡總結一下,

count

代表已經申請的位置數量, 但是不代表這些位置都被占用了, 隻有

freelist

指向表尾時才代表無可用位置, 需要再次申請. 如果需要知道對象池中已經存在的元素個數, 可以通過

count - Length(freelist)

, 當然, 也可以添加字段來記錄數量就行了.

最後再次感歎下這個設計的巧妙, 總之是學到了, 作者君又變強了(當然頭發依然茂密)!

好啦, 今天的内容就是這樣, 希望對大家有所幫助.