From 22cf9c6f33dfad88aa57e58c132bef1459768210 Mon Sep 17 00:00:00 2001 From: Huibo SHI Date: Fri, 2 May 2014 14:45:29 +0200 Subject: [PATCH] Une version marche bien avec bitvector --- src/query_tree.ml | 11 ++++------- src/query_tree.mli | 4 ++-- src/table.ml | 21 +++++++++++++-------- src/table_driver.ml | 4 ++-- tests/exemple.xml | 15 ++++++++++++--- tests/single_test.sh | 10 ++-------- 6 files changed, 35 insertions(+), 30 deletions(-) diff --git a/src/query_tree.ml b/src/query_tree.ml index 679d992..d9e6ada 100644 --- a/src/query_tree.ml +++ b/src/query_tree.ml @@ -1,6 +1,7 @@ open Table -let compteur = ref 0 +let query_tree_size = ref 0 + let table_qtree = QTreeHash.create 97 @@ -147,17 +148,13 @@ let rec eval_qtree tree start q = match q.desc with | Start -> start | Dom -> Bitvector.create ~init:true (Naive_tree.size tree) - (*let v = Bitvector.create (Naive_tree.size tree) in - for i=0 to (Bitvector.length v)-1 do - Bitvector.set v i true - done; - v*) | Tag (t,k) -> element_by_tag tree t k | Axis (a,q1) -> let v = eval_qtree tree start q1 in eval_axis tree v a | Binop (op,q1,q2)-> begin let v1 = eval_qtree tree start q1 in let v2 = eval_qtree tree start q2 in + Table.node_compteur := !Table.node_compteur + 2*Bitvector.length v1; match op with | Union -> Bitvector.union v1 v2 | Inter -> Bitvector.inter v1 v2 @@ -165,9 +162,9 @@ let rec eval_qtree tree start q = end in QTreeHash.add table_qtree q res; - compteur := !compteur + Bitvector.length res; (*????8*) res end in (* debug tree q resultat;*) + incr query_tree_size; resultat diff --git a/src/query_tree.mli b/src/query_tree.mli index 7335e52..130d7cb 100644 --- a/src/query_tree.mli +++ b/src/query_tree.mli @@ -1,5 +1,5 @@ -val compteur : int ref -(**the counter of nodes*) +val query_tree_size : int ref +(**the size of query_tree*) val element_by_tag : Naive_tree.t -> QNameSet.t -> Tree.NodeKind.t -> Bitvector.t (** [element_by_tag t tag] returns all the nodes whose tag equal to [tag] in the tree [t]. *) diff --git a/src/table.ml b/src/table.ml index c40e93b..1c10693 100644 --- a/src/table.ml +++ b/src/table.ml @@ -1,4 +1,6 @@ +let node_compteur = ref 0 + type query_tree_desc = Binop of op * query_tree * query_tree | Axis of Xpath.Ast.axis * query_tree | Start @@ -150,19 +152,20 @@ let get_descendant tree c v = else let n1 = Naive_tree.first_child tree n in let j = Naive_tree.preorder tree n in Bitvector.set acc j true; + incr node_compteur; let acc1 = aux n1 acc in let n2 = Naive_tree.next_sibling tree n in aux n2 acc1 in let v0 = Bitvector.create (Naive_tree.size tree) in - (* let v = bitvector_of_nodes tree ln in*) if c then begin for i = 0 to (Bitvector.length v)-1 do if Bitvector.get v i then let n = Naive_tree.by_preorder tree i in let n1 = Naive_tree.first_child tree n in let _ = aux n1 v0 in - Bitvector.set v0 i true + Bitvector.set v0 i true; + incr node_compteur done; end else for i = 0 to (Bitvector.length v)-1 do @@ -179,10 +182,10 @@ let get_child tree v = else let n1 = Naive_tree.next_sibling tree n in Bitvector.set acc (Naive_tree.preorder tree n) true; + incr node_compteur; aux n1 acc in let v0 = Bitvector.create (Naive_tree.size tree) in - (*let v = bitvector_of_nodes tree ln in*) for i = 0 to (Bitvector.length v)-1 do if Bitvector.get v i then let n = Naive_tree.by_preorder tree i in @@ -198,10 +201,10 @@ let get_followingSibling tree v = if n1 == Naive_tree.nil then acc else begin Bitvector.set acc (Naive_tree.preorder tree n1) true; + incr node_compteur; aux n1 acc end in let v0 = Bitvector.create (Naive_tree.size tree) in - (* let v = bitvector_of_nodes tree ln in*) for i = 0 to (Bitvector.length v)-1 do if Bitvector.get v i then let n = Naive_tree.by_preorder tree i in @@ -215,27 +218,27 @@ let rec get_firstBling tree n pred = let get_parent tree v = let v0 = Bitvector.create (Naive_tree.size tree) in - (* let v = bitvector_of_nodes tree ln in*) for i = 0 to (Bitvector.length v)-1 do if Bitvector.get v i then let n = Naive_tree.by_preorder tree i in let n1 = get_firstBling tree n Naive_tree.nil in let n2 = Naive_tree.parent_of_first tree n1 in if n2 != Naive_tree.nil then begin let j = Naive_tree.preorder tree n2 in - Bitvector.set v0 j true + Bitvector.set v0 j true; + incr node_compteur end done; v0 let get_ancestor tree b v = let v0 = Bitvector.create (Naive_tree.size tree) in - (* let v = bitvector_of_nodes tree ln in *) if b then begin for i = (Bitvector.length v)-1 downto 0 do if Bitvector.get v i then begin Bitvector.set v0 i true; + incr node_compteur; let n = Naive_tree.by_preorder tree i in let n0 = ref n in while !n0 != Naive_tree.nil do @@ -245,6 +248,7 @@ let get_ancestor tree b v = if n2 != Naive_tree.nil then begin let j = Naive_tree.preorder tree n2 in Bitvector.set v0 j true; Bitvector.set v j true; + node_compteur := !node_compteur + 2; end done; end @@ -263,6 +267,7 @@ let get_ancestor tree b v = if n2 != Naive_tree.nil then begin let j = Naive_tree.preorder tree n2 in Bitvector.set v0 j true; Bitvector.set v j true; + node_compteur := !node_compteur + 2; end done; end @@ -275,10 +280,10 @@ let get_preSibling tree v = if n1 == Naive_tree.nil then acc else begin Bitvector.set acc (Naive_tree.preorder tree n1) true; + incr node_compteur; aux n1 acc end in let v0 = Bitvector.create (Naive_tree.size tree) in - (* let v = bitvector_of_nodes tree ln in*) for i = 0 to (Bitvector.length v)-1 do if Bitvector.get v i then let n = Naive_tree.by_preorder tree i in diff --git a/src/table_driver.ml b/src/table_driver.ml index e961abb..07c6523 100644 --- a/src/table_driver.ml +++ b/src/table_driver.ml @@ -5,7 +5,7 @@ open Query_tree let parse_xpath p = Xpath.Parser.parse (Ulexing.from_utf8_string p) -let display = ref false +let display = ref true let main () = let () = Table_options.parse () in @@ -49,7 +49,7 @@ let main () = let t2 = Unix.gettimeofday () in let t = (t2 -. t1) *. 1000. in let _ = if !Table_options.count then - Format.fprintf Format.std_formatter "there are %i nodes\nit takes %fms\n" !Query_tree.compteur t; + Format.fprintf Format.std_formatter "there are %i nodes\nquery_tree size : %i\nit takes %fms\n" !Table.node_compteur !Query_tree.query_tree_size t; in exit 0 diff --git a/tests/exemple.xml b/tests/exemple.xml index d599d06..da48927 100644 --- a/tests/exemple.xml +++ b/tests/exemple.xml @@ -1,12 +1,21 @@ -China + + China Beijing + + -Japan + + Japan Tokyo - + +Japan + Tokyo + + + diff --git a/tests/single_test.sh b/tests/single_test.sh index 3c6d2b3..902fec5 100755 --- a/tests/single_test.sh +++ b/tests/single_test.sh @@ -1,18 +1,12 @@ #!/bin/sh -INPUT=tests/xmark_0.00.xml +INPUT=tests/xmark_0.05.xml QUERIES="$INPUT".queries - - - perl -MTime::HiRes -e 'print Time::HiRes::time(),"\n"'; cat "$QUERIES" | while read N Q; do echo Query "$N : $Q" - src/tatoo.native -d "$INPUT" "$Q" > /tmp/huibo"$N".xml + src/tatoo.native -s -d "$INPUT" "$Q" -o /dev/null > /tmp/kim.xml done - - perl -MTime::HiRes -e 'print Time::HiRes::time(),"\n"'; - -- 2.17.1