Shuffle Items in a Slice

[dc0d]

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?

[Konstantin Khomoutov]

What's wrong with a standard approach [1]?

1. https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm

[Jan Mercl]

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.

--
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

[dc0d]

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.

[Kaveh Shahbazian]

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 <mar...@geisler.net> wrote:

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

[Val]

2 implementations here : http://www.programming-idioms.org/idiom/10/shuffle-a-list/1564/go

As for the map iteration trick, the runtime doesn't guarantee to randomize anything, although it often tries to, so developers don't rely on some specific order. I've seen (in the past) some map iterations consistently not randomized at all. This behaviour may have evolved, but don't rely on it.

[Val]

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.

[Martin Geisler]

[dc0d]

Thanks Val for explanation & clarification;

[Joubin Houshyar]

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.

[Joubin Houshyar]

s/66537/65537

[Martin Geisler]

Hi Val

On Fri, Jun 24, 2016 at 2:48 PM, Val <dele...@gmail.com> wrote:
> 2 implementations here :
> http://www.programming-idioms.org/idiom/10/shuffle-a-list/1564/go
>
> As for the map iteration trick, the runtime doesn't guarantee to randomize
> anything, although it often tries to, so developers don't rely on some
> specific order.

That's a nice feature and very helpful when writing tests... otherwise
you end up with a test that works fine on one version/architecture and
"suddenly" breaks later.

Randomizing the order "on purpose" is probably also done for security
reasons. Python works much the same, and some years ago, the CPython
VM began randomizing the dict (map) type. The problem was that
carefully crafted input would trigger a worst-case scenario in the
hash table used behind the scenes and suddenly make your server crawl
to a halt.

The input could be HTTP headers, for example, with carefully chosen
names: these are normally read from the client and used as keys in a
map. With the right keys, you can trigger hash collisions and make the
map allocate much more memory than you would expect with typical keys.

Having the runtime add a bit of randomness to the keys prevents this
scenario. When the randomness changes at every execution, it further
helps the developers by highlighting the nondeterministic iteration
order of the hash table.

> I've seen (in the past) some map iterations consistently not
> randomized at all. This behaviour may have evolved, but don't rely on it.

That's good advice :-)

[Martin Geisler]

On Fri, Jun 24, 2016 at 2:54 PM, Val <dele...@gmail.com> 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

[Chris Hines]

The history of this behavior is explained in the release notes for Go 1.3: https://golang.org/doc/go1.3#map

[Kaveh Shahbazian]

Thanks for the reference! BTW I love this behaviour!

--
You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/UIYHKFeIf_k/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

Regards,

Kaveh Shahbazian