Re: possible bug in Cases/pattern matching??
- To: mathgroup at smc.vnet.net
- Subject: [mg6909] Re: [mg6859] possible bug in Cases/pattern matching??
- From: David Withoff <withoff>
- Date: Fri, 25 Apr 1997 14:00:39 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
> I am getting some very strange behavior when using Cases and
> replacement rules on a moderately long, but not horribly long
> expression. When I use the expression bound to "tester" (below) in a
> variety of ways (also shown below), Mathematica just goes off into
> hyperspace and cannot even be properly interrupted, only aborted.
>
> I can make the expression just a little bit simpler and the correct
> answer is quickly returned, so I don't think it is a matter of
> insufficient memory or anything like that. I have the same problem
> under both mma2 and mma3 under solaris and linux, and under at least
> mma2 on a PC. Does this return the right answer for anyone? Anyone
> have any idea what is happening?? Would appreciate direct answers to
> kant at scicomp.com for speed as well as to the mailing list if desired.
>
> Much thanks.
> - Elaine Kant
>
> (*************************************************************)
>
> (* Give the expression tester, defined below, *)
>
> Cases[tester[[2]], xx_ + num_Real, Infinity]
>
> (* returns {}, correctly and virtually instantly (as does tester[[1]] etc),
> BUT
> *)
>
> Cases[tester, xx_ + num_Real, Infinity]
>
> (* goes off into hyperspace.
> In addition, the following works fine: *)
>
> Scan[Print[# /. (xx_ + num_Real :> xx+mcDouble[num])]&, tester[[2]]];
> Print[done];
>
> (* But this also seems to hang: *)
>
> tester[[2]] /. (xx_ + num_Real :> xx+mcDouble[num])
>
> (* here's the expression used *)
>
> tester = set[part[r1, i21, j1, k1], part[r1, i21, j1, k1] +
> part[U, -1 + i21, -1 + j1, -1 + k1]*part[SA1, 1, 0, 0, 0] +
> part[U, -1 + i21, -1 + j1, k1]*part[SA1, 1, 0, 0, 1] +
> part[U, -1 + i21, -1 + j1, 1 + k1]*part[SA1, 1, 0, 0, 2] +
> part[U, -1 + i21, j1, -1 + k1]*part[SA1, 1, 0, 1, 0] +
> part[U, -1 + i21, j1, k1]*part[SA1, 1, 0, 1, 1] +
> part[U, -1 + i21, j1, 1 + k1]*part[SA1, 1, 0, 1, 2] +
> part[U, -1 + i21, 1 + j1, -1 + k1]*part[SA1, 1, 0, 2, 0] +
> part[U, -1 + i21, 1 + j1, k1]*part[SA1, 1, 0, 2, 1] +
> part[U, -1 + i21, 1 + j1, 1 + k1]*part[SA1, 1, 0, 2, 2] +
> part[U, i21, -1 + j1, -1 + k1]*part[SA1, 1, 1, 0, 0] +
> part[U, i21, -1 + j1, k1]*part[SA1, 1, 1, 0, 1] +
> part[U, i21, -1 + j1, 1 + k1]*part[SA1, 1, 1, 0, 2] +
> part[U, i21, j1, -1 + k1]*part[SA1, 1, 1, 1, 0] +
> part[U, i21, j1, k1]*part[SA1, 1, 1, 1, 1] +
> part[U, i21, j1, 1 + k1]*part[SA1, 1, 1, 1, 2] +
> part[U, i21, 1 + j1, -1 + k1]*part[SA1, 1, 1, 2, 0] +
> part[U, i21, 1 + j1, k1]*part[SA1, 1, 1, 2, 1] +
> part[U, i21, 1 + j1, 1 + k1]*part[SA1, 1, 1, 2, 2] +
> part[U, 1 + i21, -1 + j1, -1 + k1]*part[SA1, 1, 2, 0, 0] +
> part[U, 1 + i21, -1 + j1, k1]*part[SA1, 1, 2, 0, 1] +
> part[U, 1 + i21, -1 + j1, 1 + k1]*part[SA1, 1, 2, 0, 2] +
> part[U, 1 + i21, j1, -1 + k1]*part[SA1, 1, 2, 1, 0] +
> part[U, 1 + i21, j1, k1]*part[SA1, 1, 2, 1, 1] +
> part[U, 1 + i21, j1, 1 + k1]*part[SA1, 1, 2, 1, 2] +
> part[U, 1 + i21, 1 + j1, -1 + k1]*part[SA1, 1, 2, 2, 0] +
> part[U, 1 + i21, 1 + j1, k1]*part[SA1, 1, 2, 2, 1] +
> part[U, 1 + i21, 1 + j1, 1 + k1]*part[SA1, 1, 2, 2, 2]];
>
> Print[Cases[tester[[2]], xx_ + num_Real, Infinity]];
> Scan[Print[# /. (xx_ + num_Real :> xx+mcDouble[num])]&, tester[[2]]];
> Print[done];
>
> (* trouble ahead *)
> Cases[tester, xx_ + num_Real, Infinity]
>
> (* tester[[2]] /. (xx_ + num_Real :> xx+mcDouble[num]) *)
>
> ====================================
>
> Elaine Kant
> SciComp Inc.
> 5806 Mesa Drive, Suite 250
> Austin, TX 78731
>
> email: kant at scicomp.com
> voice: 512-451-1430
> fax: 512-451-1622
> www: http://www.sig.net/~scicomp/
>
=====================================================================
This example will (in principle) finish, but the time required will
be rather large. You can get an estimate of the time by extrapolating
from shorter examples. Here are a few examples which show the trend.
In[2]:= Timing[
Take[tester[[2]], 10] /. xx_ + num_Real :> xx+mcDouble[num]][[1]]
Out[2]= 4.79619 Second
In[3]:= Timing[
Take[tester[[2]], 11] /. xx_ + num_Real :> xx+mcDouble[num]][[1]]
Out[3]= 14.6702 Second
In[4]:= Timing[
Take[tester[[2]], 12] /. xx_ + num_Real :> xx+mcDouble[num]][[1]]
Out[4]= 44.7598 Second
These examples show that the time increases by roughly a factor of 3
with each additional element taken from tester[[2]]. Since tester[[2]]
has 28 elements, a simple extrapolation suggests that the complete
calculation will finish in about 60 years.
I didn't have any trouble aborting this particular example, though.
If weren't able to abort this calculation, that's a separate problem.
If you don't want to wait 60 years, you can change the calculation so
that the pattern matcher doesn't have to try so many cases. The basic
idea is to do some simple tests, or to check some simple patterns, before
trying the pattern that you really want to use.
Here is one way to do that in your example. This rule is set up so that
the pattern matcher doesn't attempt to match xx_ + num_Real until it
has already checked that the expression has a head of Plus and that at
least one element in the expression has a head of Real.
In[6]:= Timing[Take[tester[[2]], 12] /.
p_Plus :> result /;
(MemberQ[Head /@ List @@ p, Real] &&
((result = p /. xx_ + num_Real ->
xx + mcDouble[num]) =!= p)) ][[1]]
Out[6]= 0.046868 Second
It could be argued (and I would certainly agree with this) that the
pattern matcher ought to do this automatically. It is unavoidable
that the pattern matcher will sometimes look through a large number
of cases, such as all possible element orderings in patterns that are
affected by the Orderless attribute, but in this example, the pattern
matcher is checking far more cases than it needs to check. I will
report this example to our development group so that it can be
investigated to see if something can be done about it.
In the meantime, I hope that the suggestion above is useful. The
basic idea of doing some simple tests before checking more complicated
patterns is useful in many examples involving pattern matching.
Dave Withoff
Wolfram Research