Re: Re: possible bug in Cases/pattern matching??
- To: mathgroup at smc.vnet.net
- Subject: [mg6961] Re: [mg6909] Re: [mg6859] possible bug in Cases/pattern matching??
- From: Richard Gass <gass at physics.uc.edu>
- Date: Wed, 30 Apr 1997 22:25:17 -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
Dave,
Your estimate of 60 years turns out to be too conservative. It is slow, but
not that slow. Running on a Power Mac 8500/120 with 214 megs of Ram I get
In[5]:= Cases[tester, xx_ + num_Real, Infinity]//Timing
Out[5]= {8424.35, {}}
Richard Gass
Department of Physics
University of Cincinnati
Cincinnati, OH 45221
phone- 513-556-0519
E-Mail gass at physunc.uc.edu