From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id ECDE87EE5B for ; Fri, 12 Apr 2013 17:48:17 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of jeanfrancois.monin@gmail.com) identity=pra; client-ip=209.85.210.49; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="jeanfrancois.monin@gmail.com"; x-sender="jeanfrancois.monin@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of jeanfrancois.monin@gmail.com designates 209.85.210.49 as permitted sender) identity=mailfrom; client-ip=209.85.210.49; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="jeanfrancois.monin@gmail.com"; x-sender="jeanfrancois.monin@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-da0-f49.google.com) identity=helo; client-ip=209.85.210.49; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="jeanfrancois.monin@gmail.com"; x-sender="postmaster@mail-da0-f49.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AssDAHIsaFHRVdIxk2dsb2JhbABQDoZcuRGGLRYOAQEBAQcLCwkUBCSCHwEBBSMPAQ0BOAEDDAEFAwIYAgIFIQICDwUgAQUBIogVAw4BjymPJItgg0qEeCcNiVcBBQyBF5ApgRMDiQGKNYNLjzA/gVmBH3dM X-IPAS-Result: AssDAHIsaFHRVdIxk2dsb2JhbABQDoZcuRGGLRYOAQEBAQcLCwkUBCSCHwEBBSMPAQ0BOAEDDAEFAwIYAgIFIQICDwUgAQUBIogVAw4BjymPJItgg0qEeCcNiVcBBQyBF5ApgRMDiQGKNYNLjzA/gVmBH3dM X-IronPort-AV: E=Sophos;i="4.87,462,1363129200"; d="scan'208";a="13035344" Received: from mail-da0-f49.google.com ([209.85.210.49]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 12 Apr 2013 17:48:17 +0200 Received: by mail-da0-f49.google.com with SMTP id t11so1177149daj.8 for ; Fri, 12 Apr 2013 08:48:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:sender:date:from:to:cc:subject:message-id:references :mime-version:content-type:content-disposition :content-transfer-encoding:in-reply-to:user-agent; bh=V80NkXj/lTD4pkmI1UWQSe3/sF0YqJYwu1NIClLdlwo=; b=EdMQHeUnVhas+9aaycnLqKnRpqF0h2+vaIVtHTfjlZp47VF2Z+ueCSAo1lVmXWQJjZ IMZRWkxUIWQqPFG9fqGIuFbsGfkIqUMGsRsDlngnZpKW3vRzLnDnnp15DiKIQ6uSSw3I p/3RJVpCohzIOHnFIvSnlH1wrVWt0iW0w6DvGC3kWNaL7KuOOYfDxc1sCu5Jt/5NVaeV PAT7OiDaLjSxNLrt52SljoDMIj78ga/XuSeBXKXgFk99GjkzA/SQEGSYVtqRZRBfzfhX eCHBkyYj0JYyrlzgNDfCRE69Ei4Kfua2cKKWImKB6cW7RZ2/k2Slhh+CcbYZK6zArahR /m1A== X-Received: by 10.68.135.231 with SMTP id pv7mr15251282pbb.108.1365781695383; Fri, 12 Apr 2013 08:48:15 -0700 (PDT) Received: from localhost ([221.217.230.140]) by mx.google.com with ESMTPS id qr7sm9039255pbc.16.2013.04.12.08.48.12 (version=TLSv1.2 cipher=RC4-SHA bits=128/128); Fri, 12 Apr 2013 08:48:14 -0700 (PDT) Sender: =?UTF-8?Q?Jean=2DFran=C3=A7ois_Monin?= Date: Fri, 12 Apr 2013 23:48:04 +0800 From: Jean-Francois Monin To: =?utf-8?B?5rKI6IOc5a6H?= Cc: caml-list Message-ID: <20130412154804.GI6877@melezet> References: <58e60ce1.4599.13dfeacfdb3.Coremail.syshen@nudt.edu.cn> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <58e60ce1.4599.13dfeacfdb3.Coremail.syshen@nudt.edu.cn> User-Agent: Mutt/1.5.21 (2010-09-15) Subject: Re: [Caml-list] [CAML]:: efficient data structure for storing and searching int list list You may have some total order on the elements of your lists. Then consider only sorted lists, and implement LL with tries. JF On Fri, Apr 12, 2013 at 10:36:22PM +0800, 沈胜宇 wrote: > Dear all: > I have an int list list, whose name is LL > and I need to frequently decide whether a particular int list, whose name > is L, is a sublist of an element of LL. > Is there any efficent data structure to do this? > At the mean time, I store LL as (int, bool) Hashtbl.t list, that is, each > element of LL is stored as a hash table. > So searching L in LL is reduce to decide whether there exist an element of > LL, such every element of L hit in this element. > At the mean time, the space is not a big problem, but the run time > overhead is major concern, > So if there exist any more faster data structure? > Thank you > Shen -- Jean-Francois Monin LIAMA Project FORMES, CNRS & Universite de Grenoble 1 & Tsinghua University