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

| improve this answer | |
$\endgroup$
  • $\begingroup$ Good really fast and sharp! I made the way step by step to understand and learn. Really thankful Kuba! $\endgroup$ – Anxon Pués Aug 21 '17 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]
| improve this answer | |
$\endgroup$
  • $\begingroup$ Using OrderedQ[] might be more direct. $\endgroup$ – J. M.'s technical difficulties Aug 21 '17 at 11:43
  • $\begingroup$ @Chris Degnen Really good improovement, I can see MapIndexed is slow. Thanks $\endgroup$ – Anxon Pués Aug 21 '17 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 '17 at 11:54
  • 1
    $\begingroup$ Also the If[...,True,False] idiom doesn't do anything and can be removed. $\endgroup$ – Thies Heidecke Aug 21 '17 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 *)
| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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