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

[simon cruanes <simon.cruanes.2007@m4x.org>]

If the order in the lists does not matter, I would suggest some kind of
Trie (http://en.wikipedia.org/wiki/Trie) to store the *sorted* int
lists; the algorithm for search would recursively explore all the
branches of the trie that can be a superlist of the input list.

Here is a code snippet (not thoroughly tested):

(* ------------------- %< ------ >% ----------------- *)

type trie =
  | Node of bool *  (* end of a list? *)
            (int * trie) list  (* subtries, indexed by their first
element *)

let empty = Node (false, [])

(* add [l] to [trie], assuming [l] is sorted *)
let rec add trie l =
  match trie, l with
  | Node (_, subtries), [] -> Node (true, subtries)
  | Node (b, subtries), x::l' ->
    let subtrie =
      try List.assoc x subtries
      with Not_found -> Node (false, []) in
    (* recursive add *)
    let subtrie = add subtrie l' in
    let subtries = List.remove_assoc x subtries in
    Node (b, (x,subtrie) :: subtries)

(* find whether [l] is a sublist of some list of [trie] *)
let rec find trie l =
  match trie, l with
  | _, [] -> true
  | Node (_, subtries), (x::l') ->
    find_list x subtries l'
and find_list x subtries l' = match subtries with
  | [] -> false
  | (y,subtrie)::subtries' ->
    (if y < x then find subtrie (x::l')
    else if y = x then find subtrie l'
    else false) || find_list x subtries' l'

(* ------------------- %< ------ >% ----------------- *)

Cheers!


Simon

On 12/04/2013 16:36, 沈胜宇 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
> 
>