From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id LAA00373; Tue, 8 Apr 2003 11:01:13 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: (from xleroy@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id LAA00356 for caml-list@pauillac.inria.fr; Tue, 8 Apr 2003 11:01:12 +0200 (MET DST) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id CAA24151 for ; Tue, 8 Apr 2003 02:59:16 +0200 (MET DST) Received: from alpha.xerox.com (alpha.Xerox.COM [13.1.64.93]) by concorde.inria.fr (8.11.1/8.11.1) with SMTP id h380xFX07103 for ; Tue, 8 Apr 2003 02:59:15 +0200 (MET DST) Received: from katsura.parc.xerox.com ([13.2.18.21]) by alpha.xerox.com with SMTP id <149228(1)>; Mon, 7 Apr 2003 17:59:03 PDT Received: (from ruml@localhost) by katsura.parc.xerox.com (8.12.8/8.12.8/PARC RedHat Custom Submit 1.3) id h380x2wf020763; Mon, 7 Apr 2003 17:59:02 -0700 From: Wheeler Ruml MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <16018.7894.703716.797621@katsura.parc.xerox.com> Date: Mon, 7 Apr 2003 17:59:02 PDT To: John Gerard Malecki CC: caml-list@inria.fr Subject: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures In-Reply-To: <15993.10380.206589.498703@barrow.artisan.com> X-Mailer: VM 7.07 under 21.4 (patch 8) "Honest Recruiter" XEmacs Lucid X-Spam: no; 0.00; wheeler:01 glue:01 gc'ed:01 dummy:01 center:98 int:01 objects:02 allocate:03 data:03 650:95 array:04 swap:05 queue:05 812:93 tricky:06 X-Spam: no; 0.00; wheeler:01 glue:01 gc'ed:01 dummy:01 center:98 int:01 objects:02 allocate:03 data:03 650:95 array:04 swap:05 queue:05 812:93 tricky:06 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > - fast computation of cardinality > > - fast addition of single elements > > - fast addition of lists of elements > > - fast removal of single elements in random order > > - not choking on a large data size I saw Brian's recommendation of a priority queue, but wanted to mention that a resizable array would do here as well. Eg, something like type rarray = { a : 'a array; end : int; } where you allocate more space than you need (or allocate to the correct size at the start, if you know it), doubling the size when necessary, and only look at those elements before the end. Brian's queue may well do this underneath, but there's no reason to suffer O(log n) insertion and removal time if you don't really care about the order. Just add to the end and swap with a random element in constant time. Or remove from a random place and copy in the last element. The only tricky thing is to be careful to fill any "empty" cells in the array with the same dummy value (which needs to be supplied at creation time) so you don't prevent objects from being GC'ed. Wheeler -- Wheeler Ruml, Palo Alto Research Center, Rm 1522, 650-812-4329 voice http://www.parc.com/ruml 650-812-4334 fax ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners