如何是陣列設置和紅寶石

Question

引擎蓋下實現SortedSets通常數組實現爲一個內存塊，設置哈希地圖，和分類集作爲跳錶。 Ruby中也是這樣嗎？

我試圖評估性能和內存佔用方面使用Ruby中不同的容器

Answer 1

數組是Ruby的核心庫的一部分。每個Ruby實現都有自己的數組實現。 Ruby語言規範只規定了Ruby數組的行爲，它沒有指定任何特定的實現策略。它甚至沒有指定任何會強制或至少暗示特定實施策略的性能限制。

然而，大多數Ruby開發者有關於陣列，這將迫使不符合他們默默無聞到實現的性能特性的一些期望，因爲沒有人會真正使用它：

• 插入，前面加上或追加爲以及刪除元素爲O（n）的最壞情況下的步驟複雜和O的攤銷最壞情況下的步驟複雜度（1）
• 訪問一個元件爲O的最壞情況下的步驟複雜度（1 ）
• 遍歷所有元素爲O（n的最壞情況下的步驟，複雜性）

這意味着陣列需要實現與指數調整大小動態數組，否則那些履約擔保無法得到滿足。你可能擺脫一個非常廣泛和淺的樹，但AFAIK沒有Ruby實現那樣做。

這裏的Rubinius's array implementation，這是我個人認爲最簡單的讀取所有Ruby實現的。 （注意：只有最基本的要素是用C++實現的，大多數數組方法都是用Ruby實現的，例如在kernel/common/array.rb中）。

Set和SortedSet是stdlib中set庫的一部分。 stdlib在Ruby實現之間大部分是共享的（至少實際上用Ruby編寫的部分，顯然是用其他語言編寫的部分不能共享），並且由於Set是用Ruby編寫的，所以您可以期望它相同在所有Ruby實現上。

Set是作爲Hash實現的，其中僅使用密鑰，其值始終爲true：請參閱Set#add in lib/set.rb。

SortedSet由不Ruby實現紅黑樹的支持。

Answer 2

上一個答案實際上並沒有涵蓋SortedSet的性能。

• 陣列 - O（1），用於添加，刪除和通過索引接入元件
• 哈希（使用哈希表） - O（1）（大當然1，大於陣列），用於添加，刪除，和通過關鍵
• 設置訪問 - 通過哈希所以同樣
• SortedSet的實現：

所以閱讀代碼，並使用其每計數比較方法調用類人工測試後，這裏的結果。 它試圖加載'rbtree'模塊並使用常規Set作爲後備。

所以2種選擇：

1. RBTree可用，一切都快速，符合市場預期，對每一個除了O（logN）的，O（1）首先得到，O（N）上soeted_set.to_a。
2. RBTree不可用。它使用Set（哈希底下）和重新排序如果閱讀髒。

從紅寶石2.0.0 set.rb：

def to_a 
    (@keys = @hash.keys).sort! unless @keys 
    @keys 
end 

含義在於以下代碼：

X.times{ sorted_set << num; sorted_set.first } 

將O（XNlog（N）），由於訂貨是近似NLOG（ N）。

因此，基本上使用SortedSet而不確定RBTree是否可用是令人困惑和低效的，因爲它沒有使用插入時排序（二進制搜索）的事實。 因此，在這種情況下使用普通的Set和數組方法可能會更快。使用常規設置

同例如：

X.times{ set << num; set.min } 

將是O（XN）

底線，如果你需要SortedSet的工作效率，還可以添加 'rbtree' 到Gemfile中。