c# - 根据范围数据查找值

Question

什么数据结构或数据类型有利于保存数据范围，并根据该范围内的数据返回一个值？

例如假设我有以下范围

1-10 -> 1  
11-35 -> 2.5  
36-49-> 3.8  
50-60 -> 1.2  
61-80 -> 0.9 

在这种情况下，给定数字41我希望3.8返回的数字（因为 41 介于 36 和 49 之间）。

是否有一种巧妙的方法可以在数据结构中表示此类数据以执行此查找？

Answer 1

一个相对方便且性能非常好的实现是使用SortedList<int, Tuple<int, double>>. 使用每个段的下限作为键，使用上限 + 映射值的元组作为值：

var list = new SortedList<int, Tuple<int, double>>
{
    { 1, Tuple.Create(10, 1.0) },
    { 11, Tuple.Create(35, 2.5) },
};

（当然你可以决定使用更好看的数据结构来声明你的参数，以增强代码的可维护性并在开始工作之前在内部转换为这个）。

由于list.Keys保证已排序，因此在查找值时，您可以对其使用二进制搜索来查找等于或大于输入值的索引：

var index = list.Keys.BinarySearch(value);
if (index < 0 && ~index == 0) {
    // no match, stop processing
}
else if (index < 0) {
    // key not found as is, look at the previous interval
    index = ~index - 1;
}

此时指向index可能包括的唯一范围value，所以剩下的就是测试：

if(x >= list.Keys[index] && x <= list.Values[index].Item1) {
    var result = list.Values[index].Item2;
}
else {
    // no match
}

您不会称其为“干净”，但它非常短且非常快。

Answer 2

您可以使用此代码

钥匙 ：

public class Interval<T> where T : IComparable
{
    public Nullable<T> Start { get; set; }
    public Nullable<T> End { get; set; }

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

    public bool InRange(T value)
    {
        return ((!Start.HasValue || value.CompareTo(Start.Value) > 0) &&
                (!End.HasValue || End.Value.CompareTo(value) > 0));
    }
}

值：十进制

你可以使用这个类型：Dictionary<Interval, decimal>

注意：您可以定义访问方法

Answer 3

我花了一段时间，但我有一个 QuickAndDirty 方法，它假定所有给定值都是有效的并且范围是相邻的，而不使用任何数据结构。还有一个非常具体的数据结构，只有在给定的索引正好在指定的范围内并且可以在运行时扩展时才会返回一些东西。

public abstract class TreeNode
{
    public static double QuickAndDirty(int index)
    {
        double result = 1.0;

        if (index > 10)
            result = 2.5;

        if (index > 35)
            result = 3.8;

        if (index > 49)
            result = 1.2;

        if (index > 60)
            result = 0.9;

        return result;
    }

    public abstract double GetValue(int index);

    public abstract TreeNode AddRange(int begin, int end, double value);

    public static TreeNode MakeTreePart(Tuple<int, int, double>[] ranges)
    {
        return TreeNode.MakeTreePart(ranges, 0, ranges.Length >> 1, ranges.Length - 1);
    }

    private static TreeNode MakeTreePart(Tuple<int, int, double>[] ranges, int min, int index, int max)
    {
        if (index == min || index == max)
            return new Leaf(ranges[index].Item1, ranges[index].Item2, ranges[index].Item3);

        return new SegmentTree(
            ranges[index].Item2 + .5,
            TreeNode.MakeTreePart(ranges, min, index >> 1, index - 1),
            TreeNode.MakeTreePart(ranges, index + 1, index << 1, max));
    }
}

public class SegmentTree : TreeNode
{
    private double pivot;
    private TreeNode left, right;

    public SegmentTree(double pivot, TreeNode left, TreeNode right)
    {
        this.pivot = pivot;
        this.left = left;
        this.right = right;
    }

    public override double GetValue(int index)
    {
        if (index < pivot)
            return left.GetValue(index);
        return right.GetValue(index);
    }

    public override TreeNode AddRange(int begin, int end, double value)
    {
        if (end < pivot)
            this.left = this.left.AddRange(begin, end, value);
        else
            this.right = this.right.AddRange(begin, end, value);
        // Do this to confirm to the interface.
        return this;
    }
}

public class Leaf : TreeNode
{
    private int begin, end;
    private double value;

    public Leaf(int begin, int end, double value)
    {
        this.begin = begin;
        this.end = end;
        this.value = value;
    }

    public override double GetValue(int index)
    {
        if (index >= begin && index <= end)
            return value;
        throw new Exception("index out of range");
    }

    public override TreeNode AddRange(int begin, int end, double value)
    {
        if (this.end < begin)
            return new SegmentTree(((double)this.end + begin) * .5, this, new Leaf(begin, end, value));
        else if (end < this.begin)
            return new SegmentTree(((double)end + this.begin) * .5, new Leaf(begin, end, value), this);
        else throw new Exception("Indexes overlap.");
    }
}
    static void Main()
    {
        TreeNode start = new Leaf(36, 49, 3.8);
        start = start.AddRange(11, 35, 2.5);
        start = start.AddRange(1, 10, 1.0);
        start = start.AddRange(50, 60, 1.2);
        start = start.AddRange(61, 80, 0.9);
        double[] values = new double[70];
        for (int i = 1; i < values.Length; i++)
            values[i] = start.GetValue(i);

        TreeNode array = TreeNode.MakeTreePart(
            new Tuple<int, int, double>[]
            {
                Tuple.Create(1, 10, 1.0),
                Tuple.Create(11, 35, 2.5),
                Tuple.Create(36, 49, 3.8),
                Tuple.Create(50, 60, 1.2),
                Tuple.Create(61, 80, 0.9)
            });

        for (int i = 1; i < values.Length; i++)
            values[i] = start.GetValue(i);
    }