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 KAA29074; Fri, 18 Oct 2002 10:35:33 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA28802 for caml-list@pauillac.inria.fr; Fri, 18 Oct 2002 10:35:32 +0200 (MET DST) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id FAA20343 for ; Fri, 18 Oct 2002 05:09:54 +0200 (MET DST) Received: from mail.interaktif.net.tr ([62.248.102.120]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g9I39pD27351 for ; Fri, 18 Oct 2002 05:09:53 +0200 (MET DST) Received: from abn166-176.ank-avrupa-ports.kablonet.net.tr (unknown [195.174.166.176]) by mail.interaktif.net.tr (Postfix) with ESMTP id 8F2871E681; Fri, 18 Oct 2002 06:07:02 +0300 (EEST) From: Eray Ozkural Organization: Bilkent University CS Dept. To: Oleg , caml-list@inria.fr Subject: Re: [Caml-list] Array.resize ? Date: Fri, 18 Oct 2002 06:05:57 +0300 User-Agent: KMail/1.4.5 References: <200207112228.SAA02692@dewberry.cc.columbia.edu> In-Reply-To: <200207112228.SAA02692@dewberry.cc.columbia.edu> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 8bit Content-Disposition: inline Message-Id: <200210180605.57751.erayo@cs.bilkent.edu.tr> Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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. A vector is not a special type in C++. You can implement one in ocaml just as well or better. Cheers, -- Eray Ozkural Comp. Sci. Dept., Bilkent University, Ankara www: http://www.cs.bilkent.edu.tr/~erayo GPG public key fingerprint: 360C 852F 88B0 A745 F31B EA0F 7C07 AE16 874D 539C ------------------- 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