Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #10918
| From | Richard Fateman <fateman@cs.berkeley.edu> |
|---|---|
| Newsgroups | comp.soft-sys.math.mathematica |
| Subject | Re: Algorithm Analysis Course: Should I use Mathematica for projects? |
| Date | 2012-07-14 05:28 +0000 |
| Message-ID | <jtr016$ban$1@smc.vnet.net> (permalink) |
| References | <jtkuhh$2a$1@smc.vnet.net> <20120712085845.B341E6859@smc.vnet.net> <jtoglu$qk8$1@smc.vnet.net> |
| Organization | Time-Warner Telecom |
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
Back to comp.soft-sys.math.mathematica | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web