5

I am currently trying to build a program where I have a recursive function that for every loop appends one new element to the array it is building. I didn't want to use the append function that many times, because my function is supposed to do a large number of loops, and I've come to learn from previous experiences that the append function in general takes a lot of time. I've tried to look everywhere for a function that simply adds one element to the tail of the array, but I've found nothing of such sort. So I was thinking I would ask here.

So my question is basically: "Is there a more effective way of adding one element to the back of an array than using append?"

Updated with a new question regarding the previous one

So I used a list instead, inserting each new element as a head, and reverted the list when the function was finished. This made the function about 70 times faster. But the problem remains as I have another function that does pretty much the same, which became about 4 times slower, increasing the overall time for my main function. The functions are very similar. The first function (the one that became much faster) produces ints, adding each new int to the list. The second function (the one that became much slower) produces an object, adding each new object to the list. Does anyone have an idea why one function became so much faster while the other one became so much slower?

Marcus Åberg
  • 213
  • 2
  • 10
  • 1
    You should open a new question and include more details of your functions. You will get detailed answers if you do so. – pad Apr 23 '12 at 06:19

3 Answers3

10

ResizeArray is a more efficient data structure for this task, for example:

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()

ResizeArray module from F# PowerPack provides high-order functions to manipulate ResizeArray in a functional way. However, beware that these functions create new ResizeArray instances which make them less efficient than .NET methods.

A purely functional alternative is to use a list as an accumulator, prepend elements to the accumulator, reverse it (if the order matters) and convert to Array in the end:

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
pad
  • 41,040
  • 7
  • 92
  • 166
  • Unfortunately the ResizeArray module in the powerpack creates a new `ResizeArray` instance for each method instead mutating the one you pass in, so it's not an efficiency savings over creating new arrays with the Array module. – ildjarn Apr 09 '12 at 18:25
  • @ildjarn The module indeed does, but what about the standard .Net methods? I really doubt `.Add(_)` creates a new `ResizeArray`. – Ramon Snir Apr 09 '12 at 18:54
  • @Ramon : Correct, `Add` doesn't, and the code demonstrated here is fine. I only meant to point out that the ResizeArray _module_ isn't helpful at all when efficiency is a concern. – ildjarn Apr 09 '12 at 18:55
  • @ildjarn: Thanks, I update my answer based on your suggestion. – pad Apr 09 '12 at 19:39
  • Just wanted to say that I improved my first function a lot by using a list instead and adding the new elemenet as a head and then reversing the list when the function is completed. The function became about 70 times faster this way! – Marcus Åberg Apr 22 '12 at 19:26
6

I'd suggest to use a list instead than an array. If you really need the final result in an array you can convert the list to an array at the end of the process - it will still be faster.

MiMo
  • 11,793
  • 1
  • 33
  • 48
3

No. You may want to use a different data structure.

Ramon Snir
  • 7,520
  • 3
  • 43
  • 61