Re: Algorithm Analysis Course: Should I use Mathematica for projects?
- To: mathgroup at smc.vnet.net
- Subject: [mg127309] Re: Algorithm Analysis Course: Should I use Mathematica for projects?
- From: Richard Fateman <fateman at eecs.berkeley.edu>
- Date: Sun, 15 Jul 2012 04:28:47 -0400 (EDT)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- Delivered-to: mathgroup-newout@smc.vnet.net
- Delivered-to: mathgroup-newsend@smc.vnet.net
On 7/14/2012 3:37 AM, Andrzej Kozlowski wrote:
<snip>
> (rjf said....)
>> It was completely evaluated, not "in some sense".
Mathematica has a heuristic, something like this, in its evaluation
program...
Every expression depends on some set of objects. Maybe an empty set, as
for example, the integer 4.
Maybe the set {x,y, f} as the expression V= f[x,y].
Every expression has a time stamp. If V has been updated more recently
than any of the objects that it
depends on, then the expression probably does not need to be examined in
detail. Actually, the
set is abbreviated to something like the set of pages on which objects
reside.
> Well, it seems to me that I am the one who was careful and you are contradicting yourself. Note that later in the same post you say:
>
>> this is evidence that the Mathematica system has determined that the
>> value of l1
>> depends on nothing that has changed, e.g. not the definition of any
>> functions or the values of any
>> variables) and therefore it need not be evaluated (again).
Evaluation happens. Just not re-evaluation "again" of all components.
> But just a little earlier you claim that the list is "completely evaluated". How are these two statements compatible?
I would hope that you understand the evaluation process better now.
> I pointed out that Mathematica's "official" semantics seems to imply that when you evaluate Part[list,n] list will be evaluated. Trace seems to confirm this. However, evaluating Part of a very long list shows no difference compared with evaluating Part of a very short list, suggesting constant time retrieval.
This has to do with the heuristics of the evaluation process.
> This is exactly why I wrote "in some sense" - I was not sure exactly how this high performance is achieved.
Now you know how I think it is done.
> Anyway, this seems to me at least more accurate than saying that the list is both "completely evaluated" and "not evaluated at all".
Now you know how I think it is done.
>
> Another thing, all your examples of length dependent retrieval involve changing the list in w way that could alter it's length.
This is false. I set the several arrays in fixed size and then changed
the contents, not the length.
Your statement is also ungrammatical. ... " it's" is a contraction
for "it is" ... not a possessive. :)
> In such cases Mathematica obviously has to re-evaluate the list (in the ordinary sense). In particular consider this:
>
> Clear[B]
> B = Table[i, {i, 0, 1000}];
> B[[5]] = j; Timing[Do[B[[50]]++, {i, 0, 100000}]]
>
> Out[39]= {0.911279,Null}
Your computer is apparently faster than mine. I see 2.219 seconds.
now try B[[5]]=4, eliminating the dependency on j. Evaluation of B
still happens
but the time it takes is negligible since its dependency set is empty,
although the
timestamp for B has changed.
The time is now 0.297 for me.
Now if we just access B[[50]] without changing it, the timestamp will
not change...
Timing[Do[B[[50]], {i, 0, 100000}]]
The time is now 0.094 for me.
Interestingly, we can even do this now : B[[5]=j
and
Timing[Do[B[[50]], {i, 0, 100000}]]
is still 0.094.
That is as long as j's time stamp is old, the evaluation heuristic works.
Let's do something more elaborate.
total=0;
B[[5]]=ff[];
ff[]:=total++;
Timing[Do[B[[50]], {i, 0, 100000}]]
Now most programming languages would have semantics such that
asking for the value of B[[50]] once, twice, or 100000 times would not
call ff[]. But Mathematica calls ff 100,001 times.
The time on my machine is 3.015 seconds, instead of 0.094, about 32X
slower.
>
> Clear[B]
> B = Table[i, {i, 0, 1000}];
> B[[5]] = 3; Timing[Do[B[[50]]++, {i, 0, 100000}]]
>
> {0.232278,Null}
Actually, changing B[[50]] resets B's time stamp matters too.
Here's a little test to show that even with no "j" in there, the time to
access an item in an array
varies with the size of the array.
Table[(Clear[B];
B = Table[i, {i, 0, 10^k}];
Timing[ Do[B[[5]]++, {i, 0, 100000}]])[[1]], {k, 1, 8}]
I get
{0.312, 0.297, 0.453, 0.438, 0.469, 0.453, 0.469, 0.781}
>
>
> Of course using a symbol here was crucial in creating this effect. But this proves nothing in relation to "ordinary programming languages" since most of them would no allow you to do this sort of thing at all.
This is really not true. The issue here is that Mathematica has a kind
of "fixed-point" evaluation strategy that
tries to evaluate until nothing changes. Other languages with such a
strategy (I can think of only one other,
offhand, also a computer algebra system) would have a similar problem
perhaps. Ordinary programming
languages that allow arrays to store "symbolic" objects like pointers to
strings or expressions would not
have this timing problem unless they also had this evaluation strategy.
>
>
> Finally, I would like to mention that I have taken no position at all on the question in the subject of this thread. Clearly using a tool which was designed for a purpose other than the one you have in mind is rarely the optimal approach unless there are some benefits that compensate for the almost inevitable deficiencies. Mathematica was not designed primarily as an all purpose programming language so it is not the best tool for the study of the workings of such languages.
That was not the issue. Studying algorithms is not the same as studying
the workings of programming languages.
Mathematica would not be my first choice for either.
> In particular, it uses various techniques, some of which are not fully documented to speed up certain frequently used computations, sometimes at the expense of others that are less common (for most Mathematica users). On the other hand compared with standard programming languages it has many "compensating features" that have already been mentioned a number of times.
> The balance will depend on such things as the intended audience for the course, the knowledge of the instructor etc.
>
> Perhaps on a somewhat related note, at the university where I am now working, computer science is in the same department as mathematics. Our course on Mathematica is taken by both mathematics and computer science students.
You have a course on Mathematica? Do you also have a course on Python?
On C? On Excel? on PHP?
what kind of college is that?
> The latter already know many "ordinary" programming languages but most of them seem to show a lot of interest in the inner workings of Mathematica.
"interest" does not mean "approval".
> So while Mathematica may not be always the right tool for teaching computer science it is certainly something of interest to many computer scientists.
>
> Andrzej Kozlowski
RJF