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

Question

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}, 
     Heads -> False]];
  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

Answer 1

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]

Compare with your solutions:

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