Re: List concatenation - two more methods, one truly fast
- To: mathgroup at smc.vnet.net
- Subject: [mg87637] Re: List concatenation - two more methods, one truly fast
- From: Szabolcs Horvát <szhorvat at gmail.com>
- Date: Tue, 15 Apr 2008 05:46:37 -0400 (EDT)
- Organization: University of Bergen
- References: <ftv8ro$7o1$1@smc.vnet.net>
carlos at colorado.edu wrote:
>
> Observation: timing of the first 4 methods is roughly O(n^2).
> That would suggest that Mathematica does not implement a true
> list processor in the kernel, since building a list should be O(n).
Yes, unlike in most other languages that support a functional
programming paradigm, expressions in Mathematica are represented as
simple arrays in memory (and not linked lists). This means that
indexing is very fast, but concatenation is slow.
A linked list can be created by nesting expressions:
{1, {2, {3, {4, {5, {}}}}}}