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, 2013 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, 2013 at 17:46
  • $\begingroup$ Wow Cases is very fast - thanks! $\endgroup$
    – Levi
    Feb 5, 2013 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, 2013 at 23:11
  • $\begingroup$ Levi, your code is not executable (invalid syntax). Please correct it. $\endgroup$
    – Mr.Wizard
    Feb 6, 2013 at 1:36

4 Answers 4

15
$\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, 2013 at 7:50
8
$\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, 2018 at 4:45
  • $\begingroup$ And this works on reals, too: Pick[list, Unitize[list] Unitize[list - 1], 0]. $\endgroup$
    – Michael E2
    Jan 4, 2018 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, 2018 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, 2018 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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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