From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <syshen@nudt.edu.cn>
X-Original-To: caml-list@sympa.inria.fr
Delivered-To: caml-list@sympa.inria.fr
Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104])
	by sympa.inria.fr (Postfix) with ESMTPS id C45FF7EE51
	for <caml-list@sympa.inria.fr>; Fri, 12 Apr 2013 16:39:37 +0200 (CEST)
Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender
  authenticity information available from domain of
  syshen@nudt.edu.cn) identity=pra; client-ip=61.187.54.11;
  receiver=mail3-smtp-sop.national.inria.fr;
  envelope-from="syshen@nudt.edu.cn";
  x-sender="syshen@nudt.edu.cn"; x-conformance=sidf_compatible
Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender
  authenticity information available from domain of
  syshen@nudt.edu.cn) identity=mailfrom;
  client-ip=61.187.54.11;
  receiver=mail3-smtp-sop.national.inria.fr;
  envelope-from="syshen@nudt.edu.cn";
  x-sender="syshen@nudt.edu.cn"; x-conformance=sidf_compatible
Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender
  authenticity information available from domain of
  postmaster@nudt.edu.cn) identity=helo;
  client-ip=61.187.54.11;
  receiver=mail3-smtp-sop.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: AqEIAP8baFE9uzYLdGdsb2JhbABQhmq+C4FJDgEMFQg8ghaBHgkBQF8kiAKPaYwyjkwIiT+JEZFIgRcDiQGOAZQpghs
X-IPAS-Result: AqEIAP8baFE9uzYLdGdsb2JhbABQhmq+C4FJDgEMFQg8ghaBHgkBQF8kiAKPaYwyjkwIiT+JEZFIgRcDiQGOAZQpghs
X-IronPort-AV: E=Sophos;i="4.87,462,1363129200"; 
   d="scan'208";a="10763463"
Received: from mail.nudt.edu.cn (HELO nudt.edu.cn) ([61.187.54.11])
  by mail3-smtp-sop.national.inria.fr with ESMTP; 12 Apr 2013 16:39:34 +0200
Received: by ajax-webmail-coremail.nudt.edu.cn (Coremail) ; Fri, 12 Apr 2013
 22:36:22 +0800 (GMT+08:00)
Date: Fri, 12 Apr 2013 22:36:22 +0800 (GMT+08:00)
From: =?GBK?B?yfLKpNPu?= <syshen@nudt.edu.cn>
To: caml-list <caml-list@inria.fr>
Message-ID: <58e60ce1.4599.13dfeacfdb3.Coremail.syshen@nudt.edu.cn>
MIME-Version: 1.0
Content-Type: multipart/alternative; 
	boundary="----=_Part_61614_1773426435.1365777382835"
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:AQAAf0CZ3kPnG2hRJlYeAA--.4801W
X-CM-SenderInfo: xv1vxvnq6q3vvwohv3gofq/1tbiAQAFE1C8Ui+1OAAVse
X-Coremail-Antispam: 1Ur529EdanIXcx71UUUUU7IcSsGvfJ3iIAIbVAYjsxI4VW7Jw
	CS07vEb4IE77IF4wCS07vE1I0E4x80FVAKz4kxMIAIbVAFxVCaYxvI4VCIwcAKzIAtYxBI
	daVFxhVjvjDU=
Subject: [Caml-list] [CAML]:: efficient data structure for storing and
 searching int list list


------=_Part_61614_1773426435.1365777382835
Content-Type: text/plain; charset=GBK
Content-Transfer-Encoding: 7bit

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




------=_Part_61614_1773426435.1365777382835
Content-Type: text/html; charset=GBK
Content-Transfer-Encoding: 7bit

Dear all:<div><br></div><div>I have an int list list, whose name is LL</div><div><br></div><div>and I need to frequently decide whether a particular int list, whose name is L, is a sublist of an element of LL.</div><div><br></div><div>Is there any efficent data structure to do this?</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>At the mean time, the space is not a big problem, but the run time overhead is major concern,</div><div><br></div><div>So if there exist any more faster data structure?</div><div><br></div><div>Thank you</div><div><br></div><div>Shen</div><div><br></div><div><br></div>
------=_Part_61614_1773426435.1365777382835--