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 DAA08230; Sat, 19 Oct 2002 03:50:59 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f 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 DAA08102 for ; Sat, 19 Oct 2002 03:50:57 +0200 (MET DST) Received: from apakabar.cc.columbia.edu (apakabar.cc.columbia.edu [128.59.59.159]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g9J1ou529347 for ; Sat, 19 Oct 2002 03:50:56 +0200 (MET DST) Received: from there (tw304h3.cpmc.columbia.edu [156.111.84.180]) by apakabar.cc.columbia.edu (8.9.3/8.9.3) with SMTP id VAA15530; Fri, 18 Oct 2002 21:50:49 -0400 (EDT) Message-Id: <200210190150.VAA15530@apakabar.cc.columbia.edu> Content-Type: text/plain; charset="iso-8859-1" From: Oleg To: Eray Ozkural , caml-list@inria.fr Subject: Re: [Caml-list] Array.resize ? Date: Fri, 18 Oct 2002 21:51:28 -0400 X-Mailer: KMail [version 1.3.2] References: <200207112228.SAA02692@dewberry.cc.columbia.edu> <200210180605.57751.erayo@cs.bilkent.edu.tr> In-Reply-To: <200210180605.57751.erayo@cs.bilkent.edu.tr> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Thursday 17 October 2002 11:05 pm, Eray Ozkural wrote: > On Friday 12 July 2002 01:30, Oleg wrote: > > Hi > > > > Is there an efficient way in O'Caml to append an element to an array ref? > > > > let append_elt r x = r := Array.append !r [| x |];; > > > > copies the contents of the whole array in its body, while e.g. C++ vector > > push_back in most cases won't (memory is reserved in chunks > > automatically, or it can be reserved manually) > > Hi Oleg, > > Here is some Data Structures 101 for you. > > A vector is not an array. It is more like one of the "extensible array" > types that are around since 1960's. The implementation of vector types use > what we call an open table with amortized time for n consequent inserts > being O(n) making a single insert O(1). (See the MIT Algorithms textbook > for details) This also answers why memory alloc doesn't cost much when > using vectors. Since the array is expanded or contracted by a factor of 2 > in size you need only a logarithmic number of memory allocation calls. This is exactly what I meant when I wrote "memory is reserved in chunks automatically ... " above. (BTW might I suggest you save the condescending tone for somewhere else?) > A vector is not a special type in C++. You can implement one in ocaml just > as well or better. Which is why I asked for it. Oleg P.S. You keep replying to messages that are over THREE months old and probably long since lost their relevance: e.g. my question has been answered (see RES by Markus Mottl) ------------------- 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