The bitwise operators for integers already allow unsigned integers to be
used as SMALL integer sets and the operators to be viewed as set
operators. E.g:
| becomes the union operator
& becomes the intersection operator
So, if sets became a built in type, these operators could be used for
them without undue confusion. Unfortunately, the fact that {} (which
are commonly use to enclose sets) are used as block delimiters means
that they are unavailable as a notation for set constants but I'm sure
something other notation could be devised.
The alternative to built in set functionality is to provide a set
package as part of the container package group. The main disadvantage
of this alternative (to built ins) is the need to use functions/methods
instead of operators for the basic operations on sets.
Peter
I would actually prefer to have a package for sets rather than
overloading the bitwise operators.
-Kevin
--
Kevin Ballard
http://kevin.sb.org
kbal...@gmail.com
If no one else is working on an implementation of a package for sets, I
would like to have a go. So, if I don't here someone say they're
already doing it, I'll get started.
Cheers
Peter
On Tue, Apr 6, 2010 at 8:43 PM, Peter Williams <pwil...@gmail.com> wrote:
> If no one else is working on an implementation of a package for sets, I
> would like to have a go. So, if I don't here someone say they're already
> doing it, I'll get started.
I've started my own little hack for this. If you care to look:
http://github.com/phf/go-intset
I currently have simplistic bitsets as well as sparse sets following
Briggs/Torzcon. The latter seem to really rock, but of course they eat
a lot of memory...
Cheers,
Peter
--
Peter H. Froehlich <http://www.cs.jhu.edu/~phf/>
Senior Lecturer | Director, Johns Hopkins Gaming Lab
For those just joining the conversation, my work (still experimental and
previously unannounced) is at:
<http://github.com/pwil3058/gosets>
I'm contemplating two main classes of set: one for sets of the various
integer types and another for sets of arbitrary types that satisfy a
specified interface.
So far all the work has been on the integer type sets which so far has a
working "engine" and a trial version for uint32 sets which will probably
undergo a fair bit of change as I try various ideas.
My latest idea is to change to an implementation of the higher level
sets (with minor changes to the "engine") that will allow set operations
between compatible set types. This will be possible as all types will
share the same engine. Most set operations would be compatible between
set types with the exception being the union and symmetric difference
operators where one set is a signed integer set and the other an
unsigned integer set.
This problem could be overcome by providing a cast operator to create a
new set (of the proscribed type) using the members of an existing set
minus, of course, those members that are not of valid values for the
type of the new set.
Peter
PS Work is slow as I'm still getting my head around Go.
Implementations (still being debugged and tested but hopefully ready to
play with) of two set packages are available in the "mudlark" Go package
project at:
<https://code.google.com/p/mudlark-go-pkgs/>
The "mudlark/set/bitset" package contains a type that implements sets of
whole numbers in the range min(int64) to max(uint64) using a sparse
bitmap implemented using maps.
The "mudlark/set/heteroset" package contains a type that implements
heterogeneous sets of objects of mixed types.
If anyone is interested and has the time, I'd appreciate review and
feedback on these packages.
Thanks
Peter
PS there are also packages for alternate sort functions ("mudlark/sort")
and a Left Leaning Red/Black Tree ("mudlark/tree/llrb_tree") in the project.
PPS The "mudlark" part is just a device for staking out a name space so
that packages don't clash with other packages with similar functionality.
Overloading operators is one of the features which make C++
unreadable.
(because it encourages programmers to make up their own personal
syntax).
>
> Not because it encourages programmers to make up their own syntax
> (because it just reuses existing syntax), but perhaps because it
> means intuitions about the meaning of those operators are no
> longer reliable.
Of course the facility is also the one that makes writing internal DSLs
easy. So there is no black and white here just shades of grey.
--
Russel.
=============================================================================
Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel...@ekiga.net
41 Buckmaster Road m: +44 7770 465 077 xmpp: rus...@russel.org.uk
London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Actuall all of the
following languages do support such a feature:
- ML
This is a good idea. This pattern is quite often used in Perl.
For simplicity, I would suggest making the value an int and just
writing 1 (or whatever) in there each time.
--Benny.
Hmm, it appears that struct{} does take up space, because
unsafe.Sizeof(struct{}{}) returns 4. :(
Shawn
Hmm, it appears that struct{} does take up space, because
unsafe.Sizeof(struct{}{}) returns 4. :(
personally, i'd use map[KeyType]bool,
or perhaps big.Int if KeyType is a smallish
integer.
the former has the advantage that you can
test for membership in an expression, because
maps return the zero value (false) when a member
isn't present; the latter will be very much faster for
set operations, and allows representation of complementary
sets, which can be useful.
> On 10 June 2010 09:30, Xuan Luo <fake....@gmail.com> wrote:
>
>>
>> Hmm, it appears that struct{} does take up space, because
>> unsafe.Sizeof(struct{}{}) returns 4. :(
>>
>
> Myself I would count that as a bug. What do the Go team think?
I think that zero length types lead to some odd situations. E.g., if
you have an array of them, then pointers to different elements of the
array are ==.
Ian
You forgot Union(), Intersection(), Difference(), etc. :-)
My bitset package for sets ("mudlark-go-pkgs" at Google Code) of integer
numbers (int, uint, int32, ...) uses maps but instead of using one entry
per set member packs them into a uint as one bit per member
(bits[member / sizeof(uint)] | member % sizeof(uint) roughly). How much
gain (memory efficiency) you get from this depends on how dense your set
is but it will be no worse than one map entry per member. Cost is
slight increase in computational overhead some of which may be regained
doing set operations (Union, etc.) depending on previous qualification
re set density.
At the moment my iterator sends members in partial sorted order (due to
map keys not being sorted by "range") but I'm working on this. I tried
using a binary tree instead of maps (because you get the ordering for
free) but most operations were 3 to 5 times slower than with maps. A
factor of 2 would have been predicted for my implementation (due to many
operations requiring two look ups instead of one) so the indications are
that maps are very efficient and I decided to go with them.
For more general sets, maps are a good option (with a suitable wrapper)
as long as the item's types are suitable for use as map keys otherwise
you need to look elsewhere.
Peter