# Overlap between lists of sublists with different dimensions

I have two lists of sublists. The sublists in the first list contain three elements while the points in the second list contain four e.g.:

list3dim={{1.3,0.1, 140.0},{1.4,0.1,140.0},...};
list4dim={{1.2,0.1, 140.0,5.13},{1.4,0.1,140.0,6.34},...};


I want to select the sublists in the list4dim where the first three elements are a sublist of listdim3. For the example the result should be:

{{1.4,0.1,140.0,6.34},...}


So far I found a slow solution by using MemberQ:

SelectOverlap[list4dim_, list3dim_] :=
Select[list4dim, MemberQ[list3dim[[All,1 ;; 3]], #[[1;;3]]] &]


My question is if there is a faster way to do this because my lists are very long.

as pointed out by Jason B. and in reference to paw this solution gives the best performance so far:

SelectOverlap =
Compile[{{list4dim, _Real, 2}, {list3dim, _Real, 2}},
Select[list4dim, MemberQ[list3dim[[All, 1 ;; 3]], #[[1 ;; 3]]] &]];

• Can it be assumed that a list in list4dim and a subset list in list3dim will have the same position, or can they be scrambled? – J. M.'s technical difficulties Oct 28 '15 at 15:34
• Actually, you should remove it as an update, and just post it as an answer. Then accept that answer, since it is the fastest one presented here. – Jason B. Oct 30 '15 at 12:18

Generate a list of random numbers meeting OP's specifications:

list3dim = RandomReal[{1, 17}, {4000, 3}];
list4dim = RandomReal[{1, 17}, {14000, 4}];
Do[{n1, n2} = {RandomInteger[{1, Length@list3dim}],
RandomInteger[{1, Length@list4dim}]};
list4dim[[n2, ;; 3]] = list3dim[[n1]];
, {20}]


And then test a few sorting routines here. First, OP's sorting function

olap1 = SelectOverlap[list4dim, list3dim]; // AbsoluteTiming
(* {15.1939, Null} *)


Here is a method that is much faster, taking advantage of Intersection

selectOverlap[list4dim_, list3dim_] :=
list4dim[[Flatten[
Position[list4dim[[All, ;; 3]], #] & /@
Intersection[list3dim, list4dim[[All, ;; 3]]]]]];
olap2 = selectOverlap[list4dim, list3dim]; // AbsoluteTiming
(* {0.110414, Null} *)


Edit: As paw pointed out, it's possible to make this even faster using Compile:

selectOverlapComp =
Compile[{{list4dim, _Real, 2}, {list3dim, _Real, 2}},
list4dim[[Flatten[
Position[list4dim[[All, ;; -2]], #] & /@
Intersection[list3dim, list4dim[[All, ;; -2]]]]]]];
olap3 = selectOverlapComp[list4dim, list3dim]; // AbsoluteTiming
(* {0.014556, Null} *)


Of course you have to test that they are all giving the same answer

Sort[olap1] == Sort[olap2]
Sort[olap1] == Sort[olap3]
(* True *)
(* True *)

• Thank you very much! With listdim4 and listdim3 containing around 12k sublists your uncompiled version of selectOverlap takes 120s and is slower than my initial version using MemberQ which takes 40s. However your compiled version does the job in 14 seconds which is a nice speed-up. After compiling my version with MemberQ it just takes 7s. – M. Heuer Oct 30 '15 at 11:35
Composition[
Flatten[#, 1] &,
If[Length[#] > 1, Rest[#], Nothing] & /@ # &,
GatherBy[#, #[[;; 3]] &] &,
Join
][list3dim, list4dim]


Using lists generated by Jason B it seems to be twice as fast.