That's really interesting. I'd always assumed (without really thinking more deeply about it) that amortised appending to a slice was O(n*log(n)). Here's an empirical demonstration, FWIW: https://play.golang.org/p/iLGiyexo1A
On 12 November 2017 at 17:56, Bakul Shah <ba...@bitblocks.com> wrote: > On Sun, 12 Nov 2017 17:41:18 +0000 Jesper Louis Andersen > <jesper.louis.ander...@gmail.com> wrote: >> >> 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. > > You're right. I was going by the observation that earlier > values will be copied more times than later values but > reallocs happen less and less frequently as can be seen > in the following: > > 0 1 2 3 4 5 6 7 > 1 + > 2 + + > 4 + + + + > 8 + + + + + + + + > > So 2n-1 writes. > > -- > 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.
