Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

share|improve this question
6  
Much faster: keepElements2[inputList_, keepList_] := Cases[inputList, Alternatives @@ keepList] –  Daniel Lichtblau Aug 31 '12 at 17:10
add comment

1 Answer 1

up vote 9 down vote accepted

The function you're looking for is Intersection:

enter image description here

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 *)
share|improve this answer
    
beat me by a toad's jump –  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 –  belisarius Aug 31 '12 at 17:13
3  
@Verde, it's a stack so I'm first –  Rojo Aug 31 '12 at 17:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.