From: "David Powers" <david@grayskies.net>
To: jhsu1@email.sjsu.edu
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Keeping a sorted list vs sorting at the end?
Date: Sun, 20 Aug 2006 12:09:53 -0400 [thread overview]
Message-ID: <c65d14df0608200909i76e7ef6ey6b1260ecbf71a769@mail.gmail.com> (raw)
In-Reply-To: <44E7DD8E.1090707@email.sjsu.edu>
[-- Attachment #1: Type: text/plain, Size: 2067 bytes --]
Rough analysis:
If the problem is general, keeping a list sorted is the equivalent of
inserting the members into a priority queue, which is O(n lg n) (for a
binary heap) going in and O(n) walking the tree if you have access to the
internal tree structure (vs calling a get-min function that rebalances the
tree over and over). Non-general data (known bounds, etc) can be inseted
into a sorted data structure in less time.
Creating a list and then sorting it is O(n) for the list creation, then a
theoretical O(n lg n) for the sort (although possibly less (expected case)
in practice depending on the data and algorithm used), after which the items
can be read in O(n). The problem with that is that, unless the data size is
known, the list must be constructed as a list and not an Array, which means
that the sort itself can be very slow (or adds another O(n) conversion step
from List to Array).
Final tally seems to very slightly favor the priority queue if it gives you
enough access to walk the sorted tree and you can create the tree from a
stream source of some sort. If you already have the data in an Array, then
an in-place sort is likely to win.
-David
On 8/19/06, jean-david hsu <jhsu1@email.sjsu.edu> wrote:
>
> Just wondering on the average if it is more efficient to take time to
> keep a list sorted as we insert or simply sort the list at the end?
>
> JD Hsu
>
>
> p5.vert.ukl.yahoo.com uncompressed Sun Aug 20 03:27:01 GMT 2006
>
>
>
> ___________________________________________________________________________
> D�couvrez un nouveau moyen de poser toutes vos questions quelque soit le
> sujet !
> Yahoo! Questions/R�ponses pour partager vos connaissances, vos opinions et
> vos exp�riences.
> http://fr.answers.yahoo.com
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
[-- Attachment #2: Type: text/html, Size: 2711 bytes --]
prev parent reply other threads:[~2006-08-20 16:09 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2006-08-20 3:57 jean-david hsu
2006-08-20 9:45 ` [Caml-list] " Oliver Bandel
2006-08-20 16:09 ` David Powers [this message]
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=c65d14df0608200909i76e7ef6ey6b1260ecbf71a769@mail.gmail.com \
--to=david@grayskies.net \
--cc=caml-list@inria.fr \
--cc=jhsu1@email.sjsu.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).