FAQ
[ NOTE: this question does not (directly) concern the iteration order of maps as returned
by range. If you think I am asking about that, please reread the email ]

I am trying to define an efficient well-order relation for maps. A well-order relation is described
here:
https://en.wikipedia.org/wiki/Well-order
and in essence requires defining a function

func (i *Item) Less(than *Item) bool

such that if two items i1, i2 are equal
i1.Less(i2) == false AND
i2.Less(i1) == false

and if i1, i2 are non-equal, either
i1.Less(i2) == true OR
i2.Less(i1) == true
but not both

The reason for doing this is to define a Less() operator for (e.g.) a red-black or LLRB tree. Note
that I do not care *what* the well-order relation does.

In this instance the maps are map[string]string, though the content of the maps is largely
irrelevant to the question.

One (inefficient) algorithm would be as follows:
1. If len(i1)<len(i2), i1<i2, else if len(i2)<len(i1), i2<i1
2. produce a union of they keys of each map
3. sort the union of the keys
4. iterate through the sorted union of the keys in order
if the key only appears in i1, i2<i1
if the key only appears in i2, i1>i2
if i1[key]<i2[key], i1<i2
if i2[key]<i1[key], i2<i1
else next
5. i2==i1

I suspect I could skip step 3, provided that golang guarantees that the iteration order of any hash is constant during any run.

Another approach would be simply to hash the map and its contents.

Is there a faster/more efficient way to do this?

--
Alex Bligh

--
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.
For more options, visit https://groups.google.com/d/optout.

## Search Discussions

•  at Feb 21, 2016 at 8:58 pm ⇧
Map iteration order is guaranteed to change.
The inefficiency comes from sorting, so sort only once, and use ordered slices instead of maps.

--
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.
For more options, visit https://groups.google.com/d/optout.
•  at Feb 21, 2016 at 11:04 pm ⇧

On 21 Feb 2016, at 20:58, Tamás Gulácsi wrote:

Map iteration order is guaranteed to change.
It is guaranteed to change between runs. However, in order to form a well-order relation without the sort step it only needs to be guaranteed to be consistent within a given run. I do not know whether that is the case.
The inefficiency comes from sorting, so sort only once, and use ordered slices instead of maps.
Please could you expand. The point of using map[string]string is that the dereference of the map happens far more frequently than the change to the content of the map. Optimising for the latter (which is what I am trying to do now) should not be at the expense of the former (which needs to be blindingly fast). So if you are suggesting the answer is 'not using a map', I'm afraid that doesn't cut it.

--
Alex Bligh

--
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.
For more options, visit https://groups.google.com/d/optout.
•  at Feb 22, 2016 at 12:39 am ⇧
Why not just use an existing ordered tree package?

https://godoc.org/github.com/google/btree

--
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.
For more options, visit https://groups.google.com/d/optout.
•  at Feb 22, 2016 at 1:31 am ⇧

On Sunday, February 21, 2016 at 3:05:15 PM UTC-8, Alex Bligh wrote:

On 21 Feb 2016, at 20:58, Tamás Gulácsi <tgula...@gmail.com <javascript:>>
wrote:
Map iteration order is guaranteed to change.
It is guaranteed to change between runs. However, in order to form a
well-order relation without the sort step it only needs to be guaranteed to
be consistent within a given run. I do not know whether that is the case.
The iteration order can (and often will, but is not guaranteed to) change
every time you iterate.

The inefficiency comes from sorting, so sort only once, and use ordered
slices instead of maps.

Please could you expand. The point of using map[string]string is that the
dereference of the map happens far more frequently than the change to the
content of the map. Optimising for the latter (which is what I am trying to
do now) should not be at the expense of the former (which needs to be
blindingly fast). So if you are suggesting the answer is 'not using a map',
I'm afraid that doesn't cut it. --
Alex Bligh

--
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.
For more options, visit https://groups.google.com/d/optout.
•  at Feb 22, 2016 at 5:46 am ⇧
Then augment your data structure with a map of "ordered keys" slices, one for each map.
This way lookups have the same cost, and only the infrequent modifications get some maintenance cost (and need some space).

--
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.
For more options, visit https://groups.google.com/d/optout.
•  at Feb 22, 2016 at 7:47 am ⇧
Map ordering is not guaranteed. It is not guaranteed to be constant, it is not guaranteed to be random, it is simply not defined.

--
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.
For more options, visit https://groups.google.com/d/optout.
•  at Feb 22, 2016 at 7:00 am ⇧
If you need _any_ well-order relation, you can do
reflect.ValueOf(map1).Pointer() < reflect.ValueOf(map2).Pointer() .
It's not even unsafe, _but_ it considers different two different map
instances that have the same key-value pairs,
may not be what you are looking for...
On Sunday, February 21, 2016 at 9:31:53 PM UTC+1, Alex Bligh wrote:

[ NOTE: this question does not (directly) concern the iteration order of
maps as returned
by range. If you think I am asking about that, please reread the email ]

I am trying to define an efficient well-order relation for maps. A
well-order relation is described
here:
https://en.wikipedia.org/wiki/Well-order
and in essence requires defining a function

func (i *Item) Less(than *Item) bool

such that if two items i1, i2 are equal
i1.Less(i2) == false AND
i2.Less(i1) == false

and if i1, i2 are non-equal, either
i1.Less(i2) == true OR
i2.Less(i1) == true
but not both

The reason for doing this is to define a Less() operator for (e.g.) a
red-black or LLRB tree. Note
that I do not care *what* the well-order relation does.

In this instance the maps are map[string]string, though the content of the
maps is largely
irrelevant to the question.

One (inefficient) algorithm would be as follows:
1. If len(i1)<len(i2), i1<i2, else if len(i2)<len(i1), i2<i1
2. produce a union of they keys of each map
3. sort the union of the keys
4. iterate through the sorted union of the keys in order
if the key only appears in i1, i2<i1
if the key only appears in i2, i1>i2
if i1[key]<i2[key], i1<i2
if i2[key]<i1[key], i2<i1
else next
5. i2==i1

I suspect I could skip step 3, provided that golang guarantees that the
iteration order of any hash is constant during any run.

Another approach would be simply to hash the map and its contents.

Is there a faster/more efficient way to do this?

--
Alex Bligh

--
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.
For more options, visit https://groups.google.com/d/optout.
•  at Feb 22, 2016 at 10:12 am ⇧
I wrote a library for illustration how to build a sortable map in
Golang: https://github.com/mikespook/sortmap.

Despite you may use this library in a practical project, the library is
building under unserious consideration and has the unoptimized code.
But still, I think it's enough as a demo.

On Monday, 22 February 2016 09:31:53 UTC+13, Alex Bligh wrote:

[ NOTE: this question does not (directly) concern the iteration order of
maps as returned
by range. If you think I am asking about that, please reread the email ]

I am trying to define an efficient well-order relation for maps. A
well-order relation is described
here:
https://en.wikipedia.org/wiki/Well-order
and in essence requires defining a function

func (i *Item) Less(than *Item) bool

such that if two items i1, i2 are equal
i1.Less(i2) == false AND
i2.Less(i1) == false

and if i1, i2 are non-equal, either
i1.Less(i2) == true OR
i2.Less(i1) == true
but not both

The reason for doing this is to define a Less() operator for (e.g.) a
red-black or LLRB tree. Note
that I do not care *what* the well-order relation does.

In this instance the maps are map[string]string, though the content of the
maps is largely
irrelevant to the question.

One (inefficient) algorithm would be as follows:
1. If len(i1)<len(i2), i1<i2, else if len(i2)<len(i1), i2<i1
2. produce a union of they keys of each map
3. sort the union of the keys
4. iterate through the sorted union of the keys in order
if the key only appears in i1, i2<i1
if the key only appears in i2, i1>i2
if i1[key]<i2[key], i1<i2
if i2[key]<i1[key], i2<i1
else next
5. i2==i1

I suspect I could skip step 3, provided that golang guarantees that the
iteration order of any hash is constant during any run.

Another approach would be simply to hash the map and its contents.

Is there a faster/more efficient way to do this?

--
Alex Bligh

--
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.
For more options, visit https://groups.google.com/d/optout.
•  at Feb 22, 2016 at 1:42 pm ⇧
https://github.com/petar/GoLLRB
On Sunday, February 21, 2016 at 2:31:53 PM UTC-6, Alex Bligh wrote:

[ NOTE: this question does not (directly) concern the iteration order of
maps as returned
by range. If you think I am asking about that, please reread the email ]

I am trying to define an efficient well-order relation for maps. A
well-order relation is described
here:
https://en.wikipedia.org/wiki/Well-order
and in essence requires defining a function

func (i *Item) Less(than *Item) bool

such that if two items i1, i2 are equal
i1.Less(i2) == false AND
i2.Less(i1) == false

and if i1, i2 are non-equal, either
i1.Less(i2) == true OR
i2.Less(i1) == true
but not both

The reason for doing this is to define a Less() operator for (e.g.) a
red-black or LLRB tree. Note
that I do not care *what* the well-order relation does.

In this instance the maps are map[string]string, though the content of the
maps is largely
irrelevant to the question.

One (inefficient) algorithm would be as follows:
1. If len(i1)<len(i2), i1<i2, else if len(i2)<len(i1), i2<i1
2. produce a union of they keys of each map
3. sort the union of the keys
4. iterate through the sorted union of the keys in order
if the key only appears in i1, i2<i1
if the key only appears in i2, i1>i2
if i1[key]<i2[key], i1<i2
if i2[key]<i1[key], i2<i1
else next
5. i2==i1

I suspect I could skip step 3, provided that golang guarantees that the
iteration order of any hash is constant during any run.

Another approach would be simply to hash the map and its contents.

Is there a faster/more efficient way to do this?

--
Alex Bligh

--
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.
For more options, visit https://groups.google.com/d/optout.
•  at Feb 22, 2016 at 7:59 pm ⇧
github.com/cznic/b has better performance and API.
On 23/02/2016, at 12:12 AM, "C Banning" wrote:

https://github.com/petar/GoLLRB
--
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.
For more options, visit https://groups.google.com/d/optout.

## Related Discussions

Discussion Navigation
 view thread | post
Discussion Overview
 group golang-nuts categories go posted Feb 21, '16 at 8:31p active Feb 22, '16 at 7:59p posts 11 users 9 website golang.org

### 9 users in discussion

Content

People

Support

Translate

site design / logo © 2021 Grokbase