정렬 된 사전은 효율성을 위해 키 조회를 사용자 정의합니다.

Aug 17 2020

최근에 저는 Sorted Dictionary 클래스가 키에 대한 이진 검색을 구현 한다는 사실을 알게되었고이를 이점으로 사용하고 싶었습니다. 내가 만드는 중이라서 구분 간격의 무리를 통해 라인의 컬렉션을 나타냅니다 선형 함수 클래스를.

다음 Interval과 같은 클래스를 정의했습니다 .

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문제의 것은 조각 함수 클래스에서 다음과 같이 작동합니다.

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는 이진 조회에 사용할 수있는 (또는 포함하지 않는) 간격을 찾기 위해 사전의 키를 선형으로 검색 하지만 이진을 수행하는 목적을 분명히 무효화합니다. 전혀 찾아보십시오.

어떻게 든 사전이 double x값을 찾도록 만들고 유효한 간격 (키) Interval.Contains(double x)이 있는지 확인하는 동안 간격에 대해 이진 검색을 수행 true하거나 false가져 오는 데 사용할 수있는 해당 줄이 있는지 궁금합니다. 의 함수 값 x.

즉, .NET과 같은 술어로 검색하는 방법이 있습니까 FindInterval(double x) => Functions.Keys.FindBinary(i => i.Contains(x))?

답변

Knoop Aug 17 2020 at 09:34

따라서 간격이 겹치지 않으면 실제로 사용자 지정 이진 검색이 필요하지 않습니다.

우선 그것은 우리가 만드는 경우 도움 Interval을 비교 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확장 을 생성하여 다른 유형과 목록 유형 만 이진 검색을 수행 할 수 있습니다.

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)));
    }
}

이제 다음과 같이 테스트 할 수 있습니다.

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