F# Map: How do I get the next bigger key?

Question

I have  hugeMap<int*int*int,'t> which is used for a sparse array.

I need to iterate in a subset, i.e. for find the first key bigger than (10,0,0) and then iterate over all elements up to but excluding (11,0,0)

This is a very efficient operation normally in Maps, but I cannot find the necessary operations. Please help.

Using toSeq or similar and then have a predicate that checks that (x,y,z) is inside (10,0,0) (11,0,0) seems to be very inefficient.

Answer 1

You could iterate through the map. Don't know about efficiency but at least you don't have to convert to Seq:

let map = Map.ofList [
                      (10, 0, 1), "v1"; 
                      (5,  0, 2), "v2"; 
                      (10, 0, 0), "v3"; 
                      (7,  3, 2), "v4"; 
                      (10, 3, 0), "v5"; 
                      (5,  0, 0), "v6"; 
                      (13, 4, 5), "v7"; 
                      (11, 0, 0), "v8"; 
                      (10, 8, 2), "v9"; 
                      (11, 1, 0), "v10"; 
                     ]
let iterateSubset level map =
    map |> Map.iter (fun (k, l, m) value -> if (k, l, m) > (level, 0, 0)  && (k, l, m) < (level + 1, 0, 0) 
                                                then printfn "Found element: key = (%d,%d,%d) val = %A" k l m value) 

iterateSubset 10 map

> 
Found element: key = (10,0,1) val = "v1"
Found element: key = (10,3,0) val = "v5"
Found element: key = (10,8,2) val = "v9"

---

Petr

Answer 2

You could iterate through the map. Don't know about efficiency but at least you don't have to convert to Seq:

Thank you.

Yes, it is a solution, but way toooooo slow. The Map contains 1,000,000 values, and maybe I want to look at 20 of them.With your implementation, in average I would have to look at 500,000.

However, for ordered binary tree of any type, it is possible to do it in 20 * O(log 1000000) which is about 20*20 = 400, which should be 1000 faster than using  Map.iter.

Answer 3

Yes, unfortunately, the Map module is severely lacking in useful algorithms; hopefully it is greatly expanded in F# 3.0.

If it's feasible for you to put all of your map's keys into an array for the purpose of this algorithm, then Array.BinarySearch can help here:

let iterateSubset action (level:int) map =
    let inline fst3 t = let v,_,_ = t in v
    let arr = Map.toSeq map |> Seq.map fst |> Seq.toArray
    let rec loop = function
        | i when i >= arr.Length || fst3 arr.[i] > level -> ()
        | i -> let k = arr.[i] in action k map.[k]
               loop (i + 1)
    match System.Array.BinarySearch (arr, (level, 0, 0), ComparisonIdentity.Structural) with
        | i when i < 0 -> ~~~i
        | i            -> i + 1
    |> loop

Map.ofList [ (10, 0, 1), "v1"
             (5,  0, 2), "v2"
             (10, 0, 0), "v3"
             (7,  3, 2), "v4"
             (10, 3, 0), "v5"
             (5,  0, 0), "v6"
             (13, 4, 5), "v7"
             (11, 0, 0), "v8"
             (10, 8, 2), "v9"
             (11, 1, 0), "v10" ]
|> iterateSubset (printfn "%A :: %s") 10

Answer 4

It ugly and only solves a specific problem, but you might be able to use this map by restructuring to something like

let items2 =          [
                      10 , ((0, 1), "v1"); 
                      5, ((0, 2), "v2"); 
                      10, ((0, 0), "v3"); 
                      7, ((3, 2), "v4"); 
                      10, ((3, 0), "v5"); 
                      5, ((0, 0), "v6"); 
                      13, ((4, 5), "v7"); 
                      11, ((0, 0), "v8"); 
                      10, ((8, 2), "v9"); 
                      11, ((1, 0), "v10"); 
                     ]

type MapType = Map<int,Map<(int*int),string>>
let buildmap (map:MapType) (primekey,secmap) = 
  match map.TryFind(primekey) with
  | Some m -> map.Add(primekey,m.Add(secmap)) // I think this will replace key without needing to call remove
  | None -> map.Add( primekey, Map.empty.Add( secmap ) )
    
let m = items2 |> List.fold (fun m i -> buildmap m i) Map.empty


printfn "%A" (m.Item(10))

Answer 5

Thank you for your solutions.

I solved it by using the Map in the F# PowerPack. It has a method First

        /// Search the map looking for the first element where the given function returns a <c>Some</c> value
        member First: ('Key -> 'Value -> 'T option) -> 'T option

and then I could write an iterator like this that can start anywhere in the Map with O(log n) performance. I also added a Last which works like First, but from the right instead.

(** helpers for First *)
let bigger_than_current coord = (fun next_coord v4 -> if next_coord > coord then Some(next_coord,v4) else None)
let bigger_or_equal_than_current coord = (fun next_coord v4 -> if next_coord >= coord then Some(next_coord,v4) else None)


(** apply f to all elements in arr where x = x
    Same as (!arr).Iterate (fun (x2,_,_) v -> if x=x2 then f v) *)
let iter2d (arr:t<'t>) x (f:'t -> unit) : unit =
    let rec iter2d_internal next = 
        // I really hope tail calls works well!
        match next with 
        | None -> ()
        | Some( (x3,y3,z3) as coord, v3 ) -> 
            if x3 > x then () // finished
            else 
                f v3;
                let next = (!arr).First(bigger_than_current coord)
                iter2d_internal next

    let start = (!arr).First(bigger_or_equal_than_current (x,-9999999,-9999999))
    iter2d_internal start

However, I really think these enumerators used by .NET really hides the underlaying complexity. Enumerators will be the curse of modern programming, just like lists were in Lisp, works fine with small data, and never works with big data, because you get O(n^2) behaviour all the time.

Enumerations that are efficient within a range would be really nice.

Answer 6

Still not satisfied, looked at the execution using the VS2010 sample profiler of a release build.

Turn out that

next_coord > coord 

is extremely expensive if you compare int*int*int. So I replaced by

let compare_int_int_int (ax,ay,az) (bx,by,bz) =         
    let c = ax - bx
    if c <> 0 then c
    else 
        let c = ay - by
        if c <> 0 then c
        else az - bz

and now it is better. However, it is still not as good as I want. I will probably implement a better iterator without using First later.

Answer 7

Since maps are defined to have the keys ordered by generic comparison (see http://msdn.microsoft.com/en-us/library/ee353413.aspx), once you've found the first item, the problem reduces to a takeWhile operation that just inspects the first element of the tuple, along the lines of

map |> Seq.skipWhile(fun x -> let a,b,c = x.Key
                              a < 10 || (a = 10 && b = 0 && c = 0))
    |> Seq.takeWhile(fun x -> let a,b,c = x.Key
                              a < 11) |> Seq.iter (printfn "%A");;

where the efficiency would be to avoid the O(n) traversal needed in the skipWhile phase (e.g. using the First function or Array binary search for the first key, as mentioned above).