next up previous
Next: Sparse matrix-vector multiplication Up: Benchmark Code Previous: Line-fit

Selection

   function select_kth(s, k) =
     let pivot = s[#s/2]; 
         les = {e in s | e < pivot}
     in 
       if (k < #les) then
         select_kth(les, k)
       else 
         let grt = {e in s | e > pivot}
         in if (k >= #s - #grt) then
              select_kth(grt, k - (#s - #grt))
            else pivot;

For the selection benchmarks, s was the integer index vector [0, 1, 2, ...], and k was one third of the length of s.


next up previous
Next: Sparse matrix-vector multiplication Up: Benchmark Code Previous: Line-fit

Jonathan Hardwick