6
$\begingroup$

I have this bit of code that works, but it's very slow when there are 600k elements in the list:

mytbl = {};
ParallelDo{
   If[Flatten[left][[i]] == 1 || Flatten[left[[i]]==0,
     mytbl = AppendTo[mytbl, Flatten[left][[i]]];
   ];,
   {i, Length[Flatten[left]]}
];

Is there a significantly faster way to do this?

$\endgroup$
6
  • 6
    $\begingroup$ Take a look at Cases $\endgroup$
    – ssch
    Feb 5 '13 at 17:44
  • 4
    $\begingroup$ Append and AppendTo are notoriously slow because lists are array-like and have to be copied to increase their size. $\endgroup$
    – rcollyer
    Feb 5 '13 at 17:46
  • $\begingroup$ Wow Cases is very fast - thanks! $\endgroup$
    – Levi
    Feb 5 '13 at 17:50
  • 1
    $\begingroup$ I don't think that operating on a single structure from several parallel processes as you do here with ParallelDo is efficient or save. Compare i = {}; ParallelDo[i = {i, j}, {j, 1, 100}];i With the result you get for a standard Do. $\endgroup$ Feb 5 '13 at 23:11
  • $\begingroup$ Levi, your code is not executable (invalid syntax). Please correct it. $\endgroup$
    – Mr.Wizard
    Feb 6 '13 at 1:36
14
$\begingroup$

Some possibilities with their timings:

list = RandomInteger[{0, 10}, 600000];

Cases[list, 0 | 1]; // AbsoluteTiming

{0.065004, Null}

Select[list, # == 0 || # == 1 &]; // AbsoluteTiming

{0.865050, Null}

DeleteCases[list, Except[0 | 1]]; // AbsoluteTiming

{0.242014, Null}

Pick[list, # == 0 || # == 1 & /@ list]; // AbsoluteTiming

{0.922053, Null}

 Pick[list, list, 0 | 1]; // AbsoluteTiming

{0.189011, Null}

Replace[list, {0 -> 0, 1 -> 1, _ :> Sequence[]}, {1}]; // AbsoluteTiming

{0.213012, Null}

Replace[list, a_ :> Sequence[] /; Not[a == 0 || a == 1], {1}]; // AbsoluteTiming

{1.652095, Null}

Replace[list, Except[0 | 1] :> Sequence[] , {1}]; // AbsoluteTiming

{0.238014, Null}

$\endgroup$
1
  • $\begingroup$ @LeonidShifrin Oops; forgot to copy that. Thanks! $\endgroup$ Feb 6 '13 at 7:50
7
$\begingroup$

You may gain some additional speed by compiling the expression at hand, in the example given by Sjoerd it is about one order of magnitude when compiled to C.

cf = Compile[{{in, _Integer, 1}},
   Block[{newList = Internal`Bag[Most[{0}]]},
    Do[
     If[in[[i]] == 0 || in[[i]] == 1, 
      Internal`StuffBag[newList, in[[i]]];]
     , {i, Length[in]}];
    Internal`BagPart[newList, All]
    ]
   , CompilationTarget -> "C"
   ];

list = RandomInteger[{0, 10}, 600000];
(res1 = Cases[list, 0 | 1];) // AbsoluteTiming
(res2 = cf[list];) // AbsoluteTiming
res1 === res2

(*
{0.070894, Null}
{0.007514, Null}
res1 === res2
*)

An explanation of the compiled code can be found here.

$\endgroup$
4
$\begingroup$

You can gain almost an order of magnitude improvement using Pick with UnitStep:

list = RandomInteger[{0,10}, 10^6];

r1 = Cases[list, 0|1]; //RepeatedTiming
r2 = Pick[list, UnitStep[list-2], 0]; //RepeatedTiming

r1===r2

{0.060, Null}

{0.0078, Null}

True

$\endgroup$
4
  • $\begingroup$ +1. I'm surprised no one had posted a UnitStep solution -- it's been used so many times elsewhere on the site! Note it's not clear whether the integers are nonnegative in the OP, but r2 = Pick[list, UnitStep[list] UnitStep[1 - list], 1] is still quite a bit faster. $\endgroup$
    – Michael E2
    Jan 4 '18 at 4:45
  • $\begingroup$ And this works on reals, too: Pick[list, Unitize[list] Unitize[list - 1], 0]. $\endgroup$
    – Michael E2
    Jan 4 '18 at 5:22
  • 1
    $\begingroup$ @MichaelE2 In addition to UnitStep, there are variations with Ramp, Clip, Sign, Unitize etc that could be used. It's not always clear which version is optimal. $\endgroup$
    – Carl Woll
    Jan 4 '18 at 5:40
  • $\begingroup$ @CarlWoll thanks for mentioning answer with UnitStep ! when i write my code now I try to see if any of these functions can be used $\endgroup$
    – Ali Hashmi
    Jan 4 '18 at 13:48
1
$\begingroup$

Pick using Boole to construct the selector array is almost as good as Cases:

list = RandomInteger[{0, 10}, 600000];
casesLst = Cases[list, 0 | 1]; // AbsoluteTiming
(* {0.057006, Null} *)
pickBooleLst = Pick[list, Boole[# == 0 || # == 1] & /@ list, 1]; // AbsoluteTiming
(*  {0.063006, Null} *)
pickLst1 = Pick[list, list, 0 | 1]; // AbsoluteTiming
(*  {0.142014, Null} *)
pickLst2 = Pick[list, # == 0 || # == 1 & /@ list]; // AbsoluteTiming
(* {0.866087, Null} *)
casesLst == pickBooleLst
(*  True *)
$\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.