Re: [go-nuts] Shuffle Items in a Slice
On Fri, 24 Jun 2016 04:05:49 -0700 (PDT)
dc0d wrote:
> To shuffle items in a slice I'm doing this:
>
> var res []Item
>
> //fill res logic
>
> shuffle := make(map[int]*Item)
> for k, v := range res {
> shuffle[k] = &v
> }
> res = nil
> for _, v := range shuffle {
> res = append(res, *v)
> }
>
> Which inserts items into a map then ranges over that map. Ranging
> over a map in Go returns the items in random order.
>
> 1 - I thought it's a cool trick!
> 2 - Is anything bad about doing this?
What's wrong with a standard approach [1]?
1.
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
--
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.
Re: [go-nuts] Shuffle Items in a Slice
map ranging randomization has to be fast - at the cost of the randomization
other properties. Use instead perhaps
https://golang.org/pkg/math/rand/#Rand.Perm to get a random slice of
indexes of a proper length. Later range that slice instead and indirectly
use the original slice item at the particular index fetched from the first
slice.
On Fri, Jun 24, 2016, 13:05 dc0d wrote:
> Hi;
>
> To shuffle items in a slice I'm doing this:
>
> var res []Item
>
> //fill res logic
>
> shuffle := make(map[int]*Item)
> for k, v := range res {
> shuffle[k] = &v
> }
> res = nil
> for _, v := range shuffle {
> res = append(res, *v)
> }
>
> Which inserts items into a map then ranges over that map. Ranging over a
> map in Go returns the items in random order.
>
> 1 - I thought it's a cool trick!
> 2 - Is anything bad about doing this?
>
> --
> 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.
>
--
-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.
Re: [go-nuts] Shuffle Items in a Slice
Please explain what other properties are you referring to?
I'm using this to choose from a list of tickets/tokens from database to
reduce contention (CouchDB). So being cryptographic is not a concern here
but rather being fast.
And if I'm not mistaken package rand uses a mutex internally - I thing that
can be ignored compared to other tasks at hand (IO, db, disk) though; and
thanks for mentioning Perm! Yet again you can range over a map concurrently
in a read-only manner - randomized for free!
I've not tried/take a look at crypto/rand yet.
On Friday, June 24, 2016 at 4:16:47 PM UTC+4:30, Jan Mercl wrote:
>
> map ranging randomization has to be fast - at the cost of the
> randomization other properties. Use instead perhaps
> https://golang.org/pkg/math/rand/#Rand.Perm to get a random slice of
> indexes of a proper length. Later range that slice instead and indirectly
> use the original slice item at the particular index fetched from the first
> slice.
>
> On Fri, Jun 24, 2016, 13:05 dc0d >
> wrote:
>
>> Hi;
>>
>> To shuffle items in a slice I'm doing this:
>>
>> var res []Item
>>
>> //fill res logic
>>
>> shuffle := make(map[int]*Item)
>> for k, v := range res {
>> shuffle[k] = &v
>> }
>> res = nil
>> for _, v := range shuffle {
>> res = append(res, *v)
>> }
>>
>> Which inserts items into a map then ranges over that map. Ranging over a
>> map in Go returns the items in random order.
>>
>> 1 - I thought it's a cool trick!
>> 2 - Is anything bad about doing this?
>>
>> --
>> 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...@googlegroups.com .
>> For more options, visit https://groups.google.com/d/optout.
>>
> --
>
> -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.
Re: [go-nuts] Shuffle Items in a Slice
Thanks Martin for the clarification!
Yet this inconsistent behavior is daunting. What version of Go is
playground using? x86? GopherJS? Better be something wrong with playground!
:)
On Fri, Jun 24, 2016 at 5:08 PM Martin Geisler wrote:
> On Fri, Jun 24, 2016 at 1:05 PM, dc0d wrote:
> >
> > Hi;
> >
> > To shuffle items in a slice I'm doing this:
> >
> > var res []Item
> >
> > //fill res logic
> >
> > shuffle := make(map[int]*Item)
> > for k, v := range res {
> > shuffle[k] = &v
> > }
> > res = nil
> > for _, v := range shuffle {
> > res = append(res, *v)
> > }
> >
> > Which inserts items into a map then ranges over that map. Ranging over a
> map in Go returns the items in random order.
> >
> > 1 - I thought it's a cool trick!
> > 2 - Is anything bad about doing this?
>
> While iteration over a map is said to be random, it isn't specified
> exactly how "random" the iteration is. The spec says
>
> https://golang.org/ref/spec#RangeClause
> The iteration order over maps is not specified and is not guaranteed
> to be the same from one iteration to the next.
>
> That is, the iteration order should not to be relied upon. A simple test
> like
>
> https://play.golang.org/p/czRE3pbMzc
>
> shows this: the keys are printed in a scrambled order. When I run this
> on my machine, I get a different order every time, but on the
> playground the order seems to be fixed and I get "0 5 7 1 2 3 4 6 8 9"
> every time. My guess would be that an external input is used to
> initialize the hash function used behind the scene -- and on the
> playground that input somehow has a fixed value.
>
> Unless you're build a toy application, my advice would be to use a
> real random generator to generate indexes into the map. Use these
> indexes to swap elements and permute the array as Konstantin mentioned
> (https://en.wikipedia.org/wiki/Fisher–Yates_shuffle).
>
> --
> Martin Geisler
>
--
Regards,
Kaveh Shahbazian
--
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.
Re: [go-nuts] Shuffle Items in a Slice
The playground caches everything, so running multiple times the same program will just serve the previously generated output. Also in the playground everything is frozen at some point in the past : the clock, the randomness sources, and you can't make outgoing requests to import randomness from the network. On Friday, June 24, 2016 at 2:47:13 PM UTC+2, dc0d wrote: > Better be something wrong with playground! :) > > -- 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.
Re: [go-nuts] Shuffle Items in a Slice
On Fri, Jun 24, 2016 at 1:05 PM, dc0d wrote:
>
> Hi;
>
> To shuffle items in a slice I'm doing this:
>
> var res []Item
>
> //fill res logic
>
> shuffle := make(map[int]*Item)
> for k, v := range res {
> shuffle[k] = &v
> }
> res = nil
> for _, v := range shuffle {
> res = append(res, *v)
> }
>
> Which inserts items into a map then ranges over that map. Ranging over a map
> in Go returns the items in random order.
>
> 1 - I thought it's a cool trick!
> 2 - Is anything bad about doing this?
While iteration over a map is said to be random, it isn't specified
exactly how "random" the iteration is. The spec says
https://golang.org/ref/spec#RangeClause
The iteration order over maps is not specified and is not guaranteed
to be the same from one iteration to the next.
That is, the iteration order should not to be relied upon. A simple test like
https://play.golang.org/p/czRE3pbMzc
shows this: the keys are printed in a scrambled order. When I run this
on my machine, I get a different order every time, but on the
playground the order seems to be fixed and I get "0 5 7 1 2 3 4 6 8 9"
every time. My guess would be that an external input is used to
initialize the hash function used behind the scene -- and on the
playground that input somehow has a fixed value.
Unless you're build a toy application, my advice would be to use a
real random generator to generate indexes into the map. Use these
indexes to swap elements and permute the array as Konstantin mentioned
(https://en.wikipedia.org/wiki/Fisher–Yates_shuffle).
--
Martin Geisler
--
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.
Re: [go-nuts] Shuffle Items in a Slice
Thanks Val for explanation & clarification; On Friday, June 24, 2016 at 5:24:30 PM UTC+4:30, Val wrote: > > The playground caches everything, so running multiple times the same > program will just serve the previously generated output. > > Also in the playground everything is frozen at some point in the past : > the clock, the randomness sources, and you can't make outgoing requests to > import randomness from the network. > > On Friday, June 24, 2016 at 2:47:13 PM UTC+2, dc0d wrote: > > >> Better be something wrong with playground! :) >> >> -- 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.
Re: [go-nuts] Shuffle Items in a Slice
On Friday, June 24, 2016 at 7:39:23 AM UTC-4, Konstantin Khomoutov wrote:
>
> On Fri, 24 Jun 2016 04:05:49 -0700 (PDT)
> dc0d > wrote:
>
> > To shuffle items in a slice I'm doing this:
> >
> > var res []Item
> >
> > //fill res logic
> >
> > shuffle := make(map[int]*Item)
> > for k, v := range res {
> > shuffle[k] = &v
> > }
> > res = nil
> > for _, v := range shuffle {
> > res = append(res, *v)
> > }
> >
> > Which inserts items into a map then ranges over that map. Ranging
> > over a map in Go returns the items in random order.
> >
> > 1 - I thought it's a cool trick!
> > 2 - Is anything bad about doing this?
>
> What's wrong with a standard approach [1]?
>
> 1.
> https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
>
>
Thanks for the link. I've been experimenting with quadratic residue mod p
(in N, counting numbers, so no zero) based scrambler for the final stage
of a hash. P values in 17, 257, 4097, and 66537 map quite nicely to some of
the more usual mem-obj sizes.
--
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.
Re: [go-nuts] Shuffle Items in a Slice
On Friday, June 24, 2016 at 1:16:12 PM UTC-4, Joubin Houshyar wrote:
>
>
> On Friday, June 24, 2016 at 7:39:23 AM UTC-4, Konstantin Khomoutov wrote:
>>
>> On Fri, 24 Jun 2016 04:05:49 -0700 (PDT)
>> dc0d wrote:
>>
>> > To shuffle items in a slice I'm doing this:
>> >
>> > var res []Item
>> >
>> > //fill res logic
>> >
>> > shuffle := make(map[int]*Item)
>> > for k, v := range res {
>> > shuffle[k] = &v
>> > }
>> > res = nil
>> > for _, v := range shuffle {
>> > res = append(res, *v)
>> > }
>> >
>> > Which inserts items into a map then ranges over that map. Ranging
>> > over a map in Go returns the items in random order.
>> >
>> > 1 - I thought it's a cool trick!
>> > 2 - Is anything bad about doing this?
>>
>> What's wrong with a standard approach [1]?
>>
>> 1.
>> https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
>>
>>
>
>
> Thanks for the link. I've been experimenting with quadratic residue mod p
> (in N, counting numbers, so no zero) based scrambler for the final stage
> of a hash. P values in 17, 257, 4097, and 66537 map quite nicely to some of
> the more usual mem-obj sizes.
>
s/66537/65537
--
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.
Re: [go-nuts] Shuffle Items in a Slice
On Fri, Jun 24, 2016 at 2:54 PM, Val wrote: > The playground caches everything, so running multiple times the same program > will just serve the previously generated output. Thanks, that's good to know! Makes a lot of sense too. > Also in the playground everything is frozen at some point in the past : the > clock, the randomness sources, and you can't make outgoing requests to > import randomness from the network. I found this blog post with a lot more background information: https://blog.golang.org/playground -- Martin Geisler -- 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.
