4
$\begingroup$

My main problem consist in the creation of a sort function which wolud be used inside SortBy.


Introduction


The principle of the sort to apply is the following (for a list of points in 2 dimension) :

listosort = {{4, 9}, {-4, -9}, {-5, -7}, {-4, 4}, {-2, -1}, {-6, -9}, {-5, 0}};  
SortBy[listosort, {#[[1]], -#[[2]]} &];

We can noticed that :
- The sorting function allows you to sort columns by columns.
- The sorting function is a pure function.
- We can have an ascending or a descending sort with the use of 1 or -1.


Problem


I have to deal with the lists whose dimensions can vary. And I don't want to rewrite the pure function inside SortBy.

So I wrote the following code :

SPart[x_][y_] := Part[y, x];
ListSPart[x_] := (SPart[#] & /@ (Range@Length@x))*((x) /. {"max" -> 1, "min" -> 0});
SortVDL[x_, y_] := SortBy[x, ListSPart[y]]

So I can write now :

SortVDL[listosort, {1, -1}]
SortVDL[listosort, {"max", "min"}] (*equivalent*)

Instead of writing :

SortBy[listosort, {#[[1]], -#[[2]]} &];


Objectives


It's important to :
- Be able to handle list with elements of n dimensions.
- Be able to choose an ascending or descendand sorting for each column. - I don't need to treat list of non-numerical value.

Examples of possible writing :

SortVDL[listosort, {1, -1}]         (* 2D *)
SortVDL[listosort, {1, 1}]          (* 2D *)
SortVDL[listosort, {1, -1, 1, 1}]   (* 4D *)


Question


My code unfortunately does not work.

Indeed, the following lines of code :

SortVDL[listosort, {1, 1}];
SortBy[listosort, {#[[1]], #[[2]]} &];

SortVDL[listosort, {-1, 1}];
SortBy[listosort, {-#[[1]], #[[2]]} &];

SortVDL[listosort, {-1, -1}];
SortBy[listosort, {-#[[1]], -#[[2]]} &];

are not equivalent. SortVDL seems to always give the same result. Why ?
Is there a method to automatically generate reliable pure functions ?


Resume


Code n°1

F11[x_][y_] := Part[y, x];
F1[x_] := (F11[#] & /@ (Range@Length@x))*x;
F1[{1, -1, 1}];

Code n°2

F2[x_] := Function[Evaluate[Thread[F1[x] Slot /@ (ConstantArray[1, Length@x])]]];
F2[{1, -1, 1}];

Code n°3 (Xavier's answer)

F3[x_] := Activate[(Evaluate[x*Table[Inactive[Part][#, i], {i, Length@x}]]) &];
F3[{1, -1, 1}];

Code n°1 >> Don't work with SortBy >> See Xavier's answer.
Code n°2 >> Don't work with SortBy >> See Xavier's answer.
Code n°3 >> Work with SortBy >> See Xavier's answer.



Final Answer


Xavier's answer :

mySort[list_, coef_] := 
  SortBy[list, 
   Activate[(Evaluate[
       coef Table[
         Inactive[Part][#, i], {i, Dimensions[list][[2]]}]]) &]];

Ciao's answer :

numColSorter[list_, sortord_] := 
  list[[Ordering[Transpose[Transpose[list]*sortord]]]];

Benchmarks :

data1 = RandomInteger[{-9, 9}, {10^6, 2}];  

mySort >> 0.733489 s
numColSorter >> 0.282189 s

$\endgroup$
1
  • $\begingroup$ Don't have time right now to address the "...creation of a sort function..." aspect of this, but if the question changes to admit solving the end goal (arbitrary sorting by columns) by other means, there are efficient ways to do that... $\endgroup$
    – ciao
    Apr 18, 2016 at 6:22

2 Answers 2

4
$\begingroup$

This update addresses the why-questions about the codes 1, 2 and 3 in OP's Resume update. I will use the following list (reduced version of listosort) throughout the explanations:

list = {{4, 9}, {-4, -9}, {-5, -7}, {-4, 4}, {-6, -9}, {-5, 0}};

Code 1

F11[x_][y_] := Part[y, x];
F1[x_] := (F11[#] & /@ (Range@Length@x))*x;

Let's consider the list {1, -1} as argument. We have

SortBy[list, F1[{1, -1}]]
(* {{-6, -9}, {-5, -7}, {-5, 0}, {-4, -9}, {-4, 4}, {4, 9}} *)

SortBy[list, {#[[1]], -#[[2]]} &]
(* {{-6, -9}, {-5, 0}, {-5, -7}, {-4, 4}, {-4, -9}, {4, 9}} *)

To understand why this is happening, we can take a closer look at F1 and how SortBy effectively works.

a) The function F1 evaluates for {1, -1} to

F1[{1, -1}]
(* {F11[1], -F11[2]} *)

The second argument of SortBy can be a function (usage lines of the reference page), or a list of functions (section Details of the reference page). Here, F1[{1, -1}] evaluates to a list of function.

b) In the section Properties and Relations of SortBy, an effective equivalence is given:

SortBy[e, f] is equivalent to Sort[{f[#], #} & /@ e][[All, -1]]

For a list of functions, this translates to

SortBy[e, {f1, f2, ...}] is equivalent to Sort[{{f1[#], f2[#], ...}, #} & /@ e][[All, -1]]

Taking an arbitrary example for this last quote:

SortBy[list, {Abs, #[[2]] &}] === 
     Sort[{{Abs[#], #[[2]] &[#]}, #} & /@ list][[All, -1]]
(* True *)

Going back to F1, we can try this equivalence by writing (I'm using directly the output of F1[{1, -1}] given above)

SortBy[list, {F11[1], -F11[2]}] === 
    Sort[{{F11[1][#], -F11[2][#]}, #} & /@ list][[All, -1]]
(* False *)

This equivalence is not correct because the element -F11[2][#] is actually not of the form f2[#] (see the second quote above), with f2 corresponding to -F11[2]. In -F11[2][#], the part F11[2] is bound to [#] first, and then to -. The correct writing is instead

SortBy[list, {F11[1], -F11[2]}] === 
    Sort[{{F11[1][#], (-F11[2])[#]}, #} & /@ list][[All, -1]]
(* True *)

In this situation, which is the one of interest to understand why code 1 does not yield the expected result, the evaluation of (-F11[2])[#] for any element of list will not use the definition of F11. For instance consider:

(-F11[2])[First[list]]
(* (-F11[2])[{4, 9}] *)

SortBy will used expressions of this form to sort the elements of list when there is a tie on the first element of each sublist. The thing is that such a sorting will always be in the canonical order. We can see that from the equivalence with the one-argument form of Sort in the (second) quote above, and also in action with

SortBy[list, {F11[1], -F11[2]}] === SortBy[list, {F11[1]}]
(* True *)

Code 2

F2[x_] := Function[Evaluate[Thread[F1[x] Slot /@ (ConstantArray[1, Length@x])]]];

We consider again the list {1, -1} as argument. We have

SortBy[list, F2[{1, -1}]]
(* {{-6, -9}, {-5, 0}, {-5, -7}, {-4, -9}, {-4, 4}, {4, 9}} *)

SortBy[list, {#[[1]], -#[[2]]} &]
(* {{-6, -9}, {-5, 0}, {-5, -7}, {-4, 4}, {-4, -9}, {4, 9}} *)

Here the difference is due to the function constructed by F2. We have

F2[{1, -1}]
(* {F11[1] #1, -F11[2] #1} & *)

Using this time the first quote of the equivalence above:

SortBy[list, {F11[1] #, -F11[2] #} &] === 
    Sort[{{F11[1] #, -F11[2] #} &[#], #} & /@ list][[All, -1]]
(* True *)

The definition of F11 won't be used since we do not have an expression of the form F11[x][y]. What it is doing instead is evaluating elements of list as (for, e.g., {-4, -9} and {-4, 4}),

{F11[1] #, -F11[2] #} &[{-4, -9}]
(* {{-4 F11[1], -9 F11[1]}, {4 F11[2], 9 F11[2]}} *)

{F11[1] #, -F11[2] #} &[{-4, 4}]
(* {{-4 F11[1], 4 F11[1]}, {4 F11[2], -4 F11[2]}} *)

and sorting list in the canonical order with respect to these values. Indeed we have:

Order[%%, %]
(* 1 *)

This explains the difference we noted above.


Code 3 (see below the original post)

mySort[list_, coef_] := 
   SortBy[list, 
      Activate[(
         Evaluate[coef Table[Inactive[Part][#, i], {i, Dimensions[list][[2]]}]]
      ) &]
];

Taking again the argument {1, -1} for comparison, this time we get

SortBy[list, {#[[1]], -#[[2]]} &] === mySort[list, {1, -1}]
(* True *)

Here, the idea was to construct a function given to SortBy that won't be evaluated again and again for each element of list during the sorting process. Compare for instance with

mySort2[list_, coef_] := 
  SortBy[list, (coef Table[Part[#, i], {i, Dimensions[list][[2]]}]) &]

mySort[list, {1, -1}] === mySort2[list, {1, -1}]
(* True *)

SeedRandom[1];
ll = RandomInteger[10, {10^6, 2}];

mySort[ll, {1, -1}]; // AbsoluteTiming
(* {0.74406, Null} *)

mySort2[ll, {1, -1}]; // AbsoluteTiming
(* {0.845808, Null} *)

This is a small gain, but still. Anyhow, this is the reason for Evaluate in mySort. Since Part needs to be prevented from evaluating (otherwise it will return an error), I used Inactive and then Activate after the construction of the function.


Original post

mySort[list_, coef_] := 
   SortBy[list, 
          Activate[(
             Evaluate[coef Table[Inactive[Part][#, i], {i, Dimensions[list][[2]]}]]
          ) &]
   ];

Taking your examples,

listosort = {{4, 9}, {-4, -9}, {-5, -7}, {-4, 4}, {-2, -1}, {-6, -9}, {-5, 0}};

mySort[listosort, {1, 1}]
% === SortBy[listosort, {#[[1]], #[[2]]} &]

(* {{-6, -9}, {-5, -7}, {-5, 0}, {-4, -9}, {-4, 4}, {-2, -1}, {4, 9}} *)
(* True *)

mySort[listosort, {-1, 1}]
% === SortBy[listosort, {-#[[1]], #[[2]]} &]

(* {{4, 9}, {-2, -1}, {-4, -9}, {-4, 4}, {-5, -7}, {-5, 0}, {-6, -9}} *)
(* True *)

mySort[listosort, {-1, -1}]
% === SortBy[listosort, {-#[[1]], -#[[2]]} &]

(* {{4, 9}, {-2, -1}, {-4, 4}, {-4, -9}, {-5, 0}, {-5, -7}, {-6, -9}} *)
(* True *)
$\endgroup$
8
  • 1
    $\begingroup$ N.B.: This will fail for non-numeric values in the list to be sorted. Don't know if that matters to OP however. E.g., given {{1, aa}, {vv, vv}, {1, 5}, {aa, 5}, {5, vv}}, sorting as {1,-1}, yours gives {{1, 5}, {1, aa}, {5, vv}, {aa, 5}, {vv, vv}} and it should be {{1, aa}, {1, 5}, {5, vv}, {aa, 5}, {vv, vv}}. $\endgroup$
    – ciao
    Apr 18, 2016 at 6:19
  • $\begingroup$ @ciao Ah, good point. I think it depends on what OP means by {1, -1}. I interpret it as the coefficients to be allocated to {#[[1]], #[[2]]}, so the sorting {{1, 5}, {1, aa}, ...} would be correct. SortBy[{e1, e2, ...}, f] sorts its elements ei such that the f[ei] are in canonical order, and Order[{1, -5}, {1, -aa}] returns 1. If by -1 OP means "not in canonical order", I agree with you, my code is not correct. Perhaps OP could clarify this point. $\endgroup$
    – user31159
    Apr 18, 2016 at 11:45
  • $\begingroup$ Ciao _ I don't need to treat list with non-numeric values. Xavier _ Your interpretation is good. $\endgroup$
    – Doedalos
    Apr 18, 2016 at 19:23
  • $\begingroup$ @Xavier. Thank for your answer. $\endgroup$
    – Doedalos
    Apr 18, 2016 at 19:32
  • $\begingroup$ @Doedalos: In that case, numColSorter[list_, sortord_] := list[[Ordering[Transpose[Transpose[list]*sortord]]]]; is cleaner and faster... $\endgroup$
    – ciao
    Apr 18, 2016 at 21:50
0
$\begingroup$

First, DO NOT use uppercase to start a variable.

Second, does this work

sort[x_List] := SortBy[x, {#[[1]], #[[Dimensions[x][[2]]]]} &]
$\endgroup$
1
  • $\begingroup$ Thanks for your contribution ! Unfortunately, if your code can treat list with points of n dimensions, we can't choice an ascending/descending sort for each column. $\endgroup$
    – Doedalos
    Apr 17, 2016 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.