F# 中的排名函数

Question

我写了一个排序数组的算法。

let rankFun array =
    let arrayNew = List.toArray array
    let arrayLength = Array.length arrayNew
    let rankedArray = Array.create arrayLength 1.0
    for i in 0 .. arrayLength - 2 do
        for j in (i+1) .. arrayLength - 1 do
            if arrayNew.[i] > arrayNew.[j] then
                rankedArray.[i] <- rankedArray.[i] + 1.0

            elif arrayNew.[i] < arrayNew.[j] then
                rankedArray.[j] <- rankedArray.[j] + 1.0

            else 
                rankedArray.[i] <- rankedArray.[i] + 0.0
    rankedArray

我想问你，你对性能有什么看法？我使用了 for 循环，我想知道您是否认为还有比这更好的方法。在开始之前，我正在对数组进行排序，保留原始索引、排名，然后才将每个排名恢复到其原始位置，这在性能方面确实很糟糕。现在我得到了这个改进的版本并正在寻找一些反馈。有什么想法吗？

编辑：重复的元素应该有相同的等级。 ;)

非常感谢您。 :)

Answer 1

我假设运行ks 可以从对输入进行排序中获取，因为您评论说该问题对重复项的行为是一个错误。令人惊讶的是，您描述的排序解决方案运行比问题中显示的代码慢。应该会快很多。

通过排序解决此问题的一种简单方法是从所有值构建一个有序集。 F# 中的集合始终有序且不包含重复项，因此它们可用于创建运行king。

从集合中，创建一个从每个值到其在集合中的索引的映射（加一，以保留以 1 开头的运行king）。这样，您可以查找每个值的运行k 以填充输出数组。

let getRankings array =
    let rankTable =
        Set.ofArray array
        |> Seq.mapi (fun i n -> n, i + 1)
        |> Map.ofSeq
    array |> Array.map (fun n -> rankTable.[n])

这需要一个数组，而不是一个列表，因为问题中的输入参数称为 array。它还为运行ks 使用整数，因为这是用于此目的的普通数据类型。

这比原来的算法快多了，因为所有操作至多为 O(n*log(n))，而问题中的嵌套 for 循环为 O(n^2)。（另请参阅：Wikipedia on Big O notation。）对于仅 10000 个元素，基于排序的解决方案在我的计算机上的运行速度已经快了 100 多倍。

（顺便说一句，语句 else rankedArray.[i] <- rankedArray.[i] + 0.0 似乎什么也没做。除非你在用优化器做某种黑魔法，否则你可以删除它。）

F# 中的排名函数

Ranking Function in F#

arrays

f#

ranking