8
$\begingroup$

In Wagner's book "Power Programming with Mathematica" page 303. Wagner metioned do not "modify large list in place"

He take two example

s = Range[1000];
Do[s[[i]] = (s[[i]] + s[[i + 1]])/2, {i, 1, Length[s] - 1}]; // RepeatedTiming
(*{0.007,Null}*)

s = Range[1000];
(t = Table[0,{1000}];
   Do[t[[i]] = (s[[i]] + s[[i + 1]])/2, {i, 1, Length[s] - 1}]); // RepeatedTiming
(*{0.007,Null}*)

You can see on my computer with M11, the timing is the same!! However, on his book, the timing is 3.01667s and 0.6333s respectively. His explanation is as follows

In Section 7.3.3 we explained that this disparity is due to the way that the kernel evaluates an expression like s[[i]] if s has been modified since its last access. The evaluation process requires a scan of each element of s to check for upvalues, which takes time proportional to the length of a (review Section 7.3.3 for a more irrdepth explanation). Thus, in the first algorithm s undergoes a scan on each loop iteration. which makes the running time quadratic in the length of the list, rather than linear.

and on page 211, He has further explain on upvalue check

During the evaluation of s the kernel has to attempt to evaluate each element of s and check to see if there are upvalues defined for List [__, element , _]

Since the book is written for MMA 3.0. What has changed since 3.0? Is Wagner's explanation still count today? Why MMA doesn't have to check upvalue now? Is it because the general main evaluation process changed? Or because the storage of list is changed, so list contains infomation of upvalue change? What is the Mathematica evaluatioin process now when it sees such a code?

As far as I know, it seems that only this rule of thumb from Wagner's book is not right. Are there any other significant flaws in Wagner's explanation of principle of MMA that is not right for latest version of MMA?

Improve this question
$\endgroup$
8
  • $\begingroup$ Mathematica V3 did not have packed arrays. I don't know if this is a partial explanation. However, anything that was outrageously slow ~20 years ago has no doubt been an obvious target for optimisation. $\endgroup$
    – mikado
    Sep 3, 2016 at 12:22
  • $\begingroup$ @mikado I know packed array is introduced in v4. However, both example is unpacked, since (s[[i]] + s[[i + 1]])/2 is fraction expression $\endgroup$
    – matheorem
    Sep 3, 2016 at 12:26
  • 1
    $\begingroup$ @mikado we all value Wagner's book, because we assume the principle of MMA is changed little since v3. Wagner's explanation is about evaluation process, so I think it is an important thing whether it changed since v3, especially for lists which is main structure in MMA $\endgroup$
    – matheorem
    Sep 3, 2016 at 12:31
  • 2
    $\begingroup$ I'm not sure what the question is. Do you want to know if Mathematica changed in such a way that unneeded reevaluation of expressions is less frequent? If so, the answer is yes. $\endgroup$
    – Daniel Lichtblau
    Sep 3, 2016 at 22:52
  • 3
    $\begingroup$ Like I said, there have been changes. Something about them is diescribed in StackOverflow, where among other things the UpValues business gets mention. Also see this MSE thread for some discussion of what takes place in evaluation, as related to speed and determination of need for reevaluation. $\endgroup$
    – Daniel Lichtblau
    Sep 4, 2016 at 14:52

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.