Array.sort vs Array.take（x）.sort性能

Question

我有一個3000數組的數組。

用戶抓取一個數字，然後在隨後的5秒內將其放回任意時間。

我希望用戶每次都在數組中取最小的數字。

在高峯期，最多可有100人同時抓取和更換號碼。與排序整個陣列相比，選擇前100個並對它們進行排序會更便宜嗎？

我使用的Rails PostgreSQL中serialize與YAML

存儲我的數組

Answer 1

的最排序算法的複雜性是嚴格單調相對於增加至所述陣列的長度（N，N-日誌N，N^2，NN！等）。特別是，Ruby似乎使用快速排序，它是n log n。因此，對3000個項目進行排序比對100個項目進行排序要昂貴。

Answer 2

我希望用戶每次取數組中最小的數字（...）選擇一個數字範圍並將這個部分排序是否便宜？

這將返回最小數該範圍內，而不是在陣列中最小的數字：

arr = [7, 3, 5, 10, 2, 8, 6, 1, 9, 4] 

arr.take(3).sort #=> [3, 5, 7] 
# vs 
arr.sort.take(3) #=> [1, 2, 3] 

我儲存使用Rails serialize PostgreSQL中我的陣列YAML

使用3000個數字對Ruby數組排序需要不到一毫秒的時間。反序列化YAML字符串是太慢了。