Performance issues using SortedSet (100x slower than C#) [Solved]

1

I am trying to use the SortedSet collection to search for the range associated to an specific value. For example if the SortedSet has the pairs (1, 9), (10, 19) and (20, 29), searching for the number 23 will find the pair (20, 29). Here is my implementation that takes 80 seconds to execute while the same implementation in Java using TreeSet takes half a second. Is there a problem with my implementation?

open System.Collections.Generic
let s = SortedSet<int*int>()
for i in 0 .. 10 .. 100000 do
    s.Add (i, i+9) |> ignore

let mutable c = 0
for x in 0 .. 100000 do
    let upper = s.GetViewBetween ((Int32.MinValue, Int32.MinValue), (x, Int32.MaxValue))
    let a, b = Seq.tryLast upper |> Option.defaultValue (-1, -1)
    if a <= x && x <= b then
        c <- c +  1

printfn "%A" c

Thank you,

2

I have implemented now the code in C# and it is even faster than Java, so it means the problem is in my F# implementation and not in .NET.

using System;
using System.Collections.Generic;

struct Pair : IComparable<Pair>
{
    public double X, Y;
    public Pair(double x)
    {
        this.X = x;
        this.Y = 0;
    }
    public Pair(double x, double y)
    {
        this.X = x;
        this.Y = y;
    }
    public int CompareTo(Pair other)
    {
        return X.CompareTo(other.X);
    }
}
class Program
{
    static void Main(string[] args)
    {
        var s = new SortedSet<Pair>();
        for (int i = 0; i < 100000; i += 10)
        {
            s.Add(new Pair { X = i, Y = i + 9 });
        }
        int c = 0;
        for (int x = 0; x <= 100000; x++)
        {
            var lower = new Pair { X = Int32.MinValue, Y = Int32.MinValue };
            var upper = new Pair { X = x, Y = Int32.MaxValue };
            var current = s.GetViewBetween(lower, upper).Max;
            if (current.X <= x && x <= current.Y)
            {
                c++;
            }
        }
        Console.WriteLine($"{c}");
    }
}
3

I have found the problem: Using Seq.last to find the last element of the SortedSet. I switched it to be the Max property and now the performance is the same as the other languages:

open System
open System.Collections.Generic
let s = SortedSet<int*int>()
for i in 0 .. 10 .. 100000 do
    s.Add (i, i+9) |> ignore
let mutable c = 0
let lower = (Int32.MinValue, Int32.MinValue)
for x in 0 .. 100000 do
    let upper = (x, Int32.MaxValue)
    let a, b = s.GetViewBetween(lower, upper).Max
    if a <= x && x <= b then
        c <- c +  1

printfn "%A" c
1 Like