Commits

Joby Poriyath committed d4aa004

triple sum with binary search O(n^2logn)

Comments (0)

Files changed (8)

+#!/bin/bash
+
+ocamlbuild -classic-display triple_sum.byte
+ocamlbuild -classic-display triple_sum.native
+ocamlbuild -classic-display -lib unix echo.byte
+ocamlbuild -classic-display -lib unix echo.native
+ocamlbuild -classic-display main.byte
+ocamlbuild -classic-display main.native
+
+#!/bin/bash
+
+ocamlbuild -classic-display -clean
+rm -vf *~
+let echo () = 
+  for i = 1 to (Array.length (Sys.argv) - 1)
+  do
+    Printf.printf "%s " Sys.argv.(i)
+  done;
+  print_newline ()
+
+let _ = echo ()
 union 8 2
 union 9 0
 union 9 5
+connected 2 9
+let debug = ref false
+
 let triple_sum a = 
   let n = (Array.length a - 1) in
   let count = ref 0 in
   done;
   !count
 
+let triple_sum_fast a =
+  let n = Array.length a - 1 in
+  let count = ref 0 in
+  let cmp x y = if x > y 
+    then 1 
+    else if x < y then -1 
+    else 0 in
+  begin
+    Array.fast_sort cmp a;
+    for i = 0 to n do
+      for j = i + 1 to n do
+        let s = a.(i) + a.(j) in
+        let k = Util.binary_search a (-s) in
+        if k > j
+        then 
+          begin
+            count := !count + 1; 
+            if !debug 
+            then
+              begin
+                Printf.printf "a[%d] = %d a[%d] = %d a[%d] = %d" i a.(i) 
+                  j a.(j) k  a.(k) ; 
+                print_newline ()
+              end
+          end
+        else ()
+      done
+    done;
+    !count
+  end
+    
+
 let main n =
   let n = (if !Sys.interactive then n else int_of_string Sys.argv.(1)) in
   let a = Array.make (n * 1024) 0 in
-  for i = 0 to Array.length a - 1 do
-    a.(i) <- Util.random_int 1_000_000
-  done;
-  let time_taken, result = Util.time_it triple_sum a in
-  Printf.printf "result = %d time_taken = %f \n" result time_taken
+  begin
+    for i = 0 to Array.length a - 1 do
+      a.(i) <- Util.random_int 1_000_000
+    done;
+    let time_taken, result = Util.time_it triple_sum_fast a in
+    Printf.printf "result = %d time_taken = %f\n" result time_taken;
+    print_newline ();
+    (* let time_taken, result = Util.time_it triple_sum a in *)
+    (* Printf.printf "result = %d time_taken = %f" result time_taken; *)
+    (* print_newline (); *)
+  end
     
 let _ = main 1
       
 end
 
-module U = WeightedUnion
+module U = WeightedPathCompressedUF1
 
 let main () =
   
   let rec get_line () =
     try 
       let line = String.trim (input_line stdin) in
-      if line = "" then get_line () else Some line
+      if line = "" then get_line () 
+      else if Util.startswith line "#" then get_line ()
+      else Some line
     with End_of_file -> None 
   in 
   let loop = ref true in
   let j = index_r i (s_len - 1) in
   if s = "" then "" else String.sub s i (j - i)
   
-
 let rec join s = function
   | [] -> ""
   | (w::ws) -> (w ^ s) ^ join s ws
 
+let startswith s1 s2 =
+  let l1 = String.length s1 in
+  let l2 = String.length s2 in
+  let rec check i = 
+    if (i >= l2) then true (* bound check *)
+    else if s1.[i] = s2.[i] then check (i + 1) 
+    else false
+  in
+  if l1 < l2 then false
+  else check 0
+
+let range n = 
+  let rec range_aux i lst = 
+    if i < 0 then lst
+    else range_aux (i - 1) (i :: lst)
+  in range_aux (n - 1) []
+
+let binary_search a x =
+  let rec bs_aux i j =
+    if i > j then -1
+    else 
+      let m = (i + j) / 2 in
+      if a.(m) = x then m
+      else if a.(m) < x then
+        bs_aux (m + 1) j
+      else bs_aux i (m - 1)  (* a.(m) > x *)
+  in
+  bs_aux 0 (Array.length a - 1)
+
 let time_it action arg = 
   let t1 = Sys.time () in
   let result = action arg in
 val split_on : (char -> bool) -> string -> string list
 val split : string -> string list
 val join : string -> string list -> string
+val startswith : string -> string -> bool
+val range : int -> int list
+val binary_search : 'a array -> 'a -> int
 val time_it : ('a -> 'b) -> 'a -> float * 'b
 val random_int : int -> int