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
    $\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$ – Sjoerd C. de Vries 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$
  • $\begingroup$ @LeonidShifrin Oops; forgot to copy that. Thanks! $\endgroup$ – Sjoerd C. de Vries 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$
  • $\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.