Write to EXCEL from SQL DB using VBA script

How to assert on pagereference where the endpoint of pagereference is predefined

Selecting a secure PIN for building access

If an enemy is just below a 10-foot-high ceiling, are they in melee range of a creature on the ground?

Why is the SNP putting so much emphasis on currency plans?

How did Captain America use this power?

Visa for volunteering in England

I caught several of my students plagiarizing. Could it be my fault as a teacher?

When do aircrafts become solarcrafts?

Unidentified items in bicycle tube repair kit

Applying a function to a nested list

Is it always OK to ask for a copy of the lecturer's slides?

What happened to Ghost?

Password expiration with Password manager

Is thermodynamics only applicable to systems in equilibrium?

How to reply this mail from potential PhD professor?

Pressure to defend the relevance of one's area of mathematics

Field Length Validation for Desktop Application which has maximum 1000 characters

Accidentally deleted the "/usr/share" folder

Why do freehub and cassette have only one position that matches?

Pigeonhole Principle Problem

How do I tell my manager that his code review comment is wrong?

Transfer over $10k

Airbnb - host wants to reduce rooms, can we get refund?

ls Ordering[Ordering[list]] optimal?

Ordering problemHelp with PermutationsSort strings by natural orderingOrdering function with recognition of duplicatesNon-canonical re-ordering of nested listsAn efficient way to merge a pair of 4d arrays of non regular length listsMax element of a list with a custom ordering functionFinding pairs where the intersection of them is empty set from a nested listLexicographic ordering of lists-of-lists?Ordering elements of a list

11

5

$begingroup$

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?

---

benchmarks

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 *)

list-manipulation performance-tuning sorting permutation

share|improve this question

edited Mar 29 at 17:18

Roman

asked Mar 28 at 10:57

RomanRoman

6,58111134

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Have you tried out PermutationList[FindPermutation[list]] or InversePermutation[Ordering[list]]?
  $endgroup$
  – J. M. is away♦
  Mar 28 at 11:45
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks @J.M.isslightlypensive . I think that your use of InversePermutation on a permutation list instead of a permutation is undocumented. It's the fastest solution though. How do you know about all these undocumented tricks?
  $endgroup$
  – Roman
  Mar 29 at 13:44
  
  

  
  
  
  

add a comment | 

11

5

$begingroup$

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?

---

benchmarks

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 *)

list-manipulation performance-tuning sorting permutation

share|improve this question

edited Mar 29 at 17:18

Roman

asked Mar 28 at 10:57

RomanRoman

6,58111134

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Have you tried out PermutationList[FindPermutation[list]] or InversePermutation[Ordering[list]]?
  $endgroup$
  – J. M. is away♦
  Mar 28 at 11:45
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks @J.M.isslightlypensive . I think that your use of InversePermutation on a permutation list instead of a permutation is undocumented. It's the fastest solution though. How do you know about all these undocumented tricks?
  $endgroup$
  – Roman
  Mar 29 at 13:44
  
  

  
  
  
  

add a comment | 

$begingroup$

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?

---

benchmarks

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 *)

list-manipulation performance-tuning sorting permutation

share|improve this question

edited Mar 29 at 17:18

Roman

asked Mar 28 at 10:57

RomanRoman

6,58111134

$endgroup$

list = "A", "B", "D", "C", "Z", "W";
Position[Sort[list], #][[1, 1]] & /@ list

Ordering[Ordering[list]]

list = 2, 10, 1, 4, 8, 6, 3, 9, 5, 7;
Ordering[Ordering[list]]

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 *)

share|improve this question

edited Mar 29 at 17:18

Roman

asked Mar 28 at 10:57

RomanRoman

6,58111134

share|improve this question

edited Mar 29 at 17:18

Roman

asked Mar 28 at 10:57

RomanRoman

6,58111134

asked Mar 28 at 10:57

RomanRoman

6,58111134

asked Mar 28 at 10:57

RomanRoman

6,58111134

1 Answer
1

active

oldest

votes

11

$begingroup$

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

Edit

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

share|improve this answer

edited Mar 30 at 9:34

J. M. is away♦

99k10311469

answered Mar 28 at 11:21

Henrik SchumacherHenrik Schumacher

61.3k585171

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This solution cuts the effort down from two function calls to one function call plus one indexed substitution (very fast). 90% of what I was looking for, thanks!
  $endgroup$
  – Roman
  Mar 28 at 12:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You're welcome.
  $endgroup$
  – Henrik Schumacher
  Mar 28 at 12:46
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks Henrik, I hadn't even checked J.M.'s second solution because I expected (according to the documentation) that InversePermutation spits out a permutation, not a permutation list. But that's not the case when you feed it a permutation list.
  $endgroup$
  – Roman
  Mar 29 at 13:51
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "387"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f194094%2fls-orderingorderinglist-optimal%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

11

$begingroup$

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

Edit

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

share|improve this answer

edited Mar 30 at 9:34

J. M. is away♦

99k10311469

answered Mar 28 at 11:21

Henrik SchumacherHenrik Schumacher

61.3k585171

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This solution cuts the effort down from two function calls to one function call plus one indexed substitution (very fast). 90% of what I was looking for, thanks!
  $endgroup$
  – Roman
  Mar 28 at 12:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You're welcome.
  $endgroup$
  – Henrik Schumacher
  Mar 28 at 12:46
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks Henrik, I hadn't even checked J.M.'s second solution because I expected (according to the documentation) that InversePermutation spits out a permutation, not a permutation list. But that's not the case when you feed it a permutation list.
  $endgroup$
  – Roman
  Mar 29 at 13:51
  

  
  
  
  

add a comment | 

11

$begingroup$

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

Edit

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

share|improve this answer

edited Mar 30 at 9:34

J. M. is away♦

99k10311469

answered Mar 28 at 11:21

Henrik SchumacherHenrik Schumacher

61.3k585171

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This solution cuts the effort down from two function calls to one function call plus one indexed substitution (very fast). 90% of what I was looking for, thanks!
  $endgroup$
  – Roman
  Mar 28 at 12:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You're welcome.
  $endgroup$
  – Henrik Schumacher
  Mar 28 at 12:46
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks Henrik, I hadn't even checked J.M.'s second solution because I expected (according to the documentation) that InversePermutation spits out a permutation, not a permutation list. But that's not the case when you feed it a permutation list.
  $endgroup$
  – Roman
  Mar 29 at 13:51
  

  
  
  
  

add a comment | 

$begingroup$

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

Edit

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

share|improve this answer

edited Mar 30 at 9:34

J. M. is away♦

99k10311469

answered Mar 28 at 11:21

Henrik SchumacherHenrik Schumacher

61.3k585171

$endgroup$

list = RandomReal[-1, 1, 1000000];

First@RepeatedTiming[
 a[[Ordering[list]]] = a = Range[Length[list]];
 ]

First@RepeatedTiming[
 b = Ordering[Ordering[list]]
 ]

a == b

c = InversePermutation[Ordering[list]]; // RepeatedTiming // First

c == b

share|improve this answer

edited Mar 30 at 9:34

J. M. is away♦

99k10311469

answered Mar 28 at 11:21

Henrik SchumacherHenrik Schumacher

61.3k585171

edited Mar 30 at 9:34

J. M. is away♦

99k10311469

edited Mar 30 at 9:34

J. M. is away♦

99k10311469

answered Mar 28 at 11:21

Henrik SchumacherHenrik Schumacher

61.3k585171

answered Mar 28 at 11:21

Henrik SchumacherHenrik Schumacher

61.3k585171