I haven't tried it out, but I think it will work because each new slot is hit twice: it is filled with data, and it is copied away again. So when you expand from n to 2*n, you may be able to arrange that you have exactly n credits in the bank which can be used to pay for the copy. This might require you to have 2 credits per slot though. If it works out, I'm pretty sure this is the way to attack them problem.
(Mind you, I haven't done it with rigor, so I might be wrong). On Sun, Nov 12, 2017 at 5:01 PM Bakul Shah <ba...@bitblocks.com> wrote: > On Sun, 12 Nov 2017 15:45:40 +0000 Jesper Louis Andersen < > jesper.louis.ander...@gmail.com> wrote: > > > > 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. > > It will be worse than O(n), right? Old elements have to be > likely copied the new bigger slice. > > > 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. > > If you allocate 50% more space each time (or use fibonacci > factor), allocation is still exponential in nature but wastes > less space. For the loop case it is better to use loop count > as an allocation hint. [For expanding a map similar > considerations but you have to expand it at 2/3 full capacity > or so] > -- 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.
