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
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
$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
asked Mar 28 at 10:57
RomanRoman
6,58111134
$endgroup$
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
asked Mar 28 at 10:57
RomanRoman
6,58111134
$endgroup$
2
$begingroup$
Have you tried outPermutationList[FindPermutation[list]]orInversePermutation[Ordering[list]]?
$endgroup$
– J. M. is away♦
Mar 28 at 11:45
$begingroup$
Thanks @J.M.isslightlypensive . I think that your use ofInversePermutationon 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
asked Mar 28 at 10:57
RomanRoman
6,58111134
$endgroup$
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
list-manipulation performance-tuning sorting permutation
asked Mar 28 at 10:57
RomanRoman
6,58111134
asked Mar 28 at 10:57
RomanRoman
6,58111134
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
6,58111134
2
$begingroup$
Have you tried outPermutationList[FindPermutation[list]]orInversePermutation[Ordering[list]]?
$endgroup$
– J. M. is away♦
Mar 28 at 11:45
$begingroup$
Thanks @J.M.isslightlypensive . I think that your use ofInversePermutationon 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 |
2
$begingroup$
Have you tried outPermutationList[FindPermutation[list]]orInversePermutation[Ordering[list]]?
$endgroup$
– J. M. is away♦
Mar 28 at 11:45
$begingroup$
Thanks @J.M.isslightlypensive . I think that your use ofInversePermutationon 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
2
2
$begingroup$
Have you tried out
PermutationList[FindPermutation[list]] or InversePermutation[Ordering[list]]?$endgroup$
– J. M. is away♦
Mar 28 at 11:45
$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
$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 |
1 Answer
1
active
oldest
votes
$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
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) thatInversePermutationspits 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
);
);
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
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
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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
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) thatInversePermutationspits 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
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) thatInversePermutationspits 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
edited Mar 30 at 9:34
J. M. is away♦
99k10311469
answered Mar 28 at 11:21
Henrik SchumacherHenrik Schumacher
61.3k585171
$endgroup$
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
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
edited Mar 30 at 9:34
J. M. is away♦
99k10311469
99k10311469
answered Mar 28 at 11:21
Henrik SchumacherHenrik Schumacher
61.3k585171
answered Mar 28 at 11:21
Henrik SchumacherHenrik Schumacher
61.3k585171
answered Mar 28 at 11:21
Henrik SchumacherHenrik Schumacher
61.3k585171
61.3k585171
$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) thatInversePermutationspits 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$
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) thatInversePermutationspits 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
$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$
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$
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
$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 |
Thanks for contributing an answer to Mathematica Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
Have you tried out
PermutationList[FindPermutation[list]]orInversePermutation[Ordering[list]]?$endgroup$
– J. M. is away♦
Mar 28 at 11:45
$begingroup$
Thanks @J.M.isslightlypensive . I think that your use of
InversePermutationon 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