Set / Unordered Collection of Slices

[Matt Juran]

Hi folks,

Looking for an ideal way to represent a set (unordered collection) of slices.

From what I can tell this is the standard approach for sets:

type Set map[MyType]struct{}

But since slices are not comparable they cannot be used for map keys. One solution I've seen is a hash as the key:

type Hash int
type Set map[Hash]MySliceType

But I'd prefer not to manage the hashing.

Looking to define these sets pre-compile in source and dynamically generate them at runtime in the clearest way possible, without performance sacrifices. "Write that hash-based library" is a solution (or submit that patch to golang-set), but would prefer to use simple language features if possible to keep those static definitions clean and simple.

Thanks for your cycles.

Matt

@pciet

[Matt Harden]

This looks like a job for a Trie. <pun sad="true">I haven't TRIEd it,</pun> but http://godoc.org/github.com/apokalyptik/quicktrie#NewBWTrie could do the trick.

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

[Volker Dobler]

Am Freitag, 28. November 2014 04:14:16 UTC+1 schrieb Matt Juran:

Hi folks,

Looking for an ideal way to represent a set (unordered collection) of slices.

From what I can tell this is the standard approach for sets:

type Set map[MyType]struct{}

But since slices are not comparable they cannot be used for map keys. One solution I've seen is a hash as the key:

type Hash int
type Set map[Hash]MySliceType

But I'd prefer not to manage the hashing.

If _your_ notion of slice equality is coincident with equality of pointer-to-slice

than you may just use map[*MySliceType].

The difficulty here is a clear understanding what slice-equality means

in your context. 

 

Looking to define these sets pre-compile in source and dynamically generate them at runtime in the clearest way possible, without performance sacrifices. "Write that hash-based library" is a solution (or submit that patch to golang-set), but would prefer to use simple language features if possible to keep those static definitions clean and simple.

Not sure if I understand this.

V. 

[egon]

On Friday, 28 November 2014 05:14:16 UTC+2, Matt Juran wrote:

Hi folks,

Looking for an ideal way to represent a set (unordered collection) of slices.

From what I can tell this is the standard approach for sets:

type Set map[MyType]struct{}

But since slices are not comparable they cannot be used for map keys. One solution I've seen is a hash as the key:

type Hash int
type Set map[Hash]MySliceType

But I'd prefer not to manage the hashing.

It depends on the structures / requirements at hand.

Can you specify what MyType is?

How many items do you expect to be in the set?

What are the performance requirements?

How often will you put things in / take out?

Sometimes the best solution is just a []MyType.

+ Egon

[Matt Juran]

Can you specify what MyType is?

An ordered set of int8 pairs each representing a relative coordinate, combined to represent a path on a chess-like board (square grid). The set I am looking to represent is a set of these paths, representing the base moveset for a given piece.

How many items do you expect to be in the set?

Quite likely never more than 100.

What are the performance requirements?

For this specific problem I'll be calculating all of the possible moves for a given player on a chess board at once - small paths but translated to the real game state through a pipeline. Then scaled up to any number of parallel games. Needs to be calculated quick (ideally so the player doesn't notice lag) and needs to scale up to many parallel games.

How often will you put things in / take out?

In some cases the sets will be read only, in others I'll be constructing them on the fly. Still fleshing out how I want to implement much of this, so don't know the full answer yet.

 If _your_ notion of slice equality is coincident with equality of pointer-to-slice than you may just use map[*MySliceType].

This is an alternative. My thought was that this would add more language noise with dealing with dereferencing slices. I'll tinker with this approach today.

Am searching for the idiomatic Go toolset to deal with this situation:

- collection of items

- need to sometimes define ahead of time in source code (e.g. lookup tables)

- order has no meaning

- need to iterate over entire collection often

- ideally isn't more complex than maps or slices for code readability

Matt

[egon]

On Friday, 28 November 2014 19:20:34 UTC+2, Matt Juran wrote:

Can you specify what MyType is?

An ordered set of int8 pairs each representing a relative coordinate, combined to represent a path on a chess-like board (square grid). The set I am looking to represent is a set of these paths, representing the base moveset for a given piece.

How large is the maximum board?

How large is the maximum relative coordinate?

I.e. is it chess-like - or - is it actually a chess board?

[egon]

On Friday, 28 November 2014 19:42:37 UTC+2, egon wrote:

On Friday, 28 November 2014 19:20:34 UTC+2, Matt Juran wrote:

Can you specify what MyType is?

An ordered set of int8 pairs each representing a relative coordinate, combined to represent a path on a chess-like board (square grid). The set I am looking to represent is a set of these paths, representing the base moveset for a given piece.

How large is the maximum board?

How large is the maximum relative coordinate?

Also, how long is the maximum path?

[Matt Juran]

I'm building a frame for chess-like games. So that puts constraint on the order of magnitude to ~10x10 boards, and any reasonable path in that space (so order of magnitude of ~10 there as well).

[Matt Juran]

Using a pointer to the slice compiles:

type Point struct {
  X int8
  Y int8
}
type Path []Point
type PathSet map[*Path]struct{}

var MySet = PathSet{
  &Path{{0, 1}, {0, 2}}: {},
  &Path{{0, -1}, {0, -2}}: {},
}

...

for point,_ := range MySet {
  // need to dereference point here
}

Dislike the & and : {} and necessary dereferencing, but those are minor details. So I'm planning to use this approach. Thanks for the help.

Matt

[Matt Juran]

(meant path instead of point in the for loop)

--
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/xNChXkrru9E/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.

[Bakul Shah]

You can encode each location on the board as a single integer. Then for each type of piece you precompute a vector of a set of valid moves. Then i-th entry is a set of locations this kind of piece can be moved to. This valid moves set can be represented as a 100 element vector of booleans or a string (if you further convert 0..99 to a char range). A particular path is just a slice of ints or a string. If you're doing alpha-beta pruning, you will be constructing a number of such candidate paths. If you also want to compare a candidate path against a set of "known to be better" paths, you will likely want a prefix tree. (Ignore the previous sentence if it doesn't make sense!)

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.

[egon]

Initially I was thinking, yeah, maybe encoding the possible moves at a position into an uint64... but it's probably a bad idea: http://play.golang.org/p/uFQ9QIrPiQ (At least I had fun writing it. :) )

I'm not quite completely clear how it will fit into the whole thing... but one thing you might consider is that generating the moveset on the fly might be faster than looking them up.

Also this sounds a lot like a problem solved many times:

http://en.wikipedia.org/wiki/Board_representation_(chess)

https://cis.uab.edu/hyatt/boardrep.html

One that looks interesting is this: http://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation

Anyways, I would probably start with an implementation like: http://play.golang.org/p/pUQECj0wVT

And later figure out what needs to be optimized and how.

+ Egon

[Sonia Keys]

Why don't maps allow slices as keys? is a FAQ.  For your case, I'm guessing you won't get far with the pointer key solution.  I think you'll want to compare the contents of the paths.  I'll suggest using fmt.Sprintf("%v", path) as a map key.

[matthe...@gmail.com]

From this discussion I'm seeing these two approaches as being ideal with the current Go:

type map[*MySliceType]struct{}

or

type map[MyHashType]MySliceType

After reading up on the importance of cache performance I am guessing in the end I'll be doing something completely different, instead of focusing on high level consistency. But these are what I'll start with, thank you.

Bakul-

Thanks for your suggestions, I am now thinking about ways to precompute more paths. Am not working on an AI at this point, but will probably in the future. It's a good point that the space for chess problems is small in some ways (8x8), which enables a lot of potential value in precomputed lookup tables.

Egon-

That's some excellent bit fiddling :) Didn't think about setting the API up like that (call on a piece with the coordinates to move from), and really neat to be able to do move combinations with just a bitwise or (return Rook(x, y) | Bishop(x, y)).

And the hashing implementation looks great, am investigating using that approach in my code. For now code clarity wins out, will be worrying about optimization further down the road as suggested. At this point still getting up to speed on Go, so am following paths to understand my options.

Sonia-

Interesting point from that FAQ is that arrays would work:

"In Go 1, unlike prior releases, equality is defined for structs and arrays, so such types can be used as map keys. Slices still do not have a definition of equality, though."

My concern about converting that path to a string for the key is unnecessary memory usage while still needing a set of wrapper functions, without the ability to simply predefine paths in source. Using a pointer isn't so bad, as I can just write my own comparison function.

Using an array would work for the path lookup tables as those paths will not change, but that adds a language burden with having to define the size of the array in code.

Thanks all again for the help.

Matt

[Matt Harden]

Why not define the path type as a string, and create methods to access parts of the path by decoding the string?

On the other hand it is possible to create dynamic length keys for maps (without strings) by using the fact that structs and interfaces are both comparable, as long as the values in the interfaces are comparable as well:

type Path interface{}

type PathImpl struct{ head Pt; tail List }

var myPath = PathImpl{head: Pt{1,2}, tail: PathImpl{head: Pt{3,4}, tail: nil}}

var myMap = map[Path]struct{}{myPath: struct{}{}}

--

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+unsubscribe@googlegroups.com.

[Nick Craig-Wood]

On 28/11/14 19:42, Sonia Keys wrote:
> Why don't maps allow slices as keys is a FAQ.

https://golang.org/doc/faq#map_keys

The FAQ says

> Map lookup requires an equality operator, which slices do not
implement. They don't implement equality because equality is not well
defined on such types; there are multiple considerations involving
shallow vs. deep comparison, pointer vs. value comparison, how to deal
with recursive types, and so on. We may revisit this issue—and
implementing equality for slices will not invalidate any existing
programs—but without a clear idea of what equality of slices should
mean, it was simpler to leave it out for now.

Given that arrays and structs both of which which do have an equality
operator have all of these problems and have solved them I don't think
this is a very good justification for not allowing it on slices any more

Eg http://play.golang.org/p/TCU16L4mzl

--
Nick Craig-Wood <ni...@craig-wood.com> -- http://www.craig-wood.com/nick

[Rob Pike]

Structs and arrays do not have all the problems slices have, which is why they define equality and slices do not. For instance, this is a valid type:

type T []T

but 

type T [3]T

and 

type T struct { t T }

are not.

-rob

[Nick Craig-Wood]

Thanks for clearing that up.

I'm having trouble working out what use

type T []T

Is in real life, but that is probably a failure of my imagination! I
guess it could be used to describe the shape of a tree or network, but
without being able to add any extra information about the nodes.

[egon]

On Monday, 1 December 2014 15:06:22 UTC+2, Nick Craig-Wood wrote:

On 01/12/14 11:41, Rob Pike wrote:
> Structs and arrays do not have all the problems slices have, which is
> why they define equality and slices do not. For instance, this is a
> valid type:
>
> type T []T 

>
> but
>
> type T [3]T
>
> and
>
> type T struct { t T }
>
> are not.

Thanks for clearing that up.

I'm having trouble working out what use

  type T []T

I'm guessing it's more used inside a struct:

type Node struct {

  Value interface{}

  Children []Node

}

The principle stays the same... i.e. you can't have

type Node struct {

  Value interface{}

  Children [3]Node

}

or 

type Node struct {

  Value interface{}

  Left, Right Node

}

[Staven]

On Mon, Dec 01, 2014 at 11:03:21AM +0000, Nick Craig-Wood wrote:
> Given that arrays and structs both of which which do have an equality
> operator have all of these problems and have solved them I don't think
> this is a very good justification for not allowing it on slices any more

Nope.
http://play.golang.org/p/4VxjRkQ9v_