您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 訊息 >> iOS 相關資訊

動手實現一個純 C 版的 CFArray

編輯:iOS 相關資訊

日常開發中我們都在用 NSArray,但最近在寫一個純 C 的庫,不想引入太多依賴,於是想把 NSArray 的功能提取出來。由於 NSArray 與 CFArray 是 Toll-Free Bridged 的,而且 CFArray 開源,於是本文研究了一下 CFArray 的實現,並給出一個純 C、無其他依賴的替代實現。

蘋果的實現演變

翻閱 CF 源碼前,先看到一篇 2005 年的老文章,對 CFArray 與 STL Vector 做了效能比較。當時的 CFArray 有個有趣的現象:當容量超過約 30 萬時,耗時曲線完全變了樣。出於好奇,我測試了目前系統的實現,發現結果已與當年完全不同,於是翻看了 CF 的歷史源碼。

1. 最初的 deque 實現
最開始,CFArray 底層用 deque(雙端隊列)實現,頭尾插入刪除效能很高,但在中間插入刪除時需要 memmove 搬移記憶體,效能便會下降。蘋果的方法是:當 CFArray 長度超過某個數值(大約是 262040)時,把底層換成 balanced tree。具體來說,蘋果寫了一個名為 CFStorage 的類,用平衡樹實現大資料量的高效存儲與編輯,CFArray 達到閾值時便替換為 CFStorage 來完成操作。

2. 2011 年的改動
但在 2011 年的 CF-635.15 中,蘋果把這個特性拿掉了。之後 CFArray 就只用簡單的 deque 實現,長度越大,中間插入刪除的耗時越長。至於為何這麼改,或許是怕切換資料結構造成時間抖動,或許是這個特性根本沒多少人用到。

3. 最新實現
最新的 CFArray 程式碼應該又調整過,效能比單純的雙端隊列更高,我猜測應該換成了環形緩衝區(circular buffer),只是蘋果尚未開源最新程式碼。

我的測試與實現

在我的系統(10.9.1)上,我參考最新的 CFArray 源碼實作了一個純 C 的 deque,並與系統 CFArray 做效能比較,發現隨機插入時系統版本仍有更高效能。當我把 deque 換成 circular 後再比較,效能就完全一致了。因此我推測,目前系統的 CFArray 底層應該又換成了 circular。

我的實現代碼放在 https://github.com/ibireme/yy_array ,裡面有一個純 C 的簡單引用計數對象實現,以及 CFMutableArray 與 CFMutableDictionary 的模仿實現,所有 API 都與 CoreFoundation 類似。

下圖是我自己的實現與 CFArray 的效能對比,除去隨機數影響,插入效能應基本一致。

結論

回頭看蘋果對時間複雜度的官方描述:訪問值的時間最壞為 O(lg N),但通常為 O(1);線性搜尋最壞為 O(N·lg N);插入刪除通常與元素數量線性相關,最壞情況某些實現下為 O(N·lg N)。同時蘋果強調,陣列內並沒有「性能偏好位置」。

用開頭那篇博客的話總結最合適:Don't second guess Apple, because Apple has already second guessed YOU.(別試圖超越蘋果的判斷,因為蘋果早已替你想過了。)

另外補充一個常被誤解的小知識:[NSMutableArray arrayWithCapacity:xxx] 中的 capacity 參數其實沒有實際作用,它僅僅是一個提示(hint)而已。

原文地址:https://blog.ibireme.com/2014/02/17/cfarray/

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved