Skip to main content
Mathematica

Return to Answer

added 439 characters in body
Source Link
LLlAMnYP
LLlAMnYP
  • 11.5k
  • 27
  • 66

Addendum:
I checked the performances of my Cases statement with the following test:

BenchmarkPlot[
 With[{r = {Range[3 #], Range[2 #, 4 #]}}, 
   Cases[First@r, Alternatives @@ (Last@r)]] &,
 # &,
 "IncludeFits" -> True]

enter image description here

O(n log(n)) is probably the bottleneck of this method and is quite a bit better than n^3.

Addendum:
I checked the performances of my Cases statement with the following test:

BenchmarkPlot[
 With[{r = {Range[3 #], Range[2 #, 4 #]}}, 
   Cases[First@r, Alternatives @@ (Last@r)]] &,
 # &,
 "IncludeFits" -> True]

enter image description here

O(n log(n)) is probably the bottleneck of this method and is quite a bit better than n^3.

Post Undeleted by LLlAMnYP
added 1085 characters in body
Source Link
LLlAMnYP
LLlAMnYP
  • 11.5k
  • 27
  • 66

Next filter out obviously invalid positions (by invalid, I mean, that x__ must end before y__?IntegerQ ends and z__ must begin after y__?IntegerQ starts):

This answer willNow is the tricky part which may be temporarily deletedvulnerable to "algorithmic explosion". From this list of positions I wish to select permissible end-points of every pattern.

pos = pos~Join~{Length[args] + 1};
Do[pos[[i]] = Cases[pos[[i]], Alternatives @@ (pos[[i + 1]] - 1)], {i, Length[pos] - 1}];
pos = Most@pos
(* {{100, 101}, {101, 102}, {200}} *)
Tuples@%
(* {{100, 101, 200}, {100, 102, 200}, {101, 101, 200}, {101, 102, 200}} *)
Select[%, # === Union@# &]
(* {{100, 101, 200}, {100, 102, 200}, {101, 102, 200}} *)

Let's return the possible ways the original pattern can match our symbol args:

Internal`PartitionRagged[args, Differences[{0}~Join~#]] & /@ %
(*{
   {{..., 100.}, {101}, {102, 103., 104., ...}},
   {{..., 100.}, {101, 102}, {103., 104., ...}},
   {{..., 100., 101}, {102}, {103., 104., ...}}
  }
*)

So by precomputing 200 tests it was possible to somewhat analytically reduce the number of combinations of arguments to 3, pending some incremental step in its writingrather than 14752 calls to IntegerQ.

This guide should work for any amount of BlankSequence but there's a lot of bulletproofing to do here as well as early detection of outright non-matches. Hopefully, this can be a starting point for further efforts.

Next filter out obviously invalid positions:

This answer will be temporarily deleted, pending some incremental step in its writing.

Next filter out obviously invalid positions (by invalid, I mean, that x__ must end before y__?IntegerQ ends and z__ must begin after y__?IntegerQ starts):

Now is the tricky part which may be vulnerable to "algorithmic explosion". From this list of positions I wish to select permissible end-points of every pattern.

pos = pos~Join~{Length[args] + 1};
Do[pos[[i]] = Cases[pos[[i]], Alternatives @@ (pos[[i + 1]] - 1)], {i, Length[pos] - 1}];
pos = Most@pos
(* {{100, 101}, {101, 102}, {200}} *)
Tuples@%
(* {{100, 101, 200}, {100, 102, 200}, {101, 101, 200}, {101, 102, 200}} *)
Select[%, # === Union@# &]
(* {{100, 101, 200}, {100, 102, 200}, {101, 102, 200}} *)

Let's return the possible ways the original pattern can match our symbol args:

Internal`PartitionRagged[args, Differences[{0}~Join~#]] & /@ %
(*{
   {{..., 100.}, {101}, {102, 103., 104., ...}},
   {{..., 100.}, {101, 102}, {103., 104., ...}},
   {{..., 100., 101}, {102}, {103., 104., ...}}
  }
*)

So by precomputing 200 tests it was possible to somewhat analytically reduce the number of combinations of arguments to 3, rather than 14752 calls to IntegerQ.

This guide should work for any amount of BlankSequence but there's a lot of bulletproofing to do here as well as early detection of outright non-matches. Hopefully, this can be a starting point for further efforts.

Post Deleted by LLlAMnYP
Source Link
LLlAMnYP
LLlAMnYP
  • 11.5k
  • 27
  • 66

This is an extended comment which may take some time to develop into an answer.

I'll focus on the O(n^3) algorithmic behavior observed on the benchmark plot and ways to combat that. I will not, however, handle the problem in the very first example (where four pattern tests were performed). I believe, one will need to essentially rewrite a pattern matcher, based on a more intelligent testing of conceivably valid combinations, in turn based on precomputed pattern tests.

Consider the example pattern {x__, y__?IntegerQ, z__}.

args = Range[1., 100.]~Join~{101, 102}~Join~Range[103., 200.];

Now I'll precompute the tests:

Boole@Through[{Map[True &], Map[IntegerQ], Map[True &]}[args]];

MapIndexed[# Last@#2 &, %, {2}];

pos = DeleteCases[%, 0, {2}];

And pos will have a list of lists, the first containing matching positions for x__, then for y__?IntegerQ, then for z__.

Next filter out obviously invalid positions:

Do[pos[[i]] = Select[pos[[i]], # < Max[pos[[i + 1]]] &];
  pos[[i + 1]] = Select[pos[[i + 1]], # > Min[pos[[i]]] &];, {i, 
   Length[pos] - 1}];
pos

(*
  {{1,2,...,101},
   {101,102},
   {102,103,...,200}}
*)

This answer will be temporarily deleted, pending some incremental step in its writing.