# Trying to avoid loops and improving function's speed

The target is to get a True for all lists that have all elements out of canonical order. First I wrote a For loop and then a function that has not loops

lcd[cc_List] := Module[{ccp = {}, cco = {}, i, lccp, res = 0, lcd},
ccp = cc;
cco = Sort[ccp];
lccp = Length[ccp];
For[i = 1, i <= lccp, i++, If[cco[[i]] == ccp[[i]], res++]];
lcd = If[res != 0, False, True];
lcd]


Then without

aeo[lst_List] :=
If[Apply [Times, Flatten[MapIndexed[# - #2 & , Ordering[lst]]]] != 0,
True, False]


Testing both with

ldldp = Table[RandomSample[Alphabet[], 6], 10^6];


Giving theese results

AbsoluteTiming[lcd /@ ldldp;]    {53.7615, Null}
AbsoluteTiming[aeo /@  ldldp;]   {49.6765, Null}


So my question is if is possible to use more efficient functions to do this job. Thanks

• Do sublists have fixed length? – Kuba Aug 21 '17 at 11:38
• @Kuba Yes, all sublists have the same number of elements – Anxon Pués Aug 21 '17 at 11:42
• Do you really have to multiply? tst[lst_] := FreeQ[Ordering[lst] - Range[Length[lst]], 0] – J. M.'s technical difficulties Aug 21 '17 at 13:14
• @ J.M. Of course I don't need, good this run clear, sharp thanks sincerely – Anxon Pués Aug 21 '17 at 13:45

Another approach:

xyz = Function[
array
,  Not /@ ( Or @@@ MapThread[SameQ, {array, Sort /@ array}, 2] )
]

xyz2 = Function[array
, 0 != # & /@ Times @@@ Unitize[
Ordering /@ array - ConstantArray[Range, Length@array]
]
]


ldldp = Table[RandomSample[Alphabet[], 6], 10^5];

(my2 = xyz2@ldldp); // AbsoluteTiming

(my = xyz @ ldldp); // AbsoluteTiming

(cd = abc /@ ldldp); // AbsoluteTiming

(op = lcd /@ ldldp); // AbsoluteTiming

my === m2 === cd === op


{0.186604, Null}

{0.273875, Null}

{0.629395, Null}

{2.13767, Null}

True

• Good really fast and sharp! I made the way step by step to understand and learn. Really thankful Kuba! – Anxon Pués Aug 21 '17 at 12:23

A simple change but considerable timing improvement.

abc[lst_List] :=
If[Apply[Times, Ordering[lst] - Range@Length@lst] != 0,
True, False]

• Using OrderedQ[] might be more direct. – J. M.'s technical difficulties Aug 21 '17 at 11:43
• @Chris Degnen Really good improovement, I can see MapIndexed is slow. Thanks – Anxon Pués Aug 21 '17 at 11:49
• @AnxonPués please take a tour. It is a good habit to hold on with an accept in order to not discourage others, but upvote instead. – Kuba Aug 21 '17 at 11:54
• Also the If[...,True,False] idiom doesn't do anything and can be removed. – Thies Heidecke Aug 21 '17 at 12:17

If you do not use but Integers, you make @Kuba's result even faster by employing the following CompiledFunction:

cxyz2 = Compile[{{a, _Integer, 1}},
Times @@ (Ordering[a] - Range[Length[a]]) != 0,
CompilationTarget -> "C",
RuntimeAttributes -> {Listable},
Parallelization -> True
];


On my machine (4 core), this is 20 times faster than xyz2.

Preparing the data

With[{alphabet = Alphabet[]},
ldldp = Table[RandomSample[alphabet, 6], 10^5];
]; // AbsoluteTiming
data = DeveloperToPackedArray[Map[Lookup[p, #] &, ldldp]]; // AbsoluteTiming

(* {0.097882, Null} *)


Conversion time is not insignificant, so this method relies on the fact that the encoding was in Integers in the first place.

(cmy2 = cxyz2@data); // AbsoluteTiming
(my2 = xyz2@ldldp); // AbsoluteTiming
(my = xyz@ldldp); // AbsoluteTiming
(cd = abc /@ ldldp); // AbsoluteTiming
(op = lcd /@ ldldp); // AbsoluteTiming
cmy2 === my === my2 === cd === op

(* {0.01136, Null} *)
(* {0.260086, Null} *)
(* {0.285857, Null} *)
(* {0.48367, Null} *)
(* {2.12977, Null} *)
(* True *)
`