Re: Re: [Caml-list] [CAML]:: efficient data structure for storing and searching int list list

[沈胜宇 <syshen@nudt.edu.cn>]

Dear Monin:

thank you for your help.

But I think trie is too general in the sense that it did not effiecently handle 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 insert 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 
a->b->c->d->e->f
    ->d->e

do you have more suggesion on this?

Shen
> -----原始邮件-----
> 发件人: "Jean-Francois Monin" <jean-francois.monin@imag.fr>
> 发送时间: 2013-04-12 23:48:04 (星期五)
> 收件人: "沈胜宇" <syshen@nudt.edu.cn>
> 抄送: caml-list <caml-list@inria.fr>
> 主题: 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