排序字典自定义关键字查找以提高效率 [英] Sorted Dictionary customize key look-up for efficiency

问题描述

最近，我了解到排序字典类实现了对键的二进制搜索，我想以此为自己的优势。我正在制作一个逐段线性函数类，它表示一堆线的集合

Recently, I learned that the Sorted Dictionary class implements binary search over the keys, and I wanted to use this to my advantage. I am making a piecewise linear function class that represents a collection of lines over a bunch of intervals.

我定义了一个 Interval 类，如下所示：

I defined an Interval class like this:

public class Interval : ICloneable, IComparable, IComparable<Interval>
{
    public Interval()
    {

    }
    public Interval(double start, double end)
    {
        Start = start;
        End = end;
    }

    // Properties
    public double Start { get; set; } = double.NaN;
    public double End { get; set; } = double.NaN;
    public double Span => End - Start;

    // Methods
    public object Clone() => MemberwiseClone();

    public int CompareTo(object obj)
    {
        return Start.CompareTo(obj);
    }

    public int CompareTo([AllowNull] Interval other)
    {
        if (Start < other.Start)
        {
            return -1;
        }
        else if (Start > other.Start)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }

    public bool Contains(double x) => Start <= x && x <= End;
    public override string ToString() => $"[{Start}, {End}]";
}

问题中的 SortedDictionary 的工作原理如下这在分段函数类中：

And the SortedDictionary in question works like this in the piecewise function class:

public class PiecewiseLinearFunction : ICloneable
{
    ...
    // The dictionary
    public SortedDictionary<Interval, Line2D> Functions { get; set; } = new SortedDictionary<Interval, Line2D>(); // Where Line2D is just a class that contains a function definition for a line

    // Methods
    public Interval FindInterval(double x)
        => Functions.Keys.Where(interval => interval.Contains(x)).FirstOrDefault();
    public double Solve(double x)
    {
        var interval = FindInterval(x);
        if (interval != null && Functions.ContainsKey(interval))
        {
            return Functions[interval].Solve(x);
        }
        else
        {
            return double.NaN;
        }
    }
}

如您所见， PiecewiseLinearFunction.FindInterval（double x）方法线性搜索字典的键，以查找包含（或不包含） x ，它可以用于二进制查找，但是显然完全违背了进行二进制查找的目的。

So as you can see, the PiecewiseLinearFunction.FindInterval(double x) method linearly searches through the dictionary's keys in order to find the interval that contains (or doesn't contain) x, which can be used for binary look-up, but that obviously defeats the purpose of doing the binary look-up at all.

我想知道是否可以通过某种方式进行字典会查找 double x 值，并在间隔上进行二进制搜索，同时检查 Interval.Contains（double x）为 true 或 false 是要确定是否存在有效的间隔（键）和相应的行，用来获取 x 处的函数值。

I was wondering if I could somehow make the dictionary look up the double x value instead, and do a binary search over the intervals while checking if Interval.Contains(double x) is true or false to decide if there is a valid interval (key) and a corresponding line that can be used to get the function value at x.

换句话说，是否可以使用谓词进行搜索，例如 FindInterval（double x）=> Functions.Keys.FindBinary（i => i.Contains（x））。

In other words, is there a way to search with a predicate, something like FindInterval(double x) => Functions.Keys.FindBinary(i => i.Contains(x)).

推荐答案

因此，如果间隔不重叠，则实际上实际上不需要自定义二进制搜索。

So if the intervals don't overlap there is actually not really a need for a custom binary search.

首先，如果我们使 Interval 相当于 double ：

First of all it helps if we make Interval comparable to double:

public class Interval: IComparable<double>
{
    public double Start { get; set; }
    public double End { get; set; }

    public bool Contains(double x) => x >= Start && x <= End;
    public int CompareTo(double other)
    {
        if (Contains(other))
            return 0;
        return other < Start ? 1 : -1;
    }
}

现在我们创建一个 List 扩展名，因此我们能够使用其他类型（而不仅仅是列表类型）进行二进制搜索：

Now we create a List extension so we're able to do binary search with other types then just the type of the list:

public static class ListExtensions
{
    public static int BinarySearch<T, TU>(this List<T> sortedSource, TU val) where T : IComparable<TU>
    {
        return sortedSource.BinarySearch(default(T), Comparer<T>.Create((item, _) => item.CompareTo(val)));
    }
}

现在我们可以像这样测试它了：

And now we can test it like this:

var list = new List<Interval>
{
    new Interval
    {
        Start = 0,
        End = 4
    },
    new Interval
    {
        Start = 6,
        End = 7
    },
    new Interval
    {
        Start = 10,
        End = 12
    }
};

var index = list.BinarySearch(6.0d); //index = 1
var interval = index < 0 ? null : list[index]; //interval = [6, 7]

index = list.BinarySearch(9.0d); //index = -3
interval = index < 0 ? null : list[index]; //interval = null

这篇关于排序字典自定义关键字查找以提高效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！