NSMutableArray是否真的是堆棧或隊列的良好後備存儲？

我已經讀過NSMutableArray將會有O（1）性能，而不是O（n）當元素從陣列的末端添加/刪除（例如removeAtObject:0或removeLastObject），這使得它適合用作堆棧或隊列 - 否定需要爲這些容器類型創建LinkedList實現。NSMutableArray是否真的是堆棧或隊列的良好後備存儲？

這是真的嗎？如果是這樣，蘋果如何設法做到這一點？如果不是，是否有任何證據表明，隨着陣列中元素數量的增加，添加/刪除元素在NSMutableArray實例末端所花費的時間會增加？ PS：由於NSMutableArray基本上是CFArray（它是「純C」對應物）和the source code to CFArray is open，應該有可能檢查它的內部工作。

來源

2013-04-27 adib

我不知道什麼是精確的性能點 - 我懷疑它總是O（1），但實現是「聰明」和我懷疑它使用了一系列鏈接的數組來使性能相當「穩定」。 – 2013-04-27 13:24:25

鏈接列表具有較差的引用和分段屬性的位置。如果沒有它們，可以實現攤銷O（1）。 – 2013-04-27 17:20:18

一些經驗性的探索：http://ridiculousfish.com/blog/posts/array.html – 2013-04-27 18:23:07

_NSArrayM（其被用來代替CFArray對於大多數NSArrays）是目前的陣列雙端隊列，它確實提供攤銷O（1）壓入/彈出兩端

（這是不能保證是這樣在任何過去或未來的操作系統版本。NSArrayM本身是相當新的例如）

來源

2013-04-27 17:18:13

關於這方面的任何可證實的證據/測試結果？ – adib 2013-05-01 13:34:56

你可以嘗試用Hopper來分解它。否則，恐怕不是。我的NDA阻止我提供太多。 – 2013-05-01 15:38:47

順便說一句，你從這篇博客文章的源代碼丟失：http://ridiculousfish.com/blog/posts/array.html - 照顧把它放在Github上？提前致謝。 – adib 2013-05-02 02:28:55

CFArray/CFMutableArray（通過擴展，NSArray/NSMutableArray）有非常寬鬆的性能保證---他們肯定不保證O（1）插入/刪除的性能。

從CFArray.h（強調）：

計算複雜
的存取時間爲所述陣列中的值被保證是在最壞的情況O（LG N）用於任何實施方式中，當前和未來，但通常是O（1）（恆定時間）。線性搜索類似地具有O（N * lg N），的最壞情況複雜度，儘管通常邊界將更緊密，等等。插入或刪除操作將典型地在陣列中的值的數目中是線性的，但在一些實現中可能清楚地在最壞情況下爲O（N * 1g N）。表現中陣列中沒有優勢位置;也就是說，訪問具有較低索引的值或插入或刪除具有較高索引的值或無論如何不一定更快。

核心基金會/基金會目前沒有提供任何模擬鏈接表的性能的數據結構。

來源

2013-04-27 15:07:22

可能值得使用Obj-C++，並且如果數據存儲獨立使用（即，不用作樹/數組控制器的後備存儲），則可以使用任何STL/boost容器。

來源

2013-04-27 15:57:27

NSMutableArray是否真的是堆棧或隊列的良好後備存儲？

回答

相關問題