Given a list list
with unique elements, the task is to replace each element by its position in Sort[list]
. For example,
list = {"A", "B", "D", "C", "Z", "W"};
Position[Sort[list], #][[1, 1]] & /@ list
{1, 2, 4, 3, 6, 5}
Much more efficient is to call Ordering
twice:
Ordering[Ordering[list]]
{1, 2, 4, 3, 6, 5}
When applied on a permutation of Range[length]
this operation does nothing:
list = {2, 10, 1, 4, 8, 6, 3, 9, 5, 7};
Ordering[Ordering[list]]
{2, 10, 1, 4, 8, 6, 3, 9, 5, 7}
Question: is there a more efficient way of doing this operation, making a single function call instead of calling Ordering
twice?
Solutions are given from fastest to slowest:
L = RandomReal[{0, 1}, 10^7];
(* J.M.'s undocumented InversePermutation usage *)
R0 = InversePermutation[Ordering[L]]; // AbsoluteTiming // First
(* 2.39154 *)
(* Henrik Schumacher *)
R1[[Ordering[L]]] = R1 = Range[Length[L]]; //AbsoluteTiming//First
(* 2.42264 *)
(* original post *)
R2 = Ordering[Ordering[L]]; //AbsoluteTiming//First
(* 4.20186 *)
(* J.M. *)
R3 = PermutationList[InversePermutation[FindPermutation[L]]]; //AbsoluteTiming//First
(* 4.74717 *)
(* check *)
R0 == R1 == R2 == R3
(* True *)
Answer
No, Ordering[Ordering[list]]
not optimal. And yes, there is a faster method:
list = RandomReal[{-1, 1}, 1000000];
First@RepeatedTiming[
a[[Ordering[list]]] = a = Range[Length[list]];
]
First@RepeatedTiming[
b = Ordering[Ordering[list]]
]
a == b
0.13
0.236
True
J.M.'s second suggestion is more concise and at least as fast if not slightly faster:
c = InversePermutation[Ordering[list]]; // RepeatedTiming // First
c == b
0.124
True
Comments
Post a Comment