CODEWITHSUNDEEP
julia
ThatsRightJack
ThatsRightJack

Reputation: 751

Nondeterministic growth in Julia loop

I have a computation loop with adaptive time stepping and I need to store the results at each iteration. In other words, I do not know the vector size before the computation, so I can not preallocate a vector size to store the data. Right now, I build a vector using the push! function

function comp_loop()
    clock = [0.0]
    data = [0.0]
    while run_time < model_time
    
        # Calculate new timestep
        timestep = rand(Float64)  # Be sure to add Random
        run_time += timestep
    
        # Build vector
        push!(clock,run_time)
        push!(data,timestep)
        
    end
end

Is there a more efficient way to go about this? Again, I know the optimal choice is to preallocate the vector, but I do not have that luxury available. Buffers are theoretically not an option either, as I don't now how large to make them. I'm looking for something more "optimal" on how to implement this in Julia (i.e. maybe some advanced application available in the language).

Upvotes: 1

Views: 52

Answers (1)

phipsgabler
phipsgabler

Reputation: 20960

Theoretically, you can use a linked list such as the one from DataStructures.jl to get O(1) appending. And then optionally write that out to a Vector afterwards (probably in reverse order, though).

In practise, push!ing to a Vector is often efficient enough -- Vectors use a doubling strategy to manage their dynamic size, which leads to amortized constant time and the advantage of contiguous memory access.

So you could try the linked list, but be sure to benchmark whether it's worth the effort.

Now, the above is about time complexity. When you care about allocation, the argument is quite similar; with a vector, you are going to end up with memory proportional to the next power of two after your actual requirements. Most often, that can be considered amortized, too.

Upvotes: 3

Related Questions