4 ms·
As long as there is a non-zero multiplier, it does not matter the size of the constant factor, and it does not even need to be constant. I spent a while recentl
by manwe150 5y ago
As long as there is a non-zero multiplier, it does not matter the size of the constant factor, and it does not even need to be constant. I spent a while recently looking at the shape of this non-typical allocation growth curve, which ended up going with `n₁ = n₀ + 4n₀^(7/8) + n₀/8` using only integer math:
// compute maxsize = maxsize + 4*maxsize^(7/8) + maxsize/8
// for small n, we grow faster than O(n)
// for large n, we grow at O(n/8)
// and as we reach O(memory) for memory>>1MB,
// this means we end by adding about 10% of memory each time
And was graphed, discussed, and approved here:
https://github.com/JuliaLang/julia/pull/40453/files#diff-fb625ea37f59dbae7d0f5e5f7b70b887b9785a354179fab07eb4d2083fdb51b4R766-R772 https://github.com/JuliaLang/julia/pull/40453/files#diff-fb6...
- _dain_ 5y agoPython is similar[1] >The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... https://github.com/python/cpython/blob/3.7/Objects/listobject.c#L55 https://github.com/python/cpython/blob/3.7/Objects/listobjec...