7
$\begingroup$

Problem description: Given a list $A=\{1,2,0,7,0,-1,2,6,\ldots\}$ and a list $B=\{0,7,0\}$ write a program that determines whether $B$ appears in $A$ or not. Note: the order of $B$'s items does matter.

Functional way:

MemberQ[Partition[A, 3, 1], B]

The disadvantage of this way is that the whole list $A$ is processed even if $B$ is in the very start of $A$. Compare with the following code which terminates early if $B$ is found in $A$:

Procedural way:

found = False;
L = Length@A;
For[i = 1, i <= (L - 2) && !found, i++,
found = Take[A, {i, i + 2}] == B]

Question: Is there a functional way of solving the problem that does not need to scan/process all of $A$'s elements ?

P.S. Feel free to edit the title.

$\endgroup$
  • $\begingroup$ Not very efficient a = {1, 2, 3, 4}; b = {2, 3, 4}; MatchQ[a, {___, PatternSequence @@ b, ___}] A Boyer-Moore type alg should be better $\endgroup$ – Dr. belisarius Nov 26 '15 at 21:36
  • $\begingroup$ @belisariushassettled. On cursory reading about Boyer-Moore, it says that there is pre-processing done on the list in order to reduce the number of comparisons done. OP doesn't seem to want pre-processing (though your observation might mean that the OP should want pre-processing instead!). $\endgroup$ – march Nov 26 '15 at 21:50
  • 2
    $\begingroup$ @march Boyer-Moore preprocesses the needle (i.e., $B$), not the haystack ($A$). $\endgroup$ – Pillsy Nov 26 '15 at 21:52
  • $\begingroup$ @Pillsy. That's why one shouldn't post comments after a "cursory reading". $\endgroup$ – march Nov 26 '15 at 21:53
  • 2
    $\begingroup$ @march I was looking for a good example stackoverflow.com/a/6209778/353410 $\endgroup$ – Dr. belisarius Nov 26 '15 at 21:55
10
$\begingroup$

More recent (10.1+) versions of Mathematica feature the SequencePosition function, which can be told to stop after the first match, like so:

SeedRandom[1337];
a = RandomInteger[{1, 10}, 10000];
b = {1, 7, 1};

SequencePosition[a, b, 1] // AbsoluteTiming
(* {0.000175, {{88, 90}}} *)

This is quite a bit faster than the MemberQ/Partition-based approach:

MemberQ[Partition[a, 3, 1], b, {1}] // AbsoluteTiming
(* {0.00199, True} *)

As a word of warning, you can use more general patterns with SequencePosition and similar functions, but as of version 10.3 the performance is only really good with fixed patterns like {1, 7, 1}.

EDIT to add: It seems to provide a similar speedup over other solutions, like in @belisarius' comment:

MatchQ[a, {___, PatternSequence @@ b, ___}] // AbsoluteTiming
(* {0.019747, True} *)
$\endgroup$
  • 1
    $\begingroup$ I'm on V9- Could you please compare this with my cheap solution on the comments? I guess this one is faster, but I'm curious about the improvement $\endgroup$ – Dr. belisarius Nov 26 '15 at 22:02
  • 1
    $\begingroup$ @belisariushassettled on my OS X box with 10.3 this method was Timing 0.000548 whereas the MatchQ timing was 0.027489 $\endgroup$ – Mike Honeychurch Nov 26 '15 at 22:04
  • $\begingroup$ @MikeHoneychurch Thanks a lot! $\endgroup$ – Dr. belisarius Nov 26 '15 at 22:04
  • 1
    $\begingroup$ and the NestWhile methods were 0.019667 with the same a and b lists $\endgroup$ – Mike Honeychurch Nov 26 '15 at 22:06
  • $\begingroup$ you seem to be only seeing a bit over an order of magnitude enhancement whereas on my computer after clearing cache etc. I am seeing two orders of magnitude (??) $\endgroup$ – Mike Honeychurch Nov 26 '15 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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