Given a large list of $n$ dimensional sublists where each sublist has integer elements I am trying to find the quickest way of finding all sublists that satisfy some constraint on their elements.
A typical constraint would be that a sublist sums to zero.
I have tried three ways - Pick with Unitize, Pick with Clip and compiling Select.
They all seem to have similar timings. The two Pick methods are somewhat faster for $n<6$ but compiling Select is faster for larger $n$.
Does anyone have a faster way of doing this? Especially when $n \ge6$?
(* n = 3 case *)
arr = RandomInteger[{-100, 100}, {10000000, 3}];
constraint = #[[1]] + #[[2]] + #[[3]] == 0 &;
compile =
With[{criteria = constraint},
Compile[{{input, _Integer, 2}}, Select[input, criteria],
CompilationTarget -> "C", RuntimeOptions -> "Speed"]];
try1 = Pick[arr,
Unitize[#[[All, 1]] + #[[All, 2]] + #[[All, 3]] &@arr], 0]; //
RepeatedTiming // First
try2 = compile[arr]; // RepeatedTiming // First
try3 = Pick[arr,
1 -
Clip[#[[All, 1]] + #[[All, 2]] + #[[All, 3]] &@arr, {0, 0}, {1,
1}], 1]; // RepeatedTiming // First
try1 == try2 == try3
(*
0.200528
0.379881
0.222603
True
*)
and
(* n = 9 case *)
arr2 = RandomInteger[{-100, 100}, {10000000, 9}];
constraint = #[[1]] + #[[2]] + #[[3]] + #[[4]] + #[[5]] + #[[6]] + \
#[[7]] + #[[8]] + #[[9]] == 0 &;
compile =
With[{criteria = constraint},
Compile[{{input, _Integer, 2}}, Select[input, criteria],
CompilationTarget -> "C", RuntimeOptions -> "Speed"]];
try1 = Pick[arr2,
Unitize[#[[All, 1]] + #[[All, 2]] + #[[All, 3]] + #[[All,
4]] + #[[All, 5]] + #[[All, 6]] + #[[All, 7]] + #[[All,
8]] + #[[All, 9]] &@arr2], 0]; // RepeatedTiming // First
try2 = compile[arr2]; // RepeatedTiming // First
try3 = Pick[arr2,
1 -
Clip[#[[All, 1]] + #[[All, 2]] + #[[All, 3]] + #[[All,
4]] + #[[All, 5]] + #[[All, 6]] + #[[All, 7]] + #[[All,
8]] + #[[All, 9]] &@arr2, {0, 0}, {1, 1}], 1]; //
RepeatedTiming // First
try1 == try2 == try3
(*
0.59877
0.446898
0.615144
True
*)
I am not sure of the etiquette on here in regard to extending the question and have received some great responses in the comments so far.
But as a matter of interest - instead of the summing to zero constraint - what would be a fast method of constraining the first $n-1$ elements to be in ascending order?
i.e $ element[[1]] \le element[[2]] \le \dots element[[n-1]]$ in a sublist?
Pick[arr, Total[arr, {2}], 0]
$\endgroup$Pick[arr, arr.Table[1, Length[arr[[1]]]], 0]
$\endgroup$arr . (1 & /@ arr[[1]])
. Also might be worth checking ConstantArray vs Table, e . garr.ConstantArray[1, n]
$\endgroup$Total
was developed by Anton Antonov under the supervision of Rob Knapp. See here for an interesting post by AA. Before the development ofTotal
, a trick was to useTr
(now considered slow). See the entry forTr
in Clever little programs by Ted Ersek. $\endgroup$