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