Array.sort 对比 Array.take(x).sort 性能

Question

我有一个包含 3000 个数字的数组。

用户抓取一个号码，然后在接下来的 5 秒内任意时间将其放回。

我希望用户每次都取数组中最小的数。

高峰时最多有100人同时抢号和换号。 select 前 100 个并对它们进行排序，而不是对整个数组进行排序，这样会更便宜吗？

我使用 Rails serialize 在 PostgreSQL 中使用 YAML

存储我的数组

Answer 1

大多数排序算法的复杂性平均而言是严格单调增加的，相对于数组的长度（n、n log n、n^2、n n! 等）。特别是，Ruby 似乎使用了快速排序，即 n log n。因此，对 3000 项的数组进行排序比对 100 项的数组排序成本更高。

Answer 2

I want users to take the smallest number in the array every time (...) would it be less expensive to select a range of numbers, and just sort that portion?

它将return该范围中的最小数字，但不是数组中的最小数字：

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]

I am storing my array using Rails serialize in PostgreSQL with YAML

对包含 3,000 个数字的 Ruby 数组进行排序用时不到一毫秒。反序列化 YAML 字符串慢很多。

Array.sort 对比 Array.take(x).sort 性能

Array.sort vs Array.take(x).sort Performance

ruby

arrays

postgresql

performance