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 2A6697EE51 for ; Sat, 13 Apr 2013 09:02:14 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of syshen@nudt.edu.cn) identity=pra; client-ip=61.187.54.11; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="syshen@nudt.edu.cn"; x-sender="syshen@nudt.edu.cn"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of syshen@nudt.edu.cn) identity=mailfrom; client-ip=61.187.54.11; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="syshen@nudt.edu.cn"; x-sender="syshen@nudt.edu.cn"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@nudt.edu.cn) identity=helo; client-ip=61.187.54.11; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="syshen@nudt.edu.cn"; x-sender="postmaster@nudt.edu.cn"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AsMIAEICaVE9uzYLdGdsb2JhbABQhmy+ESiBGw4BDBUIPIIfAQEFIwRSEAUEAhgCAiYCAlcGExGIAo8HmwSJHokRgSONQTMHgi6BEwOJAYo1g0ySZoFDghs X-IPAS-Result: AsMIAEICaVE9uzYLdGdsb2JhbABQhmy+ESiBGw4BDBUIPIIfAQEFIwRSEAUEAhgCAiYCAlcGExGIAo8HmwSJHokRgSONQTMHgi6BEwOJAYo1g0ySZoFDghs X-IronPort-AV: E=Sophos;i="4.87,466,1363129200"; d="scan'208";a="13093535" Received: from mail.nudt.edu.cn (HELO nudt.edu.cn) ([61.187.54.11]) by mail2-smtp-roc.national.inria.fr with ESMTP; 13 Apr 2013 09:02:12 +0200 Received: by ajax-webmail-coremail.nudt.edu.cn (Coremail) ; Sat, 13 Apr 2013 14:58:57 +0800 (GMT+08:00) Date: Sat, 13 Apr 2013 14:58:57 +0800 (GMT+08:00) From: =?utf-8?B?5rKI6IOc5a6H?= To: "Jean-Francois Monin" Cc: caml-list Message-ID: <6936226f.468c.13e02309329.Coremail.syshen@nudt.edu.cn> In-Reply-To: <20130412154804.GI6877@melezet> References: <58e60ce1.4599.13dfeacfdb3.Coremail.syshen@nudt.edu.cn> <20130412154804.GI6877@melezet> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Originating-IP: [113.246.242.103] X-Priority: 3 X-Mailer: Coremail Webmail Server Version 4.0.5a build 20121109(20529.5019.5013) Copyright (c) 2002-2013 www.mailtech.cn nudt-out X-SendMailWithSms: false X-CM-TRANSID:AQAAf0A5f0QyAmlRL6weAA--.4648W X-CM-SenderInfo: xv1vxvnq6q3vvwohv3gofq/1tbiAQAIE1C8Ui+78gAAsC X-Coremail-Antispam: 1Ur529EdanIXcx71UUUUU7IcSsGvfJ3iIAIbVAYjsxI4VW7Jw CS07vEb4IE77IF4wCS07vE1I0E4x80FVAKz4kxMIAIbVAFxVCaYxvI4VCIwcAKzIAtYxBI daVFxhVjvjDU= Subject: Re: Re: [Caml-list] [CAML]:: efficient data structure for storing and searching int list list Dear Monin: thank you for your help. But I think trie is too general in the sense that it did not effiecently ha= ndle the case that two list with multiple(not just one) shared sublist. For example, I first insert a list a->b->c->d->e->f into trie, and then I i= nsert a->b->d->e into the trie. the trie can not store the second shared sublist d->e in the same place, it= can only store them like=C2=A0 a->b->c->d->e->f =C2=A0 =C2=A0 ->d->e do you have more suggesion on this? Shen > -----=E5=8E=9F=E5=A7=8B=E9=82=AE=E4=BB=B6----- > =E5=8F=91=E4=BB=B6=E4=BA=BA: "Jean-Francois Monin" > =E5=8F=91=E9=80=81=E6=97=B6=E9=97=B4: 2013-04-12 23:48:04 (=E6=98=9F=E6= =9C=9F=E4=BA=94) > =E6=94=B6=E4=BB=B6=E4=BA=BA: "=E6=B2=88=E8=83=9C=E5=AE=87" > =E6=8A=84=E9=80=81: caml-list > =E4=B8=BB=E9=A2=98: Re: [Caml-list] [CAML]:: efficient data structure for= storing and searching int list list >=20 > You may have some total order on the elements of your lists. > Then consider only sorted lists, and implement LL with tries. >=20 > JF >=20 > On Fri, Apr 12, 2013 at 10:36:22PM +0800, =E6=B2=88=E8=83=9C=E5=AE=87 wro= te: > > 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 elem= ent 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 >=20 > --=20 > Jean-Francois Monin > LIAMA Project FORMES, CNRS & Universite de Grenoble 1 & > Tsinghua University