1. Phix:Sort Columns Not Working Like Expected

-- test_sort_columns.ex 
sequence table = {{5,4,3,2,1},{'A','B','C','D','E'}} 
?sort_columns(table,{1}) 

Result:

{{5,4,3,2,1},{65,66,67,68,69}} 

What I expected:

{{1,2,3,4,5},{69,68,67,66,65}} 
new topic     » topic index » view message » categorize

2. Re: Phix:Sort Columns Not Working Like Expected

-- original 'random' 
 
sequence 
table = { 
    {3, "cat"}, 
    {5, "chipmunk"}, 
    {5, "zebu"}, 
    {9, "geese"}, 
    {1, "dog"}, 
    $} 
 
-- first column 
? sort_columns( table, {1} ) 
 
/* 

{ 
    {1,"dog"}, 
    {3,"cat"}, 
    {5,"chipmunk"}, 
    {5,"zebu"}, 
    {9,"geese"}} 
--*/ 
 
-- second column 
? sort_columns( table, {2} ) 
 
/* 

{ {3,"cat"}, 
  {5,"chipmunk"}, 
  {1,"dog"}, 
  {9,"geese"}, 
  {5,"zebu"}} 
--*/ 
 

Looks ok, as expected for this sort of thing.

  • first column is now in sorted order
  • the "rows" just follow along unaltered

be well
_tom

new topic     » goto parent     » topic index » view message » categorize

3. Re: Phix:Sort Columns Not Working Like Expected

As tom said, that is what I would expect. I'll start with a quick diversion of a new feature and an explanation/demonstration of what sort_columns actually does.

On the basis of this I have just added pp_IntCh of -1 such that

pp(table) -- {{5,4,3,2,1}, {65'A',66'B',67'C',68'D',69'E'}} 
pp(table,{pp_IntCh,-1}) -- {{5,4,3,2,1}, {'A','B','C','D','E'}} 

Without that new feature:

sequence ic = columnize({{5,4,3,2,1},{'A','B','C','D','E'}}) 
pp(ic)                      -- {{5,65'A'}, {4,66'B'}, {3,67'C'}, {2,68'D'}, {1,69'E'}} 
pp(sort_columns(ic,{1}))    -- {{1,69'E'}, {2,68'D'}, {3,67'C'}, {4,66'B'}, {5,65'A'}} 
pp(sort_columns(ic,{2}))    -- {{5,65'A'}, {4,66'B'}, {3,67'C'}, {2,68'D'}, {1,69'E'}} 

With that new feature:

sequence ic = columnize({{5,4,3,2,1},{'A','B','C','D','E'}}) 
ppOpt({pp_IntCh,-1}) 
pp(ic)                      -- {{5,'A'}, {4,'B'}, {3,'C'}, {2,'D'}, {1,'E'}} 
pp(sort_columns(ic,{1}))    -- {{1,'E'}, {2,'D'}, {3,'C'}, {4,'B'}, {5,'A'}} 
pp(sort_columns(ic,{2}))    -- {{5,'A'}, {4,'B'}, {3,'C'}, {2,'D'}, {1,'E'}} 

That is how I would naturally get the order you want, but it ain't in the format you want.

Getting back to your immediate needs, the thing is that sort can only sort one thing, but then again a tag sort can be applied to as many things as you like, so:

sequence table = {{5,4,3,2,1},{'A','B','C','D','E'}}  
sequence tags = custom_sort(table[1],tagset(length(table[1]))) 
sequence res = table -- (just for the shape, every element gets overwritten) 
for i=1 to length(tags) do 
    for j=1 to length(table) do 
        res[j][i] = table[j][tags[i]] 
    end for 
end for 
pp(res) -- {{1,2,3,4,5}, {69'E',68'D',67'C',66'B',65'A'}} 
ppOpt({pp_IntCh,-1}) 
pp(res) -- {{1,2,3,4,5}, {'E','D','C','B','A'}} 

Does that help?

I can see there might be a basis somewhere among all that for a new builtin to live alongside sort_columns() and custom_sort(), but what to call it?... (column_sort()?!)

PS: I should strongly recommend going the columnize() route, defining 5 and 'A' next to each other to start with, as per the pp(ic) outputs. Inserting/deleting the 3rd element of 54321 and ABCDE looks simple enough, but once they're 50+ elements long it gets to be a RPITA keeping two or more such sequences perfectly in step. Note that when I say "columnize() route", you should understand there is a reversibility about that:

sequence ic = columnize({{5,4,3,2,1},{'A','B','C','D','E'}}) 
ppOpt({pp_IntCh,-1}) 
pp(ic)              -- {{5,'A'}, {4,'B'}, {3,'C'}, {2,'D'}, {1,'E'}} 
pp(columnize(ic))   -- {{5,4,3,2,1}, {'A','B','C','D','E'}} 
new topic     » goto parent     » topic index » view message » categorize

4. Re: Phix:Sort Columns Not Working Like Expected

_tom said...
 
sequence 
table = { 
    {3, "cat"}, 
    {5, "chipmunk"}, 
    {5, "zebu"}, 
    {9, "geese"}, 
    {1, "dog"}, 
    $} 
 
-- first column 
? sort_columns( table, {1} ) 

So, my first error is expecting it to sort a different sequence format.

I had the table columns in separate rows:

sequence 
table = { 
    {3,5,5,9,1}, 
    {"cat","chipmunk","zebu","geese","dog"} 
    } 

So, I was using it wrong.

Now, let's see what Pete says! grin

new topic     » goto parent     » topic index » view message » categorize

5. Re: Phix:Sort Columns Not Working Like Expected

petelomax said...

I should strongly recommend going the columnize() route, defining 5 and 'A' next to each other to start with, as per the pp(ic) outputs. Inserting/deleting the 3rd element of 54321 and ABCDE looks simple enough, but once they're 50+ elements long it gets to be a RPITA keeping two or more such sequences perfectly in step. Note that when I say "columnize() route", you should understand there is a reversibility about that:

sequence ic = columnize({{5,4,3,2,1},{'A','B','C','D','E'}}) 
ppOpt({pp_IntCh,-1}) 
pp(ic)              -- {{5,'A'}, {4,'B'}, {3,'C'}, {2,'D'}, {1,'E'}} 
pp(columnize(ic))   -- {{5,4,3,2,1}, {'A','B','C','D','E'}} 

Thanks, Pete! I think columnize() will work fine.

new topic     » goto parent     » topic index » view message » categorize

6. Re: Phix:Sort Columns Not Working Like Expected

euphoric said...
petelomax said...

I should strongly recommend going the columnize() route, defining 5 and 'A' next to each other to start with, as per the pp(ic) outputs. Inserting/deleting the 3rd element of 54321 and ABCDE looks simple enough, but once they're 50+ elements long it gets to be a RPITA keeping two or more such sequences perfectly in step. Note that when I say "columnize() route", you should understand there is a reversibility about that:

sequence ic = columnize({{5,4,3,2,1},{'A','B','C','D','E'}}) 
ppOpt({pp_IntCh,-1}) 
pp(ic)              -- {{5,'A'}, {4,'B'}, {3,'C'}, {2,'D'}, {1,'E'}} 
pp(columnize(ic))   -- {{5,4,3,2,1}, {'A','B','C','D','E'}} 

Thanks, Pete! I think columnize() will work fine.

I downloaded the latest version of Phix to examine the sort routines. It appears that sort_columns() is a wrapper for custom_sort() which uses Shellsort which is acknowledged in the source as being unstable.

For Orac I dumped RDS' Shellsort in favor of a Merge/Insertion sort hybrid (See Timsort) to guarantee stability. Without stability it is risky to do multi-column sorting as the result might not always be 100% correct. For the business programs used in our office correctness is absolutely essential.

Given the popularity of Phix I recommend the same or equivalent be done to it. The above hybrid is reasonably performant.

Spock

new topic     » goto parent     » topic index » view message » categorize

7. Re: Phix:Sort Columns Not Working Like Expected

Spock said...

I downloaded the latest version of Phix to examine the sort routines. It appears that sort_columns() is a wrapper for custom_sort() which uses Shellsort which is acknowledged in the source as being unstable.

For Orac I dumped RDS' Shellsort in favor of a Merge/Insertion sort hybrid (See Timsort) to guarantee stability. Without stability it is risky to do multi-column sorting as the result might not always be 100% correct. For the business programs used in our office correctness is absolutely essential.

Given the popularity of Phix I recommend the same or equivalent be done to it. The above hybrid is reasonably performant.

Spock

I think the best thing we've got so far in terms of stable sorts is pihism_sort(): https://openeuphoria.org/forum/131271.wc#131305 (also part of demo/rosetta/CompareSortingAlgorithms.exw)

I'm open to offers, but not about to embark on anything regarding stable sorting on me lonesome.

Pete

PS: To summarise that drdobbs link, if you have say {x,y} of {{3,4},{4,4},{5,4}} and sort on x,y all is fine. Likewise if you sort on y,x. However (what he did not explain very clearly) if you sort on x, then entirely after the fact re-sort the whole thing again on (just) y, there is an expectation the x-ordering would be preserved. I will concede my shrug of "well sort it by y,x on that second pass then" is fine for unbreakable business logic rules, but doesn't really hold when it is more of a GUI-interaction expectation, for instance. Note however that you can always make a tagsort stable by using the item indexes at the end of a custom comparator, and I have just changed the (private to sort.e) standard routine for that as follows:

function tagsort(integer i, integer j, sequence data) 
-- standard function for a standard tagsort 
--  return compare(data[i],data[j]) 
    integer c = compare(data[i],data[j]) 
    if c=0 then c = compare(i,j) end if 
    return c 
end function 

Also, I am not convinced that the return 0 at the end of column_compare() in sort.e does not make sort_columns() stable anyway: at least I cannot reproduce an issue along the lines of my understanding as just outlined above.

new topic     » goto parent     » topic index » view message » categorize

8. Re: Phix:Sort Columns Not Working Like Expected

petelomax said...
Spock said...

...

Given the popularity of Phix I recommend the same or equivalent be done to it. The above hybrid is reasonably performant.

Spock

I think the best thing we've got so far in terms of stable sorts is pihism_sort(): https://openeuphoria.org/forum/131271.wc#131305 (also part of demo/rosetta/CompareSortingAlgorithms.exw)

I'm open to offers, but not about to embark on anything regarding stable sorting on me lonesome.

Pete

_Tom has kindly packaged the sort bundle I developed. That could be incorporated into Phix (or a user could simply copy/paste into their own program/s).

Spock

new topic     » goto parent     » topic index » view message » categorize

Search



Quick Links

User menu

Not signed in.

Misc Menu