0
$\begingroup$

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

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

3 Answers 3

2
$\begingroup$

Another approach:

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

xyz2 = Function[array
  , 0 != # & /@ Times @@@ Unitize[
        Ordering /@ array - ConstantArray[Range[6], 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

$\endgroup$
1
  • $\begingroup$ Good really fast and sharp! I made the way step by step to understand and learn. Really thankful Kuba! $\endgroup$ Commented Aug 21, 2017 at 12:23
2
$\begingroup$

A simple change but considerable timing improvement.

abc[lst_List] :=
 If[Apply[Times, Ordering[lst] - Range@Length@lst] != 0,
  True, False]
$\endgroup$
4
  • $\begingroup$ Using OrderedQ[] might be more direct. $\endgroup$ Commented Aug 21, 2017 at 11:43
  • $\begingroup$ @Chris Degnen Really good improovement, I can see MapIndexed is slow. Thanks $\endgroup$ Commented Aug 21, 2017 at 11:49
  • $\begingroup$ @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. $\endgroup$
    – Kuba
    Commented Aug 21, 2017 at 11:54
  • 1
    $\begingroup$ Also the If[...,True,False] idiom doesn't do anything and can be removed. $\endgroup$ Commented Aug 21, 2017 at 12:17
2
$\begingroup$

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[]},
   p = AssociationThread[alphabet -> Range[Length[alphabet]]];
   ldldp = Table[RandomSample[alphabet, 6], 10^5];
   ]; // AbsoluteTiming
data = Developer`ToPackedArray[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 *)
$\endgroup$

Your Answer

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

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