To elaborate on Jan's point: If you extended capacity every time you called append, then you will have to reallocate and copy data quite a lot. So a clever system pushes a little bit more capacity in at the end to avoid such copies whenever an append happens. It is a trade-off between space usage and processing time. From a complexity-point of view, you are amortizing the capacity allocation over several appends which yields better (amortized) complexity, turning O(n^2) into O(n). A proof sketch: associate a credit invariant (or potential) with the excess capacity and note it never goes below 0.
Typically, systems runs exponentially up to a point and then start using something different, when the added power of two becomes too large. Either you extend by a constant amount, or you extend by a fibonacci factor, depending on runtime. In short: you start trading the other way once the space usage grow too large. The optimization is there to handle the common case: extend a slice with a small set of data in some loop. On Sun, Nov 12, 2017 at 1:31 PM Lucio <lucio.d...@gmail.com> wrote: > One could lie about it, I suppose, but then you'd need to have an > additional (hidden) value and that certainly does not seem worth it. > > Lucio. > > On Sunday, 12 November 2017 13:39:59 UTC+2, Jan Mercl wrote: > >> On Sun, Nov 12, 2017 at 12:00 PM <k1at...@gmail.com> wrote: >> >> > The question is capacity. >> > Why not : 0,1,2,3,4,5 as length ? >> >> Because O(n) is better than O(n^2). >> >> -- >> >> -j >> > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
