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=0.0 required=5.0 tests=AWL autolearn=disabled version=3.1.3 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 0F74CBBC1 for ; Fri, 7 Mar 2008 11:19:43 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvoAANul0EdQDPIahWdsb2JhbACQfgEBAQgEBgcIEwebBg X-IronPort-AV: E=Sophos;i="4.25,461,1199660400"; d="scan'208";a="8113195" Received: from concorde.inria.fr ([192.93.2.39]) by mail2-smtp-roc.national.inria.fr with ESMTP; 07 Mar 2008 11:19:42 +0100 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id m27AJgFX024959 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Fri, 7 Mar 2008 11:19:42 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvoAANul0EdQDPIahWdsb2JhbACQfgEBAQgEBgcIEwebBg X-IronPort-AV: E=Sophos;i="4.25,461,1199660400"; d="scan'208";a="8113193" Received: from smtp20.orange.fr ([80.12.242.26]) by mail2-smtp-roc.national.inria.fr with ESMTP; 07 Mar 2008 11:19:42 +0100 Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf2006.orange.fr (SMTP Server) with ESMTP id 3C1C81C00091; Fri, 7 Mar 2008 11:19:42 +0100 (CET) Received: from [192.168.1.59] (APuteaux-154-1-94-92.w83-204.abo.wanadoo.fr [83.204.229.92]) by mwinf2006.orange.fr (SMTP Server) with ESMTP id 0AF1F1C0009A; Fri, 7 Mar 2008 11:19:42 +0100 (CET) X-ME-UUID: 20080307101942449.0AF1F1C0009A@mwinf2006.orange.fr Message-ID: <47D116B8.6010500@frisch.fr> Date: Fri, 07 Mar 2008 11:19:36 +0100 From: Alain Frisch User-Agent: Thunderbird 2.0.0.12 (Windows/20080213) MIME-Version: 1.0 To: Berke Durak Cc: caml-list Subject: Re: [Caml-list] Canonical Set/Map datastructure? References: <47CECF23.1020508@exalead.com> <47CFBF04.9030703@exalead.com> In-Reply-To: <47CFBF04.9030703@exalead.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 47D116BE.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; frisch:01 frisch:01 berke:01 durak:01 hash-consing:01 hashtable:01 worst-case:01 hash-consing:01 polymorphic:01 wrote:01 caml-list:01 alain:01 alain:01 data:02 data:02 Berke Durak wrote: > However, the idea of combining hash-consing and Patricia trees, however > elegant, does not suit my problem. Basically, you are cheating by using > an auxiliary data structure, the hashtable (which is also O(n^2) > worst-case). You can also implement hash-consing with the Map module (or a polymorphic version of it) to avoid the worst case complexity. But yes, you need an extra data structure. -- Alain