近似運行比較

Question

想象一下，你有一堆NSArrays的。數組都包含包裹在NSValues中的CGPoints。所有的元素都不是唯一的。所以某些元素可以出現在多個數組中。 將這些數組組合成單個數組的最快方式是什麼？這樣得到的數組只包含獨特的元素？

目前我正在做這樣的：

1. 將每個陣列爲NSSet中使用setByAddingObjectsFromArray
2. 裝滿集的內容

結果數組另一種選擇是這樣的：

1. 遍歷每個數組一次，並插入每個值int Ø一個NSDictionary（如果它不存在的話）
2. 遍歷字典的鍵一次，每次插入結果數組

傳統的運行時分析說，第一個選項應與O(n log n)規模，其中n是多少所有初始數組中的元素（遍歷所有元素，並將每個元素插入二進制搜索樹或類似的日誌時間）。對於第二種方法，運行時爲O(n)，因爲哈希表中的查找和插入以分攤的恆定時間運行。然而，在閱讀了關於蘋果數據結構的一些信息之後，假設它們像傳統數據結構一樣行事似乎是愚蠢的。

Answer 1

由於這兩種方法將介於O(n)和O(n log n)和你N的可能非常小，log n爲界，小，恆因素可能決定其中哪些是最快的。

在這一點上，與看起來像你的用例的數據實際上標杆是做的最好的事情。

我相信，但我不能肯定，認爲NSSet中與哈希實現好。

Answer 2

其實...我認爲，時間將相差無幾，但在NSDictionary中的情況下，你會得到一個位的內存開銷，因爲在這種情況下，你將需要密鑰複製到NSDictionary中。 他們兩個NSDictionary和NSSet相同的工作方式：

1. hash被檢查uniquness
2. 如果兩個項目具有相同的高速緩存，isEqual獲取調用

有在做法上沒有大的區別，你提到過。