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

  • Tamás Gulácsi 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.
  • Alex Bligh 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.
  • Donovan Hide 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.
  • Keithr 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.
  • Tamás Gulácsi 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.
  • Dave Cheney 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.
  • Roberto Zanotto 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.
  • Mikespook 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.
  • C Banning 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.
  • Dan Kortschak 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
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedFeb 21, '16 at 8:31p
activeFeb 22, '16 at 7:59p
posts11
users9
websitegolang.org

People

Translate

site design / logo © 2021 Grokbase