5

我目前正在尝试构建一个程序，其中我有一个递归函数，该函数对于每个循环都将一个新元素附加到它正在构建的数组中。我不想多次使用 append 函数，因为我的函数应该做大量的循环，而且我从以前的经验中了解到 append 函数通常需要很多时间。我试图到处寻找一个简单地将一个元素添加到数组尾部的函数，但我没有找到这种类型。所以我想我会在这里问。

所以我的问题基本上是：“有没有比使用追加更有效的方法将一个元素添加到数组的后面？”

更新了一个关于前一个问题的新问题

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

4

3 回答 3

10

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
于 2012-04-09T14:13:00.453 回答
6

我建议使用列表而不是数组。如果您确实需要数组中的最终结果，您可以在过程结束时将列表转换为数组 - 它仍然会更快。

于 2012-04-09T14:15:02.310 回答
3

不，您可能想要使用不同的数据结构。

于 2012-04-09T13:56:32.413 回答