Maps as sets.

[lamvak]

I think it's maps are a good basic implementation of sets. Say, a set of ints could be a map[int]bool. Inserting x into S could be done by simply setting S[x] = true. len(S) gives then number elements of S. Removing x from S, one would not just set S[x] to false, but remove the key from map.

Is there any better way to work with sets without actually writing a separate code for them? Using only builtins and present libraries?

[Matt Kane's Brain]

This is exactly what I do when I need a set. This way, you only need
to test S[x] in an if block.

--
matt kane's brain
http://hydrogenproject.com

[Peregrinati]

I haven't really given it much thought, but I doubt it on the grounds that that's exactly what's suggested in the Effective Go document.  http://golang.org/doc/effective_go.html#maps - 4th paragraph of the maps section.

[lamvak]

Thanks for the link. I now think I must have read that and it had to stuck with me; although I forgot where did I got that from and thus I got those second thoughts if there is a more convenient way.

So that way seems to be the preferable one.

[Stephen Day]

Further down, in http://golang.org/doc/effective_go.html#maps:

"To test for presence in the map without worrying about the actual value, you can use the blank identifier (_). The blank identifier can be assigned or declared with any value of any type, with the value discarded harmlessly. For testing just presence in a map, use the blank identifier in place of the usual variable for the value."

Maps are fine as sets for membership-based use cases. It might be better to go with a set implementation if you need more complex operations, such as intersections, differences and unions.

[Stephen Weinberg]

My opinion is that this would still waste a bool. What I do is make my
set a map[int]struct{}. A struct{} takes up no space. You can then
test for presence with _, ok := mySet[i]. If ok is true, integer i is
in the set. Adding to the set would be mySet[i] = struct{}. You may
want to make a Set type and hide these as methods. AddToSet(),
IsInSet(), etc

-- Stephen

[Lars Pensjö]

There was a time when an empty struct used one byte of memory. Maybe that has changed? Or is my memory wrong?

[Anthony Martin]

Lars Pensjö <lars....@gmail.com> once said:
> There was a time when an empty struct used one byte of memory.
> Maybe that has changed? Or is my memory wrong?

Your memory is good. It was changed last July:

changeset: 9075:6e4ee32fffd1
user: Robert Hencke <robert...@gmail.com>
date: Tue Jul 12 11:12:06 2011 -0700
files: src/cmd/gc/align.c src/cmd/gc/pgen.c
description:
gc: make size of struct{} and [0]byte 0 bytes

Fixes issue 1949.

R=iant, rsc
CC=golang-dev
http://codereview.appspot.com/4634124

Committer: Russ Cox <r...@golang.org>

Cheers,
Anthony

[lamvak]

Thanks, Stephen, Lars and Anthony! That one tweak is actually a lot for me - I'm using large data sets and I will need quite large sets (in terms of pc / laptop memory consumption at least). Thus even one byte per set item makes quite a difference for me.

[Jan Mercl]

That's a bit problematic. Hash maps are fast and all but anything like memory consumption efficient for large key sets. That's their principal cost for the speedy access.

[André Moraes]

On Wed, May 2, 2012 at 9:23 AM, Jan Mercl <0xj...@gmail.com> wrote:
> That's a bit problematic. Hash maps are fast and all but anything like memory consumption efficient for large key sets. That's their principal cost for the speedy access.

With this in mind, maybe instead of using map[something]struct{},
using []something would be better.
But the slice should be sorted for fast reading but for inserting
things would become more complicated.

--
André Moraes
http://amoraes.info

[lamvak]

And often it will. Especially, when it's not the mapping that is important in the data and it can be accessed just element by element, in a series. Then indexing through a slice is just the way to go (so to speak ;) ).

And yet sometimes I need a big map - to analyse data grouping and to process data group-wise.

[Jan Mercl]

I would probably compromise using a B-tree. All operations in log N and low memory overhead.

[lamvak]

Hmm... So what is the memory overhead for a map, then?

[Jan Mercl]

Measurement of the specific setup beats all speculations ;-)

[André Moraes]

On Wed, May 2, 2012 at 11:16 AM, Jan Mercl <0xj...@gmail.com> wrote:
> Measurement of the specific setup beats all speculations ;-)

This can help:

http://golang.org/pkg/testing/#Benchmark
http://blog.golang.org/2011/06/profiling-go-programs.html

[cmjohnson....@gmail.com]

On Sunday, April 29, 2012 10:14:54 AM UTC-10, Stephen Weinberg wrote:

My opinion is that this would still waste a bool. What I do is make my
set a map[int]struct{}. A struct{} takes up no space. You can then
test for presence with _, ok := mySet[i]. If ok is true, integer i is
in the set. Adding to the set would be mySet[i] = struct{}. You may
want to make a Set type and hide these as methods. AddToSet(),
IsInSet(), etc

I tried to do this, but when I did mySet[i] = struct{}{}, I got "panic: runtime error: assignment to entry in nil map." I take it that the problem is there are no bytes in memory allocated for setting equal to the empty struct. Is there some other way to add to the map besides mySet[i] = whatever to get around this?

-- Carl Johnson

[cmjohnson....@gmail.com]

Never-mind. I just forgot to `make` my map first. D'oh!