`O(n)` insertion time

[LilithHafner]

There are cases where construction is O(n^2) (meaning O(n) amortized insertion time):

This happens when the values span a large number of levels. I suspect that this could be O(1) insertion time by not calling sortperm! every time a new level is added.

julia> function build_coin_flip(n)
           ds = DynamicSampler()
           for i in 1:n
               push!(ds, i, 0.5^i)
           end
           ds
       end
build_coin_flip (generic function with 1 method)

julia> x = 1:100;

julia> y = [(@b xi build_coin_flip seconds=.01).time for xi in x];

julia> plot(x,y)

julia> plot!(x, 1.2e-9x.^2 .+ 8e-8x)

julia> savefig("fig.png")

[Tortar]

yes, indeed this can be avoided by removing the sortperm!, just thinking if removing it can have some bad effects on performance, probably if the criterion of reordering is improved than we can get the best of both worlds

[Tortar]

Ok should be fixed by #25 , now: