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

• 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.
• 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:

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
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.
• 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.
• 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

 view thread | post
Discussion Overview
 group golang-nuts categories go posted Mar 5, '13 at 5:39a active Mar 7, '13 at 2:53a posts 5 users 3 website golang.org

### 3 users in discussion

Content

People

Support

Translate

site design / logo © 2022 Grokbase