From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.3 required=5.0 tests=RCVD_IN_BL_SPAMCOP_NET autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 9737BBC89 for ; Sun, 20 Aug 2006 11:59:17 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.6/8.13.6) with ESMTP id k7K9xHqf000759 for ; Sun, 20 Aug 2006 11:59:17 +0200 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 LAA25780 for ; Sun, 20 Aug 2006 11:45:19 +0200 (MET DST) Received: from einhorn.in-berlin.de (einhorn.in-berlin.de [192.109.42.8]) by nez-perce.inria.fr (8.13.6/8.13.6) with ESMTP id k7K9jFvn032461 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL) for ; Sun, 20 Aug 2006 11:45:19 +0200 X-Envelope-From: oliver@first.in-berlin.de X-Envelope-To: Received: from first.in-berlin.de (e178056156.adsl.alicedsl.de [85.178.56.156]) (authenticated bits=0) by einhorn.in-berlin.de (8.13.6/8.13.6/Debian-1) with ESMTP id k7K9j6vG024848 for ; Sun, 20 Aug 2006 11:45:07 +0200 Received: by first.in-berlin.de (Postfix, from userid 501) id 2A1F3301369; Sun, 20 Aug 2006 11:45:10 +0200 (CEST) Date: Sun, 20 Aug 2006 11:45:09 +0200 From: Oliver Bandel To: caml-list@inria.fr Subject: Re: [Caml-list] Keeping a sorted list vs sorting at the end? Message-ID: <20060820094509.GA323@first.in-berlin.de> References: <44E7DD8E.1090707@email.sjsu.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <44E7DD8E.1090707@email.sjsu.edu> User-Agent: Mutt/1.5.6i X-Scanned-By: MIMEDefang_at_IN-Berlin_e.V. on 192.109.42.8 X-Spam: no; 0.00; bandel:01 in-berlin:01 ocaml:01 2006:98 wrote:01 oliver:01 oliver:01 caml-list:01 suited:02 module:03 module:03 depends:04 hsu:05 aug:06 efficient:06 On Sat, Aug 19, 2006 at 08:57:02PM -0700, jean-david hsu 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? > [...] Sort list at the end. If you want to sort at insertion time, then trees are the better technique. In OCaml there are the Set and the Map module, which may be useful to you. It depends on what you want to do, what kind of datastructure/module is best suited. Ciao, Oliver