algorithm - 哪种排序和唯一顺序更快？

Question

例如在朱莉娅

julia> sort(unique([1,2,3,2,1]))
3-element Array{Int64,1}:
 1
 2
 3

julia> unique(sort([1,2,3,2,1]))
3-element Array{Int64,1}:
 1
 2
 3

哪个订单更快？为什么？

标签： algorithmsortingunique

Answer 1

根据文档，Julia 使用QuickSort作为数字输入的默认值。这是一个n log n操作。

Unique 在时间和空间上都具有 O(n) 的复杂性。

现在，考虑 10000 个数字的小输入。

案例 1： 假设其中只有 1000 个是唯一的。

假设您运行，sort(unique(arr))那么您基本上只会对 1000 个数字进行排序，unique(sort(arr))而您将在其中对 10000 个数字进行排序。

案例 2： 假设所有 10000 个都是唯一的。现在，两者之间的性能没有显着变化，因为排序函数采用了所有 10000 个值。

所以，这完全取决于输入。但是使用它是有意义的sort(unique(arr))。