# Efficiently keeping elements in a list (an input list) that exist in another list (a keep list)

I have some code that generates lists of integers (one such list is called, for example, inputList). I also have a "master list" of integers that should be kept, if present, in keepList.

I would like to write a function keepElements that keeps integers in inputList that exist in keepList. Alternatively, I could write a function removeElements that removes elements from inputList that do not exist in keepList. Since keepElements and removeElements generate the same output list, I will use whichever is faster.

Below is a sort of minimal working example. In the first section of code, I generate inputList and keepList (I have used RandomInteger in this example, just to generate keepList). Note that even in my actual code, inputList and keepList are both in sorted ascending order. I have written keepElements and removeElements, but I am wondering if you can please help me make them faster. I will need to run either function approximately 200,000 times, so this can quite expensive and I would like to minimize the cost as much as possible.

Do you have any advice? Using Position is probably relatively expensive, so I should perhaps avoid using it. Thank you for your time!

minVal = 1;
maxVal = 1000;
inputList = Range[minVal, maxVal];
keepList =
DeleteDuplicates[
Sort[Table[RandomInteger[{minVal, maxVal}], {500}]]];

keepElements[inputList_, keepList_] := Module[{position},
position =
Flatten[Position[inputList, _?(MemberQ[keepList, #] &), {1},
inputList[[position]]
]
keepElements[inputList, keepList] // Timing // First

removeElements[inputList_, keepList_] :=
DeleteCases[inputList, _?(! MemberQ[keepList, #] &)]
removeElements[inputList, keepList] // Timing // First


which on my machine gives the output:

0.031

0.016

-
Much faster: keepElements2[inputList_, keepList_] := Cases[inputList, Alternatives @@ keepList] – Daniel Lichtblau Aug 31 '12 at 17:10

The function you're looking for is Intersection:

Since you say that your lists are already sorted, this will probably be the most efficient solution. All you need to do is:

Intersection[inputList, keepList]


keepElements[inputList, keepList] ==
removeElements[inputList, keepList] ==
Intersection[inputList, keepList]
(* True *)


and the timings:

keepElements[inputList, keepList]; // Timing // First
removeElements[inputList, keepList]; // Timing // First
Intersection[inputList, keepList]; // Timing // First

(* 0.008921
0.012487
0.000035 *)

-
beat me by a toad's jump – Dr. belisarius Aug 31 '12 at 17:12
I was about to answer that – Rojo Aug 31 '12 at 17:12
@Rojo I was in the queue first – Dr. belisarius Aug 31 '12 at 17:13
@Verde, it's a stack so I'm first – Rojo Aug 31 '12 at 17:24