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

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

• Thursday, February 16, 2012 1:00 PM

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.

### All Replies

• Thursday, February 16, 2012 1:42 PM

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

• Thursday, February 16, 2012 7:17 PM

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.

• Edited by Thursday, February 16, 2012 7:19 PM
•
• Friday, February 17, 2012 5:13 PM

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```
• Edited by Friday, February 17, 2012 5:27 PM
•
• Saturday, February 18, 2012 5:17 AM

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

let m = items2 |> List.fold (fun m i -> buildmap m i) Map.empty

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

• Sunday, February 19, 2012 12:30 PM

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.

• Sunday, February 19, 2012 3:23 PM

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.

• Saturday, February 25, 2012 8:02 PM

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).

• Edited by Saturday, February 25, 2012 8:11 PM
•