# Delete elements from a list really fast

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?

• Take a look at Cases
– ssch
Feb 5, 2013 at 17:44
• Append and AppendTo are notoriously slow because lists are array-like and have to be copied to increase their size. Feb 5, 2013 at 17:46
• Wow Cases is very fast - thanks!
– Levi
Feb 5, 2013 at 17:50
• 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. Feb 5, 2013 at 23:11
• Levi, your code is not executable (invalid syntax). Please correct it. Feb 6, 2013 at 1:36

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}

• @LeonidShifrin Oops; forgot to copy that. Thanks! Feb 6, 2013 at 7:50

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 = InternalBag[Most[{0}]]},
Do[
If[in[[i]] == 0 || in[[i]] == 1,
InternalStuffBag[newList, in[[i]]];]
, {i, Length[in]}];
InternalBagPart[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.

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

• +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. Jan 4, 2018 at 4:45
• And this works on reals, too: Pick[list, Unitize[list] Unitize[list - 1], 0]. Jan 4, 2018 at 5:22
• @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. Jan 4, 2018 at 5:40
• @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 Jan 4, 2018 at 13:48

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