有没有一种方法可以在数组中添加尾部比在F#中附加更有效？

Question

我目前正在尝试构建一个程序,其中我有一个递归函数,每个循环都将一个新元素附加到它正在构建的数组中.我不想多次使用append函数,因为我的函数应该执行大量的循环,并且我已经从以前的经验中学习了追加函数通常需要花费很多时间.我试图到处寻找一个只是在数组尾部添加一个元素的函数,但我没有发现这种类型.所以我想我会问这里.

所以我的问题基本上是:"有没有比使用append更有效的方法在数组后面添加一个元素？"

---

更新了有关上一个问题的新问题

所以我使用了一个列表,将每个新元素作为头部插入,并在函数完成时恢复列表.这使得该功能快了约70倍.但问题仍然存在,因为我有另一个功能几乎相同,大约慢了4倍,增加了我的主要功能的总时间.功能非常相似.第一个函数(变得更快的函数)生成整数,将每个新int添加到列表中.第二个函数(变慢的函数)生成一个对象,将每个新对象添加到列表中.有没有人知道为什么一个功能变得如此快,而另一个功能变得如此之慢？

Answer 1

ResizeArray是此任务的更有效的数据结构,例如:

let filterRange predicate (i, j) =
    let results = ResizeArray(j-i+1)
    for k = i to j do
        if predicate k then results.Add(k)
    results.ToArray()

来自F#PowerPack的ResizeArray模块提供高阶函数以便ResizeArray以功能方式进行操作.但是,请注意这些函数会创建新的ResizeArray实例,这使得它们的效率低于.NET方法.

一个纯函数的替代方法是使用一个列表作为累加器,将元素添加到累加器,反转它(如果顺序很重要)并在最后转换为Array:

let filterRange predicate (i, j) =
    let rec loop k acc =
        if k = j+1 then acc
        elif predicate k then loop (k+1) (k::acc)
        else loop (k+1) acc
    loop i [] |> List.rev |> Array.ofList

Answer 2

我建议使用列表而不是数组.如果你真的需要数组中的最终结果,你可以在进程结束时将列表转换为数组 - 它仍然会更快.