From: rog@vitanuova.com
To: 9fans@cse.psu.edu
Subject: Re: [9fans] Rstat needs three size fields?
Date: Wed, 9 Jul 2003 15:58:30 +0100 [thread overview]
Message-ID: <56156a60fc995930065001592e6f105a@vitanuova.com> (raw)
In-Reply-To: <008601c34591$54e87200$d2944251@insultant.net>
> > yes, tis true, but only temporarily
>
> tis true it's a god-awful algorithm.
for the kind of thing i think matt was thinking of,
something like (limbo for brevity, i'm afraid):
items: list of Item;
while((item := getnextitem()) != nil)
items = item :: items;
a := array[len items] of Item;
for(i := 0; items != nil; items = tl items)
a[i++] = hd items;
the amount of data copying is only O(n); if i'd been
expanding an array, it would have been O(n log n).
that's doesn't seem bad *algorithmicly* although the heap overheads
might be bad in practise.
i confess to having used this technique before. i'm probably missing
something crucial.
why is it a "god-awful algorithm"?
next prev parent reply other threads:[~2003-07-09 14:58 UTC|newest]
Thread overview: 36+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-06-30 18:04 Sam
2003-06-30 19:08 ` ron minnich
2003-06-30 19:15 ` boyd, rounin
2003-07-04 3:18 ` Russ Cox
2003-07-04 15:04 ` Sam
2003-07-04 17:13 ` rob pike, esq.
2003-07-07 8:33 ` Douglas A. Gwyn
2003-07-07 9:03 ` Geoff Collyer
2003-07-07 15:10 ` Douglas A. Gwyn
2003-07-08 0:49 ` ron minnich
2003-07-07 15:50 ` rob pike, esq.
2003-07-07 20:38 ` boyd, rounin
2003-07-07 21:18 ` rog
2003-07-07 21:28 ` boyd, rounin
2003-07-07 23:23 ` [9fans] simple, sufficient rog
2003-07-07 20:54 ` [9fans] Rstat needs three size fields? Geoff Collyer
2003-07-09 2:07 ` William Josephson
2003-07-07 15:48 ` rob pike, esq.
2003-07-07 15:58 ` Jack Johnson
2003-07-08 8:32 ` Douglas A. Gwyn
2003-07-08 10:30 ` boyd, rounin
2003-07-08 11:09 ` matt
2003-07-08 11:36 ` Dan Cross
2003-07-08 12:12 ` boyd, rounin
2003-07-08 14:14 ` ron minnich
2003-07-08 17:42 ` chris
2003-07-08 20:19 ` matt
2003-07-08 20:41 ` boyd, rounin
2003-07-09 14:58 ` rog [this message]
2003-07-09 19:42 ` boyd, rounin
2003-07-10 12:30 ` rog
2003-07-08 22:09 ` ron minnich
2003-07-08 22:19 ` Dan Cross
2003-07-09 1:27 ` ron minnich
2003-07-01 21:46 boyd, rounin
2003-07-02 0:24 boyd, rounin
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
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=56156a60fc995930065001592e6f105a@vitanuova.com \
--to=rog@vitanuova.com \
--cc=9fans@cse.psu.edu \
/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 NNTP newsgroup(s).