Re: Algorithm Analysis Course: Should I use Mathematica for projects?
- To: mathgroup at smc.vnet.net
- Subject: [mg127284] Re: Algorithm Analysis Course: Should I use Mathematica for projects?
- From: Andrzej Kozlowski <akozlowski at gmail.com>
- Date: Sat, 14 Jul 2012 01:28:08 -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> <50006641.8080505@cs.berkeley.edu>
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
- References:
- Re: Algorithm Analysis Course: Should I use Mathematica for projects?
- From: Richard Fateman <fateman@cs.berkeley.edu>
- Re: Algorithm Analysis Course: Should I use Mathematica for projects?