Ruby中Array.new（n，x）的複雜性是什麼？

Question

聲明具有初始大小和默認值的數組的運行時間是多少？

Answer 1

關於小數組和線性之後的常量。

require 'benchmark' 

0.upto(9).each do |power| 
    elements = 10 ** power 
    time = 10.times.map { Benchmark.measure { Array.new(elements, :foo) } }.sum(&:real)/10 
    p [elements, '%f' % time] 
end 

# [1, "0.000001"] 
# [10, "0.000001"] 
# [100, "0.000002"] 
# [1000, "0.000011"] 
# [10000, "0.000038"] 
# [100000, "0.000286"] 
# [1000000, "0.004231"] 
# [10000000, "0.036348"] 
# [100000000, "0.404822"] 
# [1000000000, "8.454289"] 

作爲一個直觀的解釋：

它基本上分配一個連續存儲器塊（*）和在存儲器每一個別塊（一個寫入對象的表示（指針）塊是一個數組元素）。對每個塊進行迭代都會導致線性複雜性。

---

請注意，對於小內存塊可能會有一些優化，使其保持不變。

（*）對於較大的塊，塊可能不連續，這會導致更差的性能。

---

所有這些比Ruby的實現本身更可能更依賴硬件/操作系統。