FAQ
Here is what I have and what works so far:

http://play.golang.org/p/BXl0IIQ-qS

You can see from the program's output that after Sort(), all entries catA,
catB and catC int categories are grouped together (hierarchically) and only within
these clusters sorted/ordered by the float64 dist value.

(Technically the catA/catB/catC int categories are also sort-ordered
ascendingly but this isn't necessary at all. They just need to stay
together but instead of 2,2,4,4,6,6 might as well be 4,4,6,6,2,2...)

This works fine with a single sort.Sort() call but now I want to 1up this
as follows:

Suppose, (without losing the cluster groupings) I want to move those
groups/clusters which have "the most 'low' dist values" first, and those
which have on-average/more "higher" dist values last.

The above program randomizes the data each time but consider the following
example result:

SORTED:
===>

catA=2 catB=5 catC=0 dist=10
catA=2 catB=5 catC=0 dist=80
catA=2 catB=5 catC=0 dist=80
catA=2 catB=5 catC=0 dist=80
catA=2 catB=5 catC=1 dist=80
catA=2 catB=7 catC=1 dist=80

catA=4 catB=5 catC=0 dist=40
catA=4 catB=5 catC=0 dist=80
catA=4 catB=5 catC=1 dist=20
catA=4 catB=5 catC=1 dist=80
catA=4 catB=7 catC=0 dist=10
catA=4 catB=7 catC=0 dist=80

catA=6 catB=3 catC=1 dist=10
catA=6 catB=5 catC=0 dist=10
catA=6 catB=5 catC=0 dist=10
catA=6 catB=5 catC=0 dist=40



The above program randomizes the data each time but consider the following
example result:

The entire catA=2 group should be at the end, since most dists are "high"
(80). The entire catA=6 group should be first, because it gets us 3
"low-distance" entries.

I realize this is a bit of a fuzzy / impresicely-defined requirement, but
working with averages here would be sufficient to get to this benefit.

Ideally I'm looking for some ideas / tricks / algos that could integrate
this final need right into the current entries.(sort.Interface).Less()
method but a second Sort() pass would also be OK.

The problem I see with a naive "do a second sort.Sort() with a different
Less() method" approach: as per godoc, "the sort is not guaranteed to be
stable". So the previous groupings would get lost if I just did a simple
"sort the entire now-grouped slice just by dist values".

So... seems like I missed that class back in Computer Science -- any
algorithmics-ninjas out there got some neat ideas?

--
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/groups/opt_out.

Search Discussions

  • Philipp Schumann at Mar 5, 2013 at 5:42 am
    By the way, a different data structure is unfortunately out -- no
    hierarchical redesign or sub-slices would do here, the one linear slice of
    structs is a prerequisite. But the entry structure could be amended by
    additional helper fields if so required.

    On Tuesday, March 5, 2013 12:39:09 PM UTC+7, Philipp Schumann wrote:

    Here is what I have and what works so far:

    http://play.golang.org/p/BXl0IIQ-qS

    You can see from the program's output that after Sort(), all entries catA,
    catB and catC int categories are grouped together (hierarchically) and only within
    these clusters sorted/ordered by the float64 dist value.

    (Technically the catA/catB/catC int categories are also sort-ordered
    ascendingly but this isn't necessary at all. They just need to stay
    together but instead of 2,2,4,4,6,6 might as well be 4,4,6,6,2,2...)

    This works fine with a single sort.Sort() call but now I want to 1up this
    as follows:

    Suppose, (without losing the cluster groupings) I want to move those
    groups/clusters which have "the most 'low' dist values" first, and those
    which have on-average/more "higher" dist values last.

    The above program randomizes the data each time but consider the following
    example result:

    SORTED:
    ===>

    catA=2 catB=5 catC=0 dist=10
    catA=2 catB=5 catC=0 dist=80
    catA=2 catB=5 catC=0 dist=80
    catA=2 catB=5 catC=0 dist=80
    catA=2 catB=5 catC=1 dist=80
    catA=2 catB=7 catC=1 dist=80

    catA=4 catB=5 catC=0 dist=40
    catA=4 catB=5 catC=0 dist=80
    catA=4 catB=5 catC=1 dist=20
    catA=4 catB=5 catC=1 dist=80
    catA=4 catB=7 catC=0 dist=10
    catA=4 catB=7 catC=0 dist=80

    catA=6 catB=3 catC=1 dist=10
    catA=6 catB=5 catC=0 dist=10
    catA=6 catB=5 catC=0 dist=10
    catA=6 catB=5 catC=0 dist=40



    The above program randomizes the data each time but consider the following
    example result:

    The entire catA=2 group should be at the end, since most dists are "high"
    (80). The entire catA=6 group should be first, because it gets us 3
    "low-distance" entries.

    I realize this is a bit of a fuzzy / impresicely-defined requirement, but
    working with averages here would be sufficient to get to this benefit.

    Ideally I'm looking for some ideas / tricks / algos that could integrate
    this final need right into the current entries.(sort.Interface).Less()
    method but a second Sort() pass would also be OK.

    The problem I see with a naive "do a second sort.Sort() with a different
    Less() method" approach: as per godoc, "the sort is not guaranteed to be
    stable". So the previous groupings would get lost if I just did a simple
    "sort the entire now-grouped slice just by dist values".

    So... seems like I missed that class back in Computer Science -- any
    algorithmics-ninjas out there got some neat ideas?
    --
    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/groups/opt_out.
  • Kyle Lemons at Mar 5, 2013 at 5:57 am
    This is where stable sorts are really handy. Check out the code rsc
    included in the issue tracker:
    https://code.google.com/p/go/issues/detail?id=3671#c4

    I'd personally like to see something like it included in the stdlib, but I
    suppose that probably won't happen until it's necessary elsewhere in the
    stdlib :). Basically, the idea is that you sort by the innermost to
    outermost fields in sequence, and it maintains order within "equal"
    entities of each.

    On Mon, Mar 4, 2013 at 9:39 PM, Philipp Schumann wrote:

    Here is what I have and what works so far:

    http://play.golang.org/p/BXl0IIQ-qS

    You can see from the program's output that after Sort(), all entries catA,
    catB and catC int categories are grouped together (hierarchically) and only within
    these clusters sorted/ordered by the float64 dist value.

    (Technically the catA/catB/catC int categories are also sort-ordered
    ascendingly but this isn't necessary at all. They just need to stay
    together but instead of 2,2,4,4,6,6 might as well be 4,4,6,6,2,2...)

    This works fine with a single sort.Sort() call but now I want to 1up this
    as follows:

    Suppose, (without losing the cluster groupings) I want to move those
    groups/clusters which have "the most 'low' dist values" first, and those
    which have on-average/more "higher" dist values last.

    The above program randomizes the data each time but consider the following
    example result:

    SORTED:
    ===>

    catA=2 catB=5 catC=0 dist=10
    catA=2 catB=5 catC=0 dist=80
    catA=2 catB=5 catC=0 dist=80
    catA=2 catB=5 catC=0 dist=80
    catA=2 catB=5 catC=1 dist=80
    catA=2 catB=7 catC=1 dist=80

    catA=4 catB=5 catC=0 dist=40
    catA=4 catB=5 catC=0 dist=80
    catA=4 catB=5 catC=1 dist=20
    catA=4 catB=5 catC=1 dist=80
    catA=4 catB=7 catC=0 dist=10
    catA=4 catB=7 catC=0 dist=80

    catA=6 catB=3 catC=1 dist=10
    catA=6 catB=5 catC=0 dist=10
    catA=6 catB=5 catC=0 dist=10
    catA=6 catB=5 catC=0 dist=40



    The above program randomizes the data each time but consider the following
    example result:

    The entire catA=2 group should be at the end, since most dists are "high"
    (80). The entire catA=6 group should be first, because it gets us 3
    "low-distance" entries.

    I realize this is a bit of a fuzzy / impresicely-defined requirement, but
    working with averages here would be sufficient to get to this benefit.

    Ideally I'm looking for some ideas / tricks / algos that could integrate
    this final need right into the current entries.(sort.Interface).Less()
    method but a second Sort() pass would also be OK.

    The problem I see with a naive "do a second sort.Sort() with a different
    Less() method" approach: as per godoc, "the sort is not guaranteed to be
    stable". So the previous groupings would get lost if I just did a simple
    "sort the entire now-grouped slice just by dist values".

    So... seems like I missed that class back in Computer Science -- any
    algorithmics-ninjas out there got some neat ideas?

    --
    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/groups/opt_out.

    --
    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/groups/opt_out.
  • Andy Balholm at Mar 5, 2013 at 7:17 pm
    I think I've got it: http://play.golang.org/p/sz28dVEGBw

    The trick is to calculate all of the averages before calling Sort.

    --
    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/groups/opt_out.
  • Philipp Schumann at Mar 7, 2013 at 2:53 am
    Good thinking and great solution.. muchos gracias Andy!

    On Wednesday, March 6, 2013 2:17:04 AM UTC+7, Andy Balholm wrote:

    I think I've got it: http://play.golang.org/p/sz28dVEGBw

    The trick is to calculate all of the averages before calling Sort.
    --
    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/groups/opt_out.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedMar 5, '13 at 5:39a
activeMar 7, '13 at 2:53a
posts5
users3
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase