From: Emanuel Berg <embe8573@student.uu.se>
To: help-gnu-emacs@gnu.org
Subject: Re: why are there [v e c t o r s] in Lisp?
Date: Sat, 17 Oct 2015 01:47:23 +0200 [thread overview]
Message-ID: <877fmmpe9g.fsf@debian.uxu> (raw)
In-Reply-To: barmar-0F46BA.09321516102015@88-209-239-213.giganet.hu
Barry Margolin <barmar@alum.mit.edu> writes:
> Lists and vectors have different performance
> characteristics. With lists, it's easy to insert and
> delete elements anywhere in the sequence, you just
> add another cons in the cdr chain, but accessing the
> nth element is O(n). With vectors, inserting and
> deleting is expensive, because you have to shift all
> the following elements over to make room (and
> appending may require moving the whole thing,
> because you didn't allocate enough room in the
> original location), but accessing the nth element
> can be done in constant time.
>
> So lists are good for flexible data structures that
> you typically access linearly, while vectors are
> good for random-access data. Also, because vectors
> are stored in contiguous memory, they generally
> exhibit better locality -- this was more important
> in the days when RAM was expensive and limited,
> because paging was more likely when you had a large
> working set.
Right, the international press is happy with
this answer.
--
underground experts united
http://user.it.uu.se/~embe8573
next prev parent reply other threads:[~2015-10-16 23:47 UTC|newest]
Thread overview: 56+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <mailman.428.1444957396.7904.help-gnu-emacs@gnu.org>
2015-10-16 1:51 ` why are there [v e c t o r s] in Lisp? Pascal J. Bourguignon
2015-10-16 2:31 ` Emanuel Berg
2015-10-16 2:29 ` Random832
2015-10-16 2:51 ` Emanuel Berg
2015-10-16 2:56 ` Random832
2015-10-16 23:30 ` Emanuel Berg
[not found] ` <mailman.482.1445037713.7904.help-gnu-emacs@gnu.org>
2015-10-17 1:55 ` Pascal J. Bourguignon
2015-10-17 4:47 ` Emanuel Berg
[not found] ` <mailman.494.1445057637.7904.help-gnu-emacs@gnu.org>
2015-10-17 15:25 ` Pascal J. Bourguignon
2015-10-17 21:12 ` Emanuel Berg
[not found] ` <mailman.519.1445115776.7904.help-gnu-emacs@gnu.org>
2015-10-18 1:08 ` Pascal J. Bourguignon
[not found] ` <mailman.432.1444964227.7904.help-gnu-emacs@gnu.org>
2015-10-16 3:57 ` Pascal J. Bourguignon
2015-10-16 4:17 ` Random832
[not found] ` <mailman.434.1444970033.7904.help-gnu-emacs@gnu.org>
2015-10-16 5:16 ` Pascal J. Bourguignon
[not found] ` <mailman.429.1444962165.7904.help-gnu-emacs@gnu.org>
2015-10-16 3:31 ` Pascal J. Bourguignon
2015-10-16 23:46 ` Emanuel Berg
[not found] ` <mailman.483.1445038647.7904.help-gnu-emacs@gnu.org>
2015-10-17 2:04 ` Pascal J. Bourguignon
2015-10-17 4:40 ` Random832
2015-10-17 5:00 ` Emanuel Berg
2015-10-17 4:40 ` Emanuel Berg
[not found] ` <mailman.491.1445056308.7904.help-gnu-emacs@gnu.org>
2015-10-17 5:53 ` Barry Margolin
2015-10-17 15:16 ` Pascal J. Bourguignon
2015-10-17 21:06 ` Emanuel Berg
[not found] ` <mailman.518.1445115463.7904.help-gnu-emacs@gnu.org>
2015-10-18 1:07 ` Pascal J. Bourguignon
2015-10-18 12:32 ` Emanuel Berg
[not found] ` <mailman.551.1445171034.7904.help-gnu-emacs@gnu.org>
2015-10-18 12:55 ` Pascal J. Bourguignon
2015-10-18 14:28 ` Emanuel Berg
2015-10-18 21:17 ` Robert Thorpe
[not found] ` <mailman.557.1445177952.7904.help-gnu-emacs@gnu.org>
2015-10-18 19:48 ` Barry Margolin
2015-10-18 21:25 ` Emanuel Berg
2015-10-18 21:39 ` Random832
2015-10-19 0:46 ` Pascal J. Bourguignon
2015-10-17 5:56 ` Barry Margolin
2015-10-17 15:06 ` Emanuel Berg
2015-10-16 13:32 ` Barry Margolin
2015-10-16 23:47 ` Emanuel Berg [this message]
[not found] <mailman.581.1445203060.7904.help-gnu-emacs@gnu.org>
2015-10-19 0:45 ` Pascal J. Bourguignon
2015-10-16 1:12 Emanuel Berg
2015-10-17 1:11 ` Aurélien Aptel
2015-10-17 4:22 ` Emanuel Berg
2015-10-17 7:58 ` Jude DaShiell
2015-10-19 16:33 ` Nick Dokos
[not found] ` <mailman.490.1445055179.7904.help-gnu-emacs@gnu.org>
2015-10-17 15:09 ` Pascal J. Bourguignon
[not found] ` <mailman.488.1445044303.7904.help-gnu-emacs@gnu.org>
2015-10-17 2:22 ` Pascal J. Bourguignon
2015-10-17 4:56 ` Emanuel Berg
2015-10-17 5:49 ` Barry Margolin
2015-10-17 15:04 ` Emanuel Berg
[not found] ` <mailman.506.1445093727.7904.help-gnu-emacs@gnu.org>
2015-10-17 15:20 ` Pascal J. Bourguignon
2015-10-17 15:38 ` Emanuel Berg
[not found] ` <mailman.511.1445095810.7904.help-gnu-emacs@gnu.org>
2015-10-17 16:01 ` Javier
2015-10-17 16:03 ` Javier
2015-10-17 16:34 ` Pascal J. Bourguignon
2015-10-17 21:18 ` Emanuel Berg
2015-10-17 16:15 ` Pascal J. Bourguignon
2015-10-17 21:37 ` Emanuel Berg
2015-10-17 15:18 ` Pascal J. Bourguignon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=877fmmpe9g.fsf@debian.uxu \
--to=embe8573@student.uu.se \
--cc=help-gnu-emacs@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).