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

**References**:**Re: Algorithm Analysis Course: Should I use Mathematica for projects?***From:*Richard Fateman <fateman@cs.berkeley.edu>