Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #10891 > unrolled thread

Algorithm Analysis Course: Should I use Mathematica for projects?

Started byBrentt <brenttnewman@gmail.com>
First post2012-07-11 22:25 +0000
Last post2012-07-23 23:57 +0000
Articles 15 — 8 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  Algorithm Analysis Course: Should I use Mathematica for projects? Brentt <brenttnewman@gmail.com> - 2012-07-11 22:25 +0000
    Re: Algorithm Analysis Course: Should I use Mathematica for projects? Richard Fateman <fateman@cs.berkeley.edu> - 2012-07-12 09:00 +0000
    Re: Algorithm Analysis Course: Should I use Mathematica for projects? Helen Read <readhpr@gmail.com> - 2012-07-13 06:54 +0000
    Re: Algorithm Analysis Course: Should I use Mathematica for projects? Joseph Gwinn <joegwinn@comcast.net> - 2012-07-13 06:55 +0000
    Re: Algorithm Analysis Course: Should I use Mathematica for projects? Andrzej Kozlowski <akozlowski@gmail.com> - 2012-07-13 06:53 +0000
      Re: Algorithm Analysis Course: Should I use Mathematica for projects? Andrzej Kozlowski <akozlowski@gmail.com> - 2012-07-14 05:29 +0000
      Re: Algorithm Analysis Course: Should I use Mathematica for projects? Richard Fateman <fateman@cs.berkeley.edu> - 2012-07-14 05:28 +0000
      Re: Algorithm Analysis Course: Should I use Mathematica for projects? Richard Fateman <fateman@eecs.berkeley.edu> - 2012-07-14 05:29 +0000
      Re: Algorithm Analysis Course: Should I use Mathematica for projects? Andrzej Kozlowski <akozlowski@gmail.com> - 2012-07-15 08:31 +0000
      Re: Algorithm Analysis Course: Should I use Mathematica for projects? Andrzej Kozlowski <akozlowski@gmail.com> - 2012-07-15 08:33 +0000
      Re: Algorithm Analysis Course: Should I use Mathematica for projects? Andrzej Kozlowski <akozlowski@gmail.com> - 2012-07-15 08:27 +0000
      Re: Algorithm Analysis Course: Should I use Mathematica for projects? Andrzej Kozlowski <akozlowski@gmail.com> - 2012-07-15 08:25 +0000
      Re: Algorithm Analysis Course: Should I use Mathematica for projects? Andrzej Kozlowski <akozlowski@gmail.com> - 2012-07-15 08:32 +0000
    Re: Algorithm Analysis Course: Should I use Mathematica for projects? David Bailey <dave@removedbailey.co.uk> - 2012-07-14 05:30 +0000
    Re: Algorithm Analysis Course: Should I use Mathematica for projects? roby <roby.nowak@gmail.com> - 2012-07-23 23:57 +0000

#10891 — Algorithm Analysis Course: Should I use Mathematica for projects?

FromBrentt <brenttnewman@gmail.com>
Date2012-07-11 22:25 +0000
SubjectAlgorithm Analysis Course: Should I use Mathematica for projects?
Message-ID<jtkuhh$2a$1@smc.vnet.net>
Hi,

I'm an undergrad math major, and taking a cross disciplinary Algorithm
Analysis course in the fall. I talked to the professor and he said we can
use whichever language we like and Mathematica would be fine if it had a
way to evaluate run-time.

Two questions:

I think the required capabilities are those found in the documentation
under "Time Measurement & Optimization". Would this be correct? And would
those functions be adequate for an algorithm analysis course?


I know this list would be a little biased but: should I use Mathematica?

Cons:  I absolutely adore Mathematica and never find myself wanting to
program in anything else (I've toyed with Python and other languages, but
Mathematica inspires me to play with programming like other languages have
not), and thought committing to Python for the class might expand my
programming skills. Also I'm guessing the course will focus on procedural
algorithms which might not be a good fit for Mathematica's functional
paradigm. I know Mathematica can be shoehorned in to any paradigm, but
maybe it'd be better to use a more procedural language.

Pros: I will learn Mathematica with more depth, and there are good reasons
to get really good at one thing as opposed to OK at many things. Plus what
I learn in Mathematica may just as well translate to other languages anyway
so it may not be a big deal which I choose.

Input anyone?

[toc] | [next] | [standalone]


#10896

FromRichard Fateman <fateman@cs.berkeley.edu>
Date2012-07-12 09:00 +0000
Message-ID<jtm3mi$ge5$1@smc.vnet.net>
In reply to#10891
On 7/11/2012 3:25 PM, Brentt wrote:
> Hi,
>
> I'm an undergrad math major, and taking a cross disciplinary Algorithm
> Analysis course in the fall. I talked to the professor and he said we can
> use whichever language we like and Mathematica would be fine if it had a
> way to evaluate run-time.
>
> Two questions:
>
> I think the required capabilities are those found in the documentation
> under "Time Measurement & Optimization". Would this be correct? And would
> those functions be adequate for an algorithm analysis course?

My guess is that those measurement tools would be fine.  The problem is 
that Mathematica is unsuitable as a programming language.
>
>
> I know this list would be a little biased but: should I use Mathematica?

You could write the programs, but the timing would look nonsensical 
without substantial explanation.
>
> Cons:  I absolutely adore Mathematica and never find myself wanting to
> program in anything else (I've toyed with Python and other languages, but
> Mathematica inspires me to play with programming like other languages have
> not), and thought committing to Python for the class might expand my
> programming skills.

You should use a conventional programming language which supports 
conventional data structures.  This could be python, or C or Java or Lisp.

  Also I'm guessing the course will focus on procedural
> algorithms which might not be a good fit for Mathematica's functional
> paradigm.
Probably not an issue.

I know Mathematica can be shoehorned in to any paradigm, but
> maybe it'd be better to use a more procedural language.

It would be better to use a programming language in which Lists are 
lists, not arrays and accessing elements in an array of length N is an 
O(1) operation, not O(N).

Your times and the expectations of the class/instructor/exams/homeworks
would work together if you used a language which did not disrespect the
fundamentals of data structures.

>
> Pros: I will learn Mathematica with more depth, and there are good reasons
> to get really good at one thing as opposed to OK at many things.

It is unlikely that having an in-depth understanding of Mathematica will 
have a strongly positive impact on what you do after graduation.
Compared (say) with experience in a more commonly used programming language.

Plus what
> I learn in Mathematica may just as well translate to other languages anyway
> so it may not be a big deal which I choose.

To some extent Mathematica makes a hash of "paradigms" from other 
programming languages, with a dose of mathematical procedures.  Learning 
functional programming from Mathematica seems to me to
be an unappealing prospect.

Ask your instructor for a recommendation of a programming language, and
learn that one.

Good luck.

>
> Input anyone?
>


[toc] | [prev] | [next] | [standalone]


#10906

FromHelen Read <readhpr@gmail.com>
Date2012-07-13 06:54 +0000
Message-ID<jtognr$ql1$1@smc.vnet.net>
In reply to#10891
Another poster, I think it was Nasser, posted a link to a page offering 
good reasons for using Mathematica.

http://research.sabioacademy.com/why-we-use-mathematica


On 7/11/2012 6:25 PM, Brentt wrote:
> Hi,
>
> I'm an undergrad math major, and taking a cross disciplinary Algorithm
> Analysis course in the fall. I talked to the professor and he said we can
> use whichever language we like and Mathematica would be fine if it had a
> way to evaluate run-time.
>
> Two questions:
>
> I think the required capabilities are those found in the documentation
> under "Time Measurement & Optimization". Would this be correct? And would
> those functions be adequate for an algorithm analysis course?
>
>
> I know this list would be a little biased but: should I use Mathematica?
>
> Cons:  I absolutely adore Mathematica and never find myself wanting to
> program in anything else (I've toyed with Python and other languages, but
> Mathematica inspires me to play with programming like other languages have
> not), and thought committing to Python for the class might expand my
> programming skills. Also I'm guessing the course will focus on procedural
> algorithms which might not be a good fit for Mathematica's functional
> paradigm. I know Mathematica can be shoehorned in to any paradigm, but
> maybe it'd be better to use a more procedural language.
>
> Pros: I will learn Mathematica with more depth, and there are good reasons
> to get really good at one thing as opposed to OK at many things. Plus what
> I learn in Mathematica may just as well translate to other languages anyway
> so it may not be a big deal which I choose.
>
> Input anyone?
>



[toc] | [prev] | [next] | [standalone]


#10907

FromJoseph Gwinn <joegwinn@comcast.net>
Date2012-07-13 06:55 +0000
Message-ID<jtogoq$qle$1@smc.vnet.net>
In reply to#10891
In article <jtkuhh$2a$1@smc.vnet.net>, Brentt <brenttnewman@gmail.com> 
wrote:

> Hi,
> 
> I'm an undergrad math major, and taking a cross disciplinary Algorithm
> Analysis course in the fall. I talked to the professor and he said we can
> use whichever language we like and Mathematica would be fine if it had a
> way to evaluate run-time.
> 
> Two questions:
> 
> I think the required capabilities are those found in the documentation
> under "Time Measurement & Optimization". Would this be correct? And would
> those functions be adequate for an algorithm analysis course?
> 
> 
> I know this list would be a little biased but: should I use Mathematica?
> 
> Cons:  I absolutely adore Mathematica and never find myself wanting to
> program in anything else (I've toyed with Python and other languages, but
> Mathematica inspires me to play with programming like other languages have
> not), and thought committing to Python for the class might expand my
> programming skills. Also I'm guessing the course will focus on procedural
> algorithms which might not be a good fit for Mathematica's functional
> paradigm. I know Mathematica can be shoehorned in to any paradigm, but
> maybe it'd be better to use a more procedural language.
> 
> Pros: I will learn Mathematica with more depth, and there are good reasons
> to get really good at one thing as opposed to OK at many things. Plus what
> I learn in Mathematica may just as well translate to other languages anyway
> so it may not be a big deal which I choose.
> 
> Input anyone?

Before I start, let me say that I use Mathematica for almost everything, 
and have done so since version 1.2.

But an Algorithms course is not something I would do in Mathematica.

Mathematica is far too complex internally to be suitable for this, as 
its hidden complexities (and thus performance scaling laws) will obscure 
performance scaling of the various algorithms being taught.

It is hard to simply implement such common algorithms as a hash table in 
Mathematics, and one will spend much time wrestling with Mathematica, 
versus the algorithm being taught.  And the scaling laws of Mathematica 
itself  will completely obscure the scaling laws of the algorithms being 
programmed.

I would use C (not C++, although one can use a C++ compiler).  It's the 
simplest and cleanest language (more so than Python), and has massive 
support and documentation, and is a good language to have on one's 
resume.

Joe Gwinn

[toc] | [prev] | [next] | [standalone]


#10908

FromAndrzej Kozlowski <akozlowski@gmail.com>
Date2012-07-13 06:53 +0000
Message-ID<jtoglu$qk8$1@smc.vnet.net>
In reply to#10891
On 12 Jul 2012, at 10:58, Richard Fateman wrote:

> It would be better to use a programming language in which Lists are
> lists, not arrays and accessing elements in an array of length N is an
> O(1) operation, not O(N).

I have no idea what was meant by "accessing elements" in the quote above but "retrieving elements"  from  Mathematica's lists ("arrays") is in fact constant time (i.e. O(1)).
In fact, this is the main reason why Mathematica uses this particular data structure.  The price of this is that one cannot efficiently extend Mathematica's lists, but there are well discussed ways of avoiding this problem.

AndrzejKozlowski

[toc] | [prev] | [next] | [standalone]


#10911

FromAndrzej Kozlowski <akozlowski@gmail.com>
Date2012-07-14 05:29 +0000
Message-ID<jtr034$bbc$1@smc.vnet.net>
In reply to#10908
On 13 Jul 2012, at 20:17, Richard Fateman wrote:

> On 7/12/2012 11:53 PM, Andrzej Kozlowski wrote:
>> On 12 Jul 2012, at 10:58, Richard Fateman wrote:
>>
>>> It would be better to use a programming language in which Lists are
>>> lists, not arrays and accessing elements in an array of length N is an
>>> O(1) operation, not O(N).
>>
>> I have no idea what was meant by "accessing elements" in the quote above but "retrieving elements"
>
>> from  Mathematica's lists ("arrays") is in fact constant time (i.e. O(1)).
>
> No, the cost for retrieving an element from a list/array depends on the length of the list.   It does not depend on the index of the element.
>
> It is interesting a person who ordinarily displays evidence of substantial knowledge of Mathematica should be unaware of this situation.  Here is the reason, so far as I can tell.
>
> If you mention a name like  A,  in  A[[i]]=A[[i]]+1, Mathematica re-evaluates all elements in the list/array  A.
>
> So changing an element has a cost that is proportional to the number of
> elements in A.
>
>
> Proof.
>
> M = Table[mm[i], {i, 1, 5}]
> mm[i_]:=Print[i]
>
> M[[2]]++
>
> prints 1 2 3 4 5
>
> Also confounding the situation is that, I think,  something funny happens if the list/array is larger than some threshold
> beyond which Mathematica does not operate the same way.
>
>
>
>> In fact, this is the main reason why Mathematica uses this particular data structure.
>
> In almost any other programming language, that's the way it would operate.
>
> >The price of this is that one cannot efficiently extend Mathematica's lists,
> > but there are well discussed ways of avoiding this problem.
>
> If you want to build lists out of other structures, there are certainly well-known ways of doing this. For example, the language LISP
> makes lists of any length out of fixed-length  (2-element) cells.
>
> RJF

Well, I don't think this proves anything of the kind you believe it does. As you often seem to do you stop your experiments too early so the conclusions you reach prove much less than you claim they do.

It is indeed true (and, in fact, pretty obvious) that when Mathematica evaluates M[[i]] (i.e. Part[M,i]) it must evaluate M, since the attributes of Part are:

Attributes[Part]

{NHoldRest,Protected,ReadProtected}

in other words, they don't include HoldFirst or HoldAll. We can see it simply here:

l = Range[10];

Trace[l[[2]]]

{{l,{1,2,3,4,5,6,7,8,9,10}},{1,2,3,4,5,6,7,8,9,10}[[2]],2}

So l was indeed evaluated, in some sense anyway. But then try some practical timings:

l1 = Table[1, {10^8}]; // Timing

{2.23099,Null}

Took quite a while, right? But:

l1[[10^4]] // Timing

{0.00002,1}

Pretty fast, wouldn't you say? It does not look to me that Mathematica really reevaluated the list, certainly not in the same sense that it did the first time? Now, look at this:

l[[2]] // Timing

{0.000015,1}

Remember, l has 10 elements while l1 has 10^8. I would say, the evidence points to O(1) retrieval, at least for all practical purposes.

Andrzej Kozlowski




[toc] | [prev] | [next] | [standalone]


#10918

FromRichard Fateman <fateman@cs.berkeley.edu>
Date2012-07-14 05:28 +0000
Message-ID<jtr016$ban$1@smc.vnet.net>
In reply to#10908
On 7/12/2012 11:53 PM, Andrzej Kozlowski wrote:
> On 12 Jul 2012, at 10:58, Richard Fateman wrote:
>
>> It would be better to use a programming language in which Lists are
>> lists, not arrays and accessing elements in an array of length N is an
>> O(1) operation, not O(N).
>
> I have no idea what was meant by "accessing elements" in the quote above but "retrieving elements"

> from  Mathematica's lists ("arrays") is in fact constant time (i.e. O(1)).

No, the cost for retrieving an element from a list/array depends on the 
length of the list.   It does not depend on the index of the element.

It is interesting a person who ordinarily displays evidence of 
substantial knowledge of Mathematica should be unaware of this 
situation.  Here is the reason, so far as I can tell.

If you mention a name like  A,  in  A[[i]]=A[[i]]+1, Mathematica 
re-evaluates all elements in the list/array  A.

So changing an element has a cost that is proportional to the number of
elements in A.


Proof.

M = Table[mm[i], {i, 1, 5}]
mm[i_]:=Print[i]

M[[2]]++

prints 1 2 3 4 5

Also confounding the situation is that, I think,  something funny 
happens if the list/array is larger than some threshold
beyond which Mathematica does not operate the same way.



> In fact, this is the main reason why Mathematica uses this particular data structure.

In almost any other programming language, that's the way it would operate.

 >The price of this is that one cannot efficiently extend Mathematica's 
lists,
 > but there are well discussed ways of avoiding this problem.

If you want to build lists out of other structures, there are certainly 
well-known ways of doing this. For example, the language LISP
makes lists of any length out of fixed-length  (2-element) cells.

RJF

[toc] | [prev] | [next] | [standalone]


#10919

FromRichard Fateman <fateman@eecs.berkeley.edu>
Date2012-07-14 05:29 +0000
Message-ID<jtr042$bbo$1@smc.vnet.net>
In reply to#10908
On 7/13/2012 12:47 PM, Andrzej Kozlowski wrote:
> On 13 Jul 2012, at 20:17, Richard Fateman wrote:
>
>> On 7/12/2012 11:53 PM, Andrzej Kozlowski wrote:
>>> On 12 Jul 2012, at 10:58, Richard Fateman wrote:
>>>
>>>> It would be better to use a programming language in which Lists are
>>>> lists, not arrays and accessing elements in an array of length N is an
>>>> O(1) operation, not O(N).
>>> I have no idea what was meant by "accessing elements" in the quote above but "retrieving elements"
>>> from  Mathematica's lists ("arrays") is in fact constant time (i.e. O(1)).
>> No, the cost for retrieving an element from a list/array depends on the length of the list.   It does not depend on the index of the element.
>>
>> It is interesting a person who ordinarily displays evidence of substantial knowledge of Mathematica should be unaware of this situation.  Here is the reason, so far as I can tell.
>>
>> If you mention a name like  A,  in  A[[i]]=A[[i]]+1, Mathematica re-evaluates all elements in the list/array  A.
>>
>> So changing an element has a cost that is proportional to the number of
>> elements in A.
>>
>>
>> Proof.
>>
>> M = Table[mm[i], {i, 1, 5}]
>> mm[i_]:=Print[i]
>>
>> M[[2]]++
>>
>> prints 1 2 3 4 5
>>
>> Also confounding the situation is that, I think,  something funny happens if the list/array is larger than some threshold
>> beyond which Mathematica does not operate the same way.
>>
>>
>>
>>> In fact, this is the main reason why Mathematica uses this particular data structure.
>> In almost any other programming language, that's the way it would operate.
>>
>>> The price of this is that one cannot efficiently extend Mathematica's lists,
>>> but there are well discussed ways of avoiding this problem.
>> If you want to build lists out of other structures, there are certainly well-known ways of doing this. For example, the language LISP
>> makes lists of any length out of fixed-length  (2-element) cells.
>>
>> RJF
> Well, I don't think this proves anything of the kind you believe it does. As you often seem to do you stop your experiments too early so the conclusions you reach prove much less than you claim they do.
>
> It is indeed true (and, in fact, pretty obvious) that when Mathematica evaluates M[[i]] (i.e. Part[M,i]) it must evaluate M, since the attributes of Part are:
>
> Attributes[Part]
>
> {NHoldRest,Protected,ReadProtected}
>
> in other words, they don't include HoldFirst or HoldAll. We can see it simply here:
>
> l = Range[10];
>
> Trace[l[[2]]]
>
> {{l,{1,2,3,4,5,6,7,8,9,10}},{1,2,3,4,5,6,7,8,9,10}[[2]],2}
>
> So l was indeed evaluated, in some sense anyway.
It was completely evaluated, not "in some sense".

>   But then try some practical timings:
>
> l1 = Table[1, {10^8}]; // Timing
>
> {2.23099,Null}
>
> Took quite a while, right? But:
>
> l1[[10^4]] // Timing
>
> {0.00002,1}
>
> Pretty fast, wouldn't you say?
What I would say is that

1. 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). This strategy is
described in my review of Mathematica published in J. Symbolic 
Computing, and
somewhere on my web site.

2.  In fact, 20 microsecond is kind of slow for a memory reference.

3. But I am surprised there is such a high resolution timer being used.


To show that this is a special case, let us alter just one of the 10^8 
entries and show that it makes
access to ANOTHER entry 10000X slower.


Try this:
l1[[50]]=mm[50];
mm[i_]:= total++


l1[10^4]]//Timing

takes over 2 seconds.  To be specific, *A single array reference takes 
over 2 seconds!*  5 orders of magnitude slower
than your timing.


> It does not look to me that Mathematica really reevaluated the list, certainly not in the same sense that it did the first time?
I find the Mathematica "Trace" facility difficult to fathom, so I base 
my reasoning on other evidence.

>   Now, look at this:
>
> l[[2]] // Timing
>
> {0.000015,1}
A similar trick with a small array/list  like this doesn't affect the 
cost much, since only 10 elements
need to be re-evaluated.  From my own computer, it reports 0. time.
>
> Remember, l has 10 elements while l1 has 10^8. I would say, the evidence points to O(1) retrieval, at least for all practical purposes.
It seems to me that the evidence is that except for certain special 
circumstances (well, not so
special in, say, Fortran, where arrays can only hold constant 
fixed-length numbers or bit strings),
but special circumstances for Mathematica, the cost of an array 
reference depends
on the size of the array  (as well as the complexity of elements which 
have nothing to do with
the array element being referenced).

While this may seem like a peculiar problem in isolation, it is a 
consequence of Mathematica's
evaluation strategy.  It is a feature, so to speak.  It makes the use of 
Mathematica's runtime
statistics a subject for some kind of advanced data-structures / 
trade-secret class, not
an intro to algorithms for non-computer-science majors.


RJF

[toc] | [prev] | [next] | [standalone]


#10937

FromAndrzej Kozlowski <akozlowski@gmail.com>
Date2012-07-15 08:31 +0000
Message-ID<jttv5s$gvg$1@smc.vnet.net>
In reply to#10908
On 14 Jul 2012, at 20:10, Richard Fateman wrote:

> 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?

No, only on Mathematica ;-)

Actually it is a course on symbolic algebra algorithms such as GrobenerBasis, Cylindrical Algebraic Decomposition, Integrate etc. But Mathematica is the only tool. We also have a yearly Mathematica project contest (with prizes from the Dean of Mathematics and the Dean of Computer Science).

As for the university, it is the largest university in Central Europe and its computer science students just won the silver medal in the World Programming Championships ;-)


http://en.wikipedia.org/wiki/ACM_International_Collegiate_Programming_Contest

though I don't think they used Mathematica ;-)
Actually, the  oldest university in the same country has a much older Mathematica course (again called "Symbolic Algebra" but only Mathematica is used) and they also have a yearly Mathematica contest. We have only just started plagiarising their ideas.

Andrzej Kozlowski

[toc] | [prev] | [next] | [standalone]


#10939

FromAndrzej Kozlowski <akozlowski@gmail.com>
Date2012-07-15 08:33 +0000
Message-ID<jttv8n$gvo$1@smc.vnet.net>
In reply to#10908
On 14 Jul 2012, at 21:12, Richard Fateman wrote:

>
>>  But Mathematica is the only tool.
> I would hope that people taking such a course would also use pencil, paper, and brains.

Well, of course they do. One of the main differences between our computer science students and those in the US is that our students know a great deal more mathematics, and for that brains (and to a much lesser extent pen and paper) are still required. I don't know if this has anything to do with the fact that no US university won this  ICPC title in this century but it might.

>>  We also have a yearly Mathematica project contest (with prizes from the Dean of Mathematics and the Dean of Computer Science).
> That sounds silly.

The idea is to solve or attempt to solve a mathematical problem with the help of Mathmatica. I am not surprised this sounds silly to you but the dean of computer science was one of the judges at the last contest and liked it enough to offer to fund an additional prize.
>> 
>> As for the university, it is the largest university in Central Europe and its computer science students just won the silver medal in the World Programming Championships ;-)
> Is there some reason you are trying to keep the name anonymous? I thought you were in Japan.
>>

Nothing lasts forever. Also (in some sense) I have always lived in more than one country and still do.

AK

[toc] | [prev] | [next] | [standalone]


#10942

FromAndrzej Kozlowski <akozlowski@gmail.com>
Date2012-07-15 08:27 +0000
Message-ID<jttutb$grp$1@smc.vnet.net>
In reply to#10908
On 14 Jul 2012, at 22:44, Richard Fateman wrote:

>> B = Table[i, {i, 0, 1000}];
>> B[[5]] = j; Timing[Do[B[[50]]++, {i, 0, 100000}]]
>>
>> This sort of thing can certainly change the length of a list. A simple example:
>>
>> Clear[B]
>>
>>  j /: {a___, j, b__} := {a, 1, 1, b}
>>
>> B = Table[i, {i, 0, 5}];
>> Length[B]
>> 6
>>
>> B[[5]] = j;
>> Length[B]
>> 7
>>
>> It would seem to me that this alone should force re-evaluation of the list.
> The activity which is being timed is  B[[50]]    or B[[50]]++
> neither of which changes the length of the list/ size of the array.

Yes, but this can also trigger a change in the length if the list contains a symbol with and UpValue. For example:



j /: {a___, j, 3, b__} := {a, 1, 1, 2, b}

B = Table[i, {i, 0, 5}];

B[[2]] = j;

B[[2]] = j;

Do[B[[3]]++, {3}]

B

{0,1,1,2,3,4,5}

The length of the list has changed. As long as the list contains a symbol that might have an UpValue any change of any index can change the length of the list. I still think that makes re-evaluation necessary.

Andrzej

[toc] | [prev] | [next] | [standalone]


#10943

FromAndrzej Kozlowski <akozlowski@gmail.com>
Date2012-07-15 08:25 +0000
Message-ID<jttuqe$gqt$1@smc.vnet.net>
In reply to#10908
Time difference and Daniel's comments have made most of what I would have said obsolete so here is only what remains.


On 14 Jul 2012, at 07:28, Richard Fateman wrote:
>>
>>
>> It is indeed true (and, in fact, pretty obvious) that when Mathematica evaluates M[[i]] (i.e. Part[M,i]) it must evaluate M, since the attributes of Part are:
>>
>> Attributes[Part]
>>
>> {NHoldRest,Protected,ReadProtected}
>>
>> in other words, they don't include HoldFirst or HoldAll. We can see it simply here:
>>
>> l = Range[10];
>>
>> Trace[l[[2]]]
>>
>> {{l,{1,2,3,4,5,6,7,8,9,10}},{1,2,3,4,5,6,7,8,9,10}[[2]],2}
>>
>> So l was indeed evaluated, in some sense anyway.
> It was completely evaluated, not "in some sense".

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).

But just a little earlier you claim that the list is "completely evaluated". How are these two statements compatible?

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 is exactly why I wrote "in some sense" - I was not sure exactly how this high performance is achieved.  Anyway, this seems to me at least more accurate than saying that the list is both "completely evaluated" and "not evaluated at all".

Another thing, all your examples of length dependent retrieval involve changing the list in w way that could alter it's length. 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}

Clear[B]
B = Table[i, {i, 0, 1000}];
B[[5]] = 3; Timing[Do[B[[50]]++, {i, 0, 100000}]]

{0.232278,Null}


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.


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. 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. 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. 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

[toc] | [prev] | [next] | [standalone]


#10945

FromAndrzej Kozlowski <akozlowski@gmail.com>
Date2012-07-15 08:32 +0000
Message-ID<jttv7p$gvl$1@smc.vnet.net>
In reply to#10908
I don't intend to get involved in more pompous and futile rhetorics so beloved by Richard, but so I will restrict myself to matters of substance.
 The stuff about "how it all works" is mere hypothesis - quite interesting in some ways but no more (and actually perhaps less) than similar hypothesis I have heard from my students. It's all rather unimportant.

>> 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. :)

I will address only the first part of the above (the second is just too childish, even with the smiley, to bother with).

You used the construction:


B = Table[i, {i, 0, 1000}];
B[[5]] = j; Timing[Do[B[[50]]++, {i, 0, 100000}]]

This sort of thing can certainly change the length of a list. A simple example:

Clear[B]

 j /: {a___, j, b__} := {a, 1, 1, b}

B = Table[i, {i, 0, 5}];
Length[B]
6

B[[5]] = j;
Length[B]
7

It would seem to me that this alone should force re-evaluation of the =
list.
  
>>
>> 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.

Studying algorithms is not the same as studying the working of =
programming languages and I never said it was. But algorithms have =
various aspects some of which can be studied without any mention of any =
programming language at all (as happens for example with algorithms in =
commutative algebra) and others (such as time and space complexity) =
require the introduction of a specific model of a computer and a =
suitable language - (as was done, for example, in volume 1 of Knuth's =
"The Art of Computer Programming"). Choosing such a model and a language =
is always to some extent arbitrary. One could probably create a computer =
especially designed to run Mathematica (as was once done with LISP at =
MIT) and if this computer became the "accepted standard" "the study of =
algorithms" for such a computer would not be exactly the same as the =
study of algorithms for th standard computers in use today.

Andrzej=

[toc] | [prev] | [next] | [standalone]


#10913

FromDavid Bailey <dave@removedbailey.co.uk>
Date2012-07-14 05:30 +0000
Message-ID<jtr05v$bcd$1@smc.vnet.net>
In reply to#10891
On 11/07/2012 23:25, Brentt wrote:
> Hi,
>
> I'm an undergrad math major, and taking a cross disciplinary Algorithm
> Analysis course in the fall. I talked to the professor and he said we can
> use whichever language we like and Mathematica would be fine if it had a
> way to evaluate run-time.
>
> Two questions:
>
> I think the required capabilities are those found in the documentation
> under "Time Measurement&  Optimization". Would this be correct? And would
> those functions be adequate for an algorithm analysis course?
>
>
> I know this list would be a little biased but: should I use Mathematica?
>
> Cons:  I absolutely adore Mathematica and never find myself wanting to
> program in anything else (I've toyed with Python and other languages, but
> Mathematica inspires me to play with programming like other languages have
> not), and thought committing to Python for the class might expand my
> programming skills. Also I'm guessing the course will focus on procedural
> algorithms which might not be a good fit for Mathematica's functional
> paradigm. I know Mathematica can be shoehorned in to any paradigm, but
> maybe it'd be better to use a more procedural language.
>
> Pros: I will learn Mathematica with more depth, and there are good reasons
> to get really good at one thing as opposed to OK at many things. Plus what
> I learn in Mathematica may just as well translate to other languages anyway
> so it may not be a big deal which I choose.
>
> Input anyone?
>

If you time much Mathematica code, you will become aware of a mass of 
subtleties, that might trip you up if you were primarily interested in 
algorithm performances. Here are a few examples:

1)    If you use Fourier to do a DFT of a list of values, the internal 
algorithm will use a faster algorithm for particular lengths, such as 
powers of 2.

2)    Some results can be cached inside Mathematica so that they don't 
get re-computed if needed again.

3)    Many operations on lists or matrices go at very different speeds 
depending on whether these structures are packed or not.

4)    Code may seem to execute slowly because it isn't doing what you 
think. For example, if you iterate:

Nest[(#^2 + 2)/(#^2 + 3) &, 2, 4]

Discarding the answer because you are only interested in the CPU time, 
you may not notice that it has performed the calculation in exact 
fractional arithmetic - which is much slower than floating point arithmetic.

An interesting approach might be to run the code in C, but use 
Mathematica to provide the overall timing, C compilation, report 
generation, etc.

David Bailey
http://www.dbaileyconsultancy.co.uk

[toc] | [prev] | [next] | [standalone]


#11046

Fromroby <roby.nowak@gmail.com>
Date2012-07-23 23:57 +0000
Message-ID<jukocr$o0r$1@smc.vnet.net>
In reply to#10891
Hi Brentt,

are you sure that you need real timing in e.g. seconds ?

Would it not be sufficent to implement instruction counters to 
count the total number of e.g. additions, multiplicatiion, other arithmetic operations, function calls etc. involved in the algorithms under test.

Regards Robert

[toc] | [prev] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web