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
    Aug 21, 2017 at 11:38
  • $\begingroup$ @Kuba Yes, all sublists have the same number of elements $\endgroup$ Aug 21, 2017 at 11:42
  • $\begingroup$ Do you really have to multiply? tst[lst_] := FreeQ[Ordering[lst] - Range[Length[lst]], 0] $\endgroup$ Aug 21, 2017 at 13:14
  • $\begingroup$ @ J.M. Of course I don't need, good this run clear, sharp thanks sincerely $\endgroup$ 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$ 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$ Aug 21, 2017 at 11:43
  • $\begingroup$ @Chris Degnen Really good improovement, I can see MapIndexed is slow. Thanks $\endgroup$ 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
    Aug 21, 2017 at 11:54
  • 1
    $\begingroup$ Also the If[...,True,False] idiom doesn't do anything and can be removed. $\endgroup$ 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.