MathGroup Archive 2012

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Algorithm Analysis Course: Should I use Mathematica for projects?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg127282] Re: Algorithm Analysis Course: Should I use Mathematica for projects?
  • From: Richard Fateman <fateman at cs.berkeley.edu>
  • Date: Sat, 14 Jul 2012 01:27:28 -0400 (EDT)
  • Delivered-to: l-mathgroup@mail-archive0.wolfram.com
  • Delivered-to: mathgroup-newout@smc.vnet.net
  • Delivered-to: mathgroup-newsend@smc.vnet.net
  • References: <jtkuhh$2a$1@smc.vnet.net> <20120712085845.B341E6859@smc.vnet.net> <jtoglu$qk8$1@smc.vnet.net>

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



  • Prev by Date: Re: SendMail with multiples receives
  • Next by Date: Re: Algorithm Analysis Course: Should I use Mathematica for projects?
  • Previous by thread: Re: Algorithm Analysis Course: Should I use Mathematica for projects?
  • Next by thread: Re: Algorithm Analysis Course: Should I use Mathematica for projects?