FAQ

On 2012/10/10 Matt Conrad wrote:
Hi, I'm trying to enumerate all the combinations from rolling a dice
repeatedly, with an arbitrary number of rolls.

http://play.golang.org/p/LBhxle3WM_

[...]

Oddly, if I add a 5th roll, the last element starts iterating again (next to
last element is still broken).

I've studied on it for a while and can't figure it out. I must be misusing
slices somehow, but I'm not seeing it. Two questions:

a) what the heck is wrong here?
append(oldseries, die) may refer to the same piece of memory as oldseries.
Then the loop of dice may actually mutate a single array instead of
producing slices.
b) I bet there is a nicer way to permute a slice against another slice than
all this new/old/series/combined stuff. Please show me the way.
I prefer this way of doing: http://play.golang.org/p/IzaqT9y8q1
I think it is also more memory-efficient if you need to generate a lot
of dice rolls.

Rémy.

--

Search Discussions

  • Matt Conrad at Oct 10, 2012 at 9:56 pm
    Hi, I'm trying to enumerate all the combinations from rolling a dice
    repeatedly, with an arbitrary number of rolls.

    http://play.golang.org/p/LBhxle3WM_

    In the example I'm using a 3 sided die. So rolling once gets you 3
    possibilities [1, 2, 3], rolling twice gets you 9 [[1, 1], [1, 2], [1, 3],
    [2, 1] etc], three rolls would have 27 combinations, etc.

    I'm keeping track of these results as a slice of slices, where each
    iteration (roll) permutes the original set of slices against each dice
    possibility. Even if this is not the optimal way to solve this problem, I'd
    like to understand the bug and get it to work.

    Something is wrong with my logic. If we simulate 4 rolls, something goes
    wrong on the fourth roll, and the final element is not iterating the way it
    should, instead it's always the last value:

    newseries: [[1 1 1 3] [1 1 1 3] [1 1 1 3]]
    newseries: [[1 1 2 3] [1 1 2 3] [1 1 2 3]]

    should be

    newseries: [[1 1 1 1] [1 1 1 2] [1 1 1 3]]
    newseries: [[1 1 2 1] [1 1 2 2] [1 1 2 3]]

    Oddly, if I add a 5th roll, the last element starts iterating again (next
    to last element is still broken).

    I've studied on it for a while and can't figure it out. I must be misusing
    slices somehow, but I'm not seeing it. Two questions:

    a) what the heck is wrong here?
    b) I bet there is a nicer way to permute a slice against another slice than
    all this new/old/series/combined stuff. Please show me the way.


    --
  • Matt Conrad at Oct 10, 2012 at 11:34 pm

    On Wed, Oct 10, 2012 at 4:21 PM, Rémy Oudompheng wrote:
    On 2012/10/10 Matt Conrad wrote:

    http://play.golang.org/p/LBhxle3WM_
    a) what the heck is wrong here?
    append(oldseries, die) may refer to the same piece of memory as oldseries.
    Then the loop of dice may actually mutate a single array instead of
    producing slices.
    I tried making the append to oldseries an explicit temporary variable
    and watching what happened.

    http://play.golang.org/p/z0MCwq45EZ

    The append to newseries is behaving wrongly:

    extendold: [1 1 1 1] //correct
    partial newseries: [[1 1 1 1]]
    extendold: [1 1 1 2] //correct
    partial newseries: [[1 1 1 2] [1 1 1 2]] // ?!?! wrong, we
    append *and* modify earlier element?
    extendold: [1 1 1 3] //correct
    partial newseries: [[1 1 1 3] [1 1 1 3] [1 1 1 3]] // also wrong
    newseries: [[1 1 1 3] [1 1 1 3] [1 1 1 3]]

    You were saying the append might mutate the array, here it seems to be
    both appending, and mutating the previous element, in the same step.

    I don't understand why "newseries = append(newseries, extendold)" is
    doing this.

    I guess all 3 references in newseries are really to the same extendold
    slice? Which is only the newest version of extendold--even though
    extendold is being reallocated each time? Clearly this is not
    happening every time, most of the permutations work correctly.

    Can you show me the correct way to do this append so the reference is
    not reused (if that is in fact what is happening)? Mostly I am
    concerned with understanding what I am doing wrong here so I don't get
    bitten by something similar in the future. This behavior is thoroughly
    confusing and surprising to me.
    b) I bet there is a nicer way to permute a slice against another slice than
    all this new/old/series/combined stuff. Please show me the way.
    I prefer this way of doing: http://play.golang.org/p/IzaqT9y8q1
    I think it is also more memory-efficient if you need to generate a lot
    of dice rolls.
    That is nicer and cleaner (and accurate!). I'll take some time and digest it.

    Thanks for the help Remy.

    --
  • Rémy Oudompheng at Oct 10, 2012 at 11:11 pm

    On 2012/10/11 Matt Conrad wrote:
    You were saying the append might mutate the array, here it seems to be
    both appending, and mutating the previous element, in the same step.

    I don't understand why "newseries = append(newseries, extendold)" is
    doing this.
    It happens whenever the capacity of newseries is large enough.
    I guess all 3 references in newseries are really to the same extendold
    slice? Which is only the newest version of extendold--even though
    extendold is being reallocated each time? Clearly this is not
    happening every time, most of the permutations work correctly.
    The capacity grow in unspecified ways. At some time you can append one
    element but the reallocation makes the capacity grow by more than 1.
    Can you show me the correct way to do this append so the reference is
    not reused (if that is in fact what is happening)?
    It's essentially not possible. You would need to create a full copy
    each time, which is very inefficient.
    b) I bet there is a nicer way to permute a slice against another slice than
    all this new/old/series/combined stuff. Please show me the way.
    I prefer this way of doing: http://play.golang.org/p/IzaqT9y8q1
    I think it is also more memory-efficient if you need to generate a lot
    of dice rolls.
    That is nicer and cleaner (and accurate!). I'll take some time and digest it.

    Thanks for the help Remy.
    Rémy.

    --
  • Matt Conrad at Oct 11, 2012 at 12:58 am

    On Wed, Oct 10, 2012 at 6:11 PM, Rémy Oudompheng wrote:
    On 2012/10/11 Matt Conrad wrote:
    Can you show me the correct way to do this append so the reference is
    not reused (if that is in fact what is happening)?
    It's essentially not possible. You would need to create a full copy
    each time, which is very inefficient.
    Ugh. Well, that, at least, helps me understand my error.

    Am I right then that my mistake was fundamentally this: modifying a
    reference type, and then using the modified version as if it were a
    new allocation separate from the earlier version?

    To go further: even though it seemed to be working most of the time,
    this was basically a fluke having to do with the way space for slices
    is extended?

    --
  • Rory McGuire at Oct 11, 2012 at 6:18 am
    Perhaps if you had sent the cap on the initial assignment to a large number you could have checked if it was in fact because of capacity allocation?
    Looks like you fixed the original so I can't test.

    --
  • Matt Conrad at Oct 11, 2012 at 11:42 pm

    On Thu, Oct 11, 2012 at 1:18 AM, Rory McGuire wrote:
    Perhaps if you had sent the cap on the initial assignment to a large number you could have checked if it was in fact because of capacity allocation?
    That's a good idea. The answer is no, apparently not:

    http://play.golang.org/p/yVkWW56YYJ

    I set the initial cap to 64 for all of the slices. I expected this
    would result in more reuse of old references, and thus more strange
    behavior, but it acts the same as the original.

    At this point I am more confused by the first few iterations
    generating the correct results, than by the later ones being "wrong".
    Looks like you fixed the original so I can't test.
    It's still there and still broken.

    http://play.golang.org/p/LBhxle3WM_

    Note that the strange behavior doesn't show up until the fourth "roll".

    Although Remy recommended against it for efficiency reasons, you can
    patch the original so it works by using copy():

    http://play.golang.org/p/lCacHUyxlm

    --
  • Rory McGuire at Oct 11, 2012 at 10:04 pm

    On 11 Oct 2012 11:49 PM, "Matt Conrad" wrote:
    On Thu, Oct 11, 2012 at 1:18 AM, Rory McGuire wrote:
    Perhaps if you had sent the cap on the initial assignment to a large
    number you could have checked if it was in fact because of capacity
    allocation?
    That's a good idea. The answer is no, apparently not:

    http://play.golang.org/p/yVkWW56YYJ
    Weird would have that appending checks cap not len. I suppose they didn't
    want append to clobber data if the slice was from a larger array that had
    important data after the slice.

    --
  • Rémy Oudompheng at Oct 11, 2012 at 10:07 pm

    On 2012/10/11 Matt Conrad wrote:
    On Thu, Oct 11, 2012 at 1:18 AM, Rory McGuire wrote:
    Perhaps if you had sent the cap on the initial assignment to a large number you could have checked if it was in fact because of capacity allocation?
    That's a good idea. The answer is no, apparently not:

    http://play.golang.org/p/yVkWW56YYJ

    I set the initial cap to 64 for all of the slices. I expected this
    would result in more reuse of old references, and thus more strange
    behavior, but it acts the same as the original.

    At this point I am more confused by the first few iterations
    generating the correct results, than by the later ones being "wrong".
    Here is a version that indeed does what you may have intended:

    http://play.golang.org/p/aq_GqYzMJ-

    Rémy.

    --

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedOct 10, '12 at 9:49p
activeOct 11, '12 at 11:42p
posts9
users3
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase