# 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 '13 at 17:44
Append and AppendTo are notoriously slow because lists are array-like and have to be copied to increase their size. – rcollyer Feb 5 '13 at 17:46
Wow Cases is very fast - thanks! – Levi Feb 5 '13 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. – Sjoerd C. de Vries Feb 5 '13 at 23:11
Levi, your code is not executable (invalid syntax). Please correct it. – Mr.Wizard Feb 6 '13 at 1:36

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

-

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.

-

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! – Sjoerd C. de Vries Feb 6 '13 at 7:50