A slice is not an array. Words to live by. 

> On May 26, 2021, at 7:37 PM, Kurtis Rader <kra...@skepticism.us> wrote:
> 
> 
> It's more likely you've misunderstood how slices work. From 
> https://golang.org/ref/spec#Slice_types:
> 
> > A slice is a descriptor for a contiguous segment of an underlying array and 
> > provides access to a numbered sequence of elements from that array.
> 
> If you still believe you've found a bug we'll need the smallest reproducer 
> you can provide.
> 
>> On Wed, May 26, 2021 at 5:27 PM John Olson <johnforestol...@gmail.com> wrote:
>> I have a recursive function that seems to be reusing memory it shouldn't. 
>> I'm developing in Goland 2021.1.1 with go version 1.16.2.
>> 
>> I've written a function to generate the partitions of an integer. The 
>> partitions of n are all the sets of integers that add up to n, so the 
>> partitions of 3 are {3}, {2,1} and {1,1,1}. As n grows, the number of 
>> partitions grows exponentially (to be precise, as e^(n^½)). I wrote a 
>> recursive function, which works great up to n=7. At n=8, one of the 
>> partitions is {2,2,2,1}, which is obviously wrong; and since the function is 
>> recursive, every subsequent n is wrong, too.
>> 
>> I just spent quite a long time stepping through the code, and I found that 
>> what seems to be happening is that a slice declared in my recursive function 
>> is being reused in two different recursions. Specifically, my function 
>> declares
>> var temp [][]int
>> to build up the list of partitions. When I compute Partitions(8), I have to 
>> compute Partitions(4), 5, 6 and 7. I memoize each set of partitions so I 
>> only have to compute them once.
>> 
>> It all goes wrong when I'm working on Partitions(7). At this point, 
>> Partitions(8) has already added 6 cases, the last of which is {2,2,2,2}. 
>> This is stored in temp[5], the temp corresponding to n=8, of course. Then I 
>> compute Partitions(7), which should create a new temp [][]int; I'll call 
>> this temp//7. temp[6]//7 gets {2,2,2,1}, and at that point temp[5]//8 
>> changes from {2,2,2,2} to {2,2,2,1}. The addresses of temp[6]//7 and 
>> temp[5]//8 are different, but the addresses of the elements of these slices 
>> are the same.
>> 
>> This has to be wrong.
>> 
>> I suspect a bug in go, but I suppose it's possible there's a bug in goland. 
>> I'm running on macOS 11.3.1, just in case that's relevant.
>> 
>> I'm happy to share the source code if anyone is interested.
>> 
>> Thanks,
>> 
>> 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.
>> To view this discussion on the web visit 
>> https://groups.google.com/d/msgid/golang-nuts/fb9031ba-bfa0-4c92-9cb7-6ad3a8781184n%40googlegroups.com.
> 
> 
> -- 
> Kurtis Rader
> Caretaker of the exceptional canines Junior and Hank
> -- 
> 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.
> To view this discussion on the web visit 
> https://groups.google.com/d/msgid/golang-nuts/CABx2%3DD-vkk_aOtNk%3D4woXcwDRy8_-pyeRu9NnRKF9beuOFSYTw%40mail.gmail.com.

-- 
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.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/golang-nuts/92F4E6ED-F7E2-4548-A4AA-014827E64353%40ix.netcom.com.

Reply via email to