Delete elements from a list really fast

Question

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?

Answer 1

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}

Answer 2

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.

Answer 3

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

Answer 4

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 *)