Storing structures in maps , what is the best way ?
Serge Hulne
maps is:
- use two ancillary functions, say e.g. fold(), unfold(), as in the
snippet herunder.
- Is there a more efficient (faster at runtime) way to dot that ?
All suggestions welcome !
Serge.
////////////////////////////////
package main
import (
"strconv"
"strings"
"fmt"
)
type person struct {
name string
surname string
age int
}
func fold (p person) string {
s := p.name + "~" + p.surname + "~" + strconv.Itoa(p.age)
return s
}
func unfold(s string) person {
ps := strings.Split(s, "~", -1)
age, _ := strconv.Atoi(ps[2])
p := person{ps[0], ps[1], age}
return p
}
func main(){
m := make(map[string]int)
p := person{"john", "Doe", 30}
//fold test
p_folded := fold(p)
fmt.Printf("folded : \t%s\n", p_folded)
//unfold test
fmt.Printf("unfolded : \t%v\n", unfold(p_folded))
//map test:
m[fold(p)]=1
}
////////////////////////////////
Serge Hulne
> The only straightforward way I can think of for storing structures in
> maps is:
>
> - use two ancillary functions, say e.g. fold(), unfold(), as in the
Two other obvious ways to achieve the same goal, which I have tried
are:
1. Generalise the idea using json.Marshal (obviously inefficient,
because marshalling is too complex hence too costly).
2. Use a prototype container from Github , which stores all objects
which implement a "hashvalue()" interface.
(sounds promising, but it is inefficient at the moment, because the
prototype is not optimized at all).
Serge.
peterGo
Is this a real problem?
The concatenation of name, surname, and age as a key to identify a
person is neither unique nor invariant over time: Jane Doe (one of
thirty-three in the California telephone directory) age 30 gets
married to John Buck and ages another year to age 31, etc.
"A map is an unordered group of elements of one type, called the
element type, indexed by a set of unique keys of another type, called
the key type."
Map types, The Go Programming Language Specification.
http://golang.org/doc/go_spec.html#Map_types
Peter
peterGo
package main
import (
"encoding/binary"
"fmt"
)
type id struct {
surname string
age int
}
id
street string
city string
state string
zip string
}
func mkey(p *id) string {
age := [4]byte{}[:]
binary.LittleEndian.PutUint32(age, uint32(p.age))
return p.name + p.surname + string(age)
}
func main() {
p := []person{
{id{"Jane", "Doe", 30}, "Rose St", "Passadena", "CA", "91107"},
{id{"John", "Buck", 35}, "Main St", "Peoria", "IL", "61602"},
}
m := make(map[string]*person)
for i := range p {
if _, ok := m[mkey(&p[i].id)]; ok {
fmt.Println("duplicate key", &p[i])
}
m[mkey(&p[i].id)] = &p[i]
}
if p := m[mkey(&p[0].id)]; p != nil {
fmt.Println(p.name, p.surname, p.age, ":", *p)
}
for _, p := range m {
if p != nil {
fmt.Println(p.name, p.surname, p.age, ":", *p)
Serge Hulne
Thanks for the sugestion !
However, simulating storing objects in a map, by indirection (storing
the data in an array of said objects and hash values as keys in a
container along with addresses of these objects as values) :
- Works for inserting an object.
- Offers no efficient solution for deleting an object,
- Does not result in a "map", but in a "set" (the key and the value
together refer to the *same* object , via its hash key and its
address).
Therefore it does not solve the problem at hand, namely :
"how to store an object of an arbitrary type, efficiently, as a *key*,
in a map".
Personally, I think that besides *string maps* and *integer maps*, Go
should define *maps for interfaces* (which implement the methods :
equal() and hash() )
Serge.
bflm
> Personally, I think that besides *string maps* and *integer maps*, Go
> should define *maps for interfaces* (which implement the methods :
> equal() and hash() )
map, e.g. pointer types are especially valuable as key types also.
Additionally I think that the proposal for some MapKeyer interface is
not a good idea. It will allow to write code which is IMO terrible (in
performance, not in terseness). Why? Imagine a C program performing
the same what will be possible with MapKeyer implementation of a
concrete type. C's approach, in many cases, would not be that easy,
but I expect it to be significantly better performing. Go is not e.g.
Java or C++ and I hope it will never be.
Just a 2c opinion.
Serge Hulne
> map, e.g. pointer types are especially valuable as key types also.
you need a second container to store the data.
In that case, one is back to square one: as in peterGo' s example.
> Go is not e.g. Java or C++ and I hope it will never be.
what I would like to propose is the integration of :
https://github.com/phf/go-hashmap
As a standard, next to the existing Go map, in order to generalize the
concept of maps the "Go way" !
Serge
peterGo
> Personally, I think that besides *string maps* and *integer maps*, Go
> should define *maps for interfaces* (which implement the methods :
> equal() and hash() )
http://golang.org/doc/go_faq.html#map_keys
Why are maps built in?, FAQ.
http://golang.org/doc/go_faq.html#builtin_maps
Peter
chris dollin
> Serge,
>
>> Personally, I think that besides *string maps* and *integer maps*, Go
>> should define *maps for interfaces* (which implement the methods :
>> equal() and hash() )
>
> Why don't maps allow structs and arrays as keys?, FAQ.
> http://golang.org/doc/go_faq.html#map_keys
In what way is that item an answer to Serge's comment? The
item says "Map lookup requires an equality operator", and
Serge's suggestion /provides/ one (and a hash, if hashing is
to be used, although some kind of ordering relation might
work instead; It All Depends. Without generics, it's harder to
test-drive plausible alrernatives).
> Why are maps built in?, FAQ.
> http://golang.org/doc/go_faq.html#builtin_maps
Similarly.
Chris
--
Chris "allusive" Dollin
peterGo
Did you read the references in full?
"Why don't maps allow structs and arrays as keys? Map lookup requires
an equality operator, which structs and arrays 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
structures, and so on. We may revisit this issue—and implementing
equality for structs and arrays will not invalidate any existing
programs—but without a clear idea of what equality of structs and
arrays should mean, it was simpler to leave it out for now."
"Why are maps built in? The same reason strings are: they are such a
powerful and important data structure that providing one excellent
implementation with syntactic support makes programming more pleasant.
We believe that Go's implementation of maps is strong enough that it
will serve for the vast majority of uses. If a specific application
can benefit from a custom implementation, it's possible to write one
but it will not be as convenient syntactically; this seems a
reasonable tradeoff."
Peter
On Dec 19, 8:30 am, chris dollin <ehog.he...@googlemail.com> wrote:
Paulo Pinto
In more expressive languages, maps are part of the library and I
honestly doubt
that they are less performant than in Go.
--
Paulo
On Dec 19, 2:10 pm, peterGo <go.peter...@gmail.com> wrote:
> Serge,
>
> > Personally, I think that besides *string maps* and *integer maps*, Go
> > should define *maps for interfaces* (which implement the methods :
> > equal() and hash() )
>
>
> Why are maps built in?, FAQ.http://golang.org/doc/go_faq.html#builtin_maps
chris dollin
> Chris,
>
> Did you read the references in full?
Yes, Peter, I did.
You answered Serge's
> Personally, I think that besides *string maps* and *integer
> maps*, Go should define *maps for interfaces* (which
> implement the methods: equal() and hash() )
with those references, one of which says that Go doesn't do
structs and arrays as map keys because equality isn't well
defined -- but Serge's suggestion says
>define *maps for interfaces* (which implement the
> methods: equal() and hash() )
where I had assumed that the equals() method /provided/
the well-definition of equality, making the cite you chose
inappropriate.
The other reference says
> We believe that Go's implementation of maps is strong
> enough that it will serve for the vast majority of uses
It certainly serves for a /lot/ of uses, but not being able to
have structs for keys has certainly been an issue for me,
and it looks like for Serge, and this isn't the first time this
has come up (of course it might be the same few complainers
each time).
I'd be quite happy to write my own map type for these
purposes, if I had generics so I could write the dratted
thing ONCE. But I can't.
So I don't think your cites address the issue that Serge
had laid before us.
Russel Winder
On Sun, 2010-12-19 at 06:00 -0800, Paulo Pinto wrote:
> Personally I don't agree with this reasoning.
>
> In more expressive languages, maps are part of the library and I
> honestly doubt
> that they are less performant than in Go.
At the risk of having taken the comment out of context: maps are
library types in Java and hence Groovy -- though there is significant
syntactic support in Groovy so they look part of the language -- but in
Python, maps (dicts for dictionaries) are integral to the whole Python
system. Python dict are very fast compared to the rest of Python,
albeit slow compared to maps in C++, Go, D, etc.
--
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
Johann Höchtl
On Dec 19, 3:00 pm, Paulo Pinto <paulo.jpi...@gmail.com> wrote:
> Personally I don't agree with this reasoning.
>
> In more expressive languages, maps are part of the library
long as two different builtins are required to create a map/slice/
channel vs. the rest, a map can not become a library type.
Johann
Paulo Pinto
Guess what two features all those languages have in common regarding
data structures.
--
Paulo
On Dec 19, 4:37 pm, Russel Winder <rus...@russel.org.uk> wrote:
> Paulo,
>
> On Sun, 2010-12-19 at 06:00 -0800, Paulo Pinto wrote:
> > Personally I don't agree with this reasoning.
>
> > In more expressive languages, maps are part of the library and I
> > honestly doubt
> > that they are less performant than in Go.
>
> At the risk of having taken the comment out of context: maps are
> library types in Java and hence Groovy -- though there is significant
> syntactic support in Groovy so they look part of the language -- but in
> Python, maps (dicts for dictionaries) are integral to the whole Python
> system. Python dict are very fast compared to the rest of Python,
> albeit slow compared to maps in C++, Go, D, etc.
>
> --
> Russel.
> =============================================================================
> London SW11 1EN, UK w:www.russel.org.uk skype: russel_winder
>
> < 1KViewDownload
Serge Hulne
current concept for a Go "map".
What I am actually proposing, in concrete terms, is to add something
like the hashmap :
https://github.com/phf/go-hashmap
in the standard container library of of Go, for the following reason:
- There are no associative containers in the go Go library yet (for
arbitrary objects, i.e. interfaces).
- The build-in "map" is intended only for keys having integers and
string type.
- The addition of a standard associative container (hashmap) in the Go
container library would ensure that it is:
- - available.
- - optimized ( O(n) ).
- - standard.
Thereby providing a solution to the problem of the missing associative
container by offering a fairly standardized and optimized data
structure in the shape of an addition to the containers library
(without modifying the existing map construct).
A positive side-effect is that it would also offer a concrete answer
to the recurring question about "generic maps" (which makes no sense
in Go).
Serge.
jnml
> - The build-in "map" is intended only for keys having integers and
> string type.
using pointer-to-struct keys. Note that the struct's pointer is
already a perfect, non colliding hash of the struct's identity (not of
the struct "value", but that's another story with a different
solution).
Serge Hulne
> already a perfect, non colliding hash of the struct's identity (not of
> the struct "value", but that's another story with a different
> solution).
Two separate instances of a given stuct with the *same data* will be
given two different address as in:
/////////////////////////
package main
import(
)
type person struct {
name string
surname string
}
m := make(map[*person]bool)
m[&person{"John", "Doe"}] = true
m[&person{"John", "Doe"}] = true
println("Elements present in the map:")
for item, _ := range m {
fmt.Printf("item = %v\n", *item)
}
}
//////////////////////////
Serge.
chris dollin
>>Note that the struct's pointer is
>> the struct "value", but that's another story with a different
>> solution).
>
> No it isn't:
>
> Two separate instances of a given stuct with the *same data* will be
> given two different address as in:
He said /identity/, not /equality/, and specifically "not of the struct "value".
Eleanor McHugh
>> Note that the struct's pointer is
>> already a perfect, non colliding hash of the struct's identity (not of
>> the struct "value", but that's another story with a different
>> solution).
>
> No it isn't:
>
> Two separate instances of a given stuct with the *same data* will be
> given two different address as in:
Which of course is the point. Two separate literals stored in memory may well contain the same data at a given point in time, but that's a transient correspondence which may or may not be indicative of equality.
On the face of it the easiest way to get around this would be for Go to accept struct values as keys and under the hood to calculate a hash based purely on the binary data they represent and the type signature. This would be nice from a developer perspective as we'd never have to worry about implementing our own hashing interfaces, but it would have the unfortunate consequence of mandating a given view of equality which might well be a poor fit with any given real-world usage. And there would always be the possibility of hash collisions which thanks to the extra layer of magic might be very difficult to debug...
Another alternative would be to give the language default interfaces which have an incestuous and privileged relationship with builtin data types and functions. This is how Ruby, Python. (un)Icon and a number of other languages with first-class map types handle things - but it feels contrary to the nature of Go in its current form.
So the best compromise is probably the one we all seem to adopt: a Hash interface which returns a unique key for a given type. I agree this is ugly, but this is a systems language we're talking about so it seems quite reasonable that it should be the implementer of a type who decides what constitutes equality for that type.
Ellie
Eleanor McHugh
Games With Brains
http://feyeleanor.tel
----
raise ArgumentError unless @reality.responds_to? :reason
chris dollin
> So the best compromise is probably the one we all seem to adopt: a Hash
> interface which returns a unique key for a given type. I agree this is ugly,
> but this is a systems language we're talking about so it seems quite
> reasonable that it should be the implementer of a type who decides
> what constitutes equality for that type.
I think that's true independant of any "systems language" issues.
We don't need to use interfaces for this. We could pass an equality
function and hash function to the map-making version of make.
(That allows the same type to be used in maps with different equality
and hashing functions, which sounds plausible to me.)
Serge Hulne
> >> Note that the struct's pointer is
> >> already a perfect, non colliding hash of the struct's identity (not of
> >> the struct "value", but that's another story with a different
> >> solution).
>
> > No it isn't:
>
> > Two separate instances of a given stuct with the *same data* will be
> > given two different address as in:
>
> Which of course is the point. Two separate literals stored in memory may well contain the same data at a given point in time, but that's a transient correspondence which may or may not be indicative of equality.
>
duplicates ?
A map which stores pointers to data as keys will not reject
duplicates, therefore it can hardly be regarded as a map, in the sense
of an associative container.
Serge.
jnml
> Yes, of course, but what is the point of a map which accepts
> duplicates ?
keys in a Go map are ever equal.
> A map which stores pointers to data as keys will not reject
> duplicates, therefore it can hardly be regarded as a map, in the sense
> of an associative container.
maps with pointer-to-struct keys on a daily basis and it is very
useful.
It seems to me like a case confusion of what the equality of structs
or pointer to them really is. The answer is: it's how you design the
data structures and their meanings and how are they used, i.e. there's
no universal answer. This problem is mentioned in the FAQ:
http://golang.org/doc/go_faq.html#map_keys
chris dollin
>
>> >> Note that the struct's pointer is
>> >> already a perfect, non colliding hash of the struct's identity (not of
>> >> the struct "value", but that's another story with a different
>> >> solution).
>>
>> > No it isn't:
>>
>> > Two separate instances of a given stuct with the *same data* will be
>> > given two different address as in:
>>
>> Which of course is the point. Two separate literals stored in memory may well contain the same data at a given point in time, but that's a transient correspondence which may or may not be indicative of equality.
>>
>
> Yes, of course, but what is the point of a map which accepts
> duplicates ?
They're not duplicates. They're just pointers to things that happen,
at this moment, to have the same contents.
> A map which stores pointers to data as keys will not reject
> duplicates, therefore it can hardly be regarded as a map, in the sense
> of an associative container.
The definition of "duplicate" is up to the definer. That's why, for example,
pop11 has newproperty (for address-based properties) and newanyproperty
(for whatever-yopu-like based properties), and Java has identity maps as
well as equality ones.
Eleanor McHugh
That's a very good idea idea, although even better would be having a runtime properties set for types which would allow equality, ordering, etc. to be specified directly. Can't really think of a clean way of doing that with the existing structure of Go though.
Steven
That's a very good idea idea, although even better would be having a runtime properties set for types which would allow equality, ordering, etc. to be specified directly. Can't really think of a clean way of doing that with the existing structure of Go though.On 20 Dec 2010, at 12:40, chris dollin wrote:
> I think that's true independant of any "systems language" issues.
>
> We don't need to use interfaces for this. We could pass an equality
> function and hash function to the map-making version of make.
>
> (That allows the same type to be used in maps with different equality
> and hashing functions, which sounds plausible to me.)
Steven
Eleanor McHugh
One possible syntax which springs to mind would be
prop (t T) Equals(o T) bool {
...
}
where the set of properties which can be implemented is defined in the language spec and T cannot be an interface. This could also be a nice way to add constructors into Go by allowing 'new' and/or 'allocate' properties.
Handled this way I see properties as similar to the various callbacks in a Ruby or Python system which potentially opens the door to a go-friendly meta-programming model.
Steven
One possible syntax which springs to mind would be
prop (t T) Equals(o T) bool {
...
}
where the set of properties which can be implemented is defined in the language spec and T cannot be an interface. This could also be a nice way to add constructors into Go by allowing 'new' and/or 'allocate' properties.
Handled this way I see properties as similar to the various callbacks in a Ruby or Python system which potentially opens the door to a go-friendly meta-programming model.
But here I am arguing syntax for a feature that smells suspiciously like something the Go team would object to ;-). Whatever the syntax, I think that, hypothetically, if properties were implemented, they should be specified using either library functions/constants, or using strings (like in imports or tags), rather than introducing identifiers that have special meaning.
Eleanor McHugh
> On Wed, Dec 22, 2010 at 7:13 AM, Eleanor McHugh <ele...@games-with-brains.com> wrote:
> > One possible syntax which springs to mind would be
> >
> > prop (t T) Equals(o T) bool {
> > ...
> >}
> >
> > where the set of properties which can be implemented is defined in the language spec and T cannot
> > be an interface. This could also be a nice way to add constructors into Go by allowing 'new' and/or
> > 'allocate' >properties.
> >
> > Handled this way I see properties as similar to the various callbacks in a Ruby or Python system which
> > potentially opens the door to a go-friendly meta-programming model.
>
> Something doesn't seem right about having special magical method names, and that's essentially what this is but with a different keyword. Can you call it like a method? Defining a method (and thus a method like item) isn't always as convenient as defining a func value, which makes spinning off variations on a type with different properties more cumbersome. On the other hand, built-in functions are fairly common and comfortable, and using a package to group them together and qualify them is also already a part of the language. Admittedly, using functions to manipulate properties of types poses some of its own issues as well, such as, where do you put these function calls? In init blocks?
I'd see properties as only being called by the runtime rather than explicitly by function or method invocation within code. As for interrogation and manipulation, that should probably be restricted to the reflection and unsafe APIs for conformity with other safety-breaking features.
> But here I am arguing syntax for a feature that smells suspiciously like something the Go team would object to ;-). Whatever the syntax, I think that, hypothetically, if properties were implemented, they should be specified using either library functions/constants, or using strings (like in imports or tags), rather than introducing identifiers that have special meaning.
That would leave properties very restricted in their utility, however I freely concede that this could be another one of those cases where my Ruby-brain's conflicting with the core principles of Go ;)