存储距离 table

Question

我有一个距离 table，我想将其表示为代码。它存储点之间的距离并具有相同的行和列标题。 table 的右上部分是左下部分的镜像。并且在相同点的交叉点处有空单元格。我应该如何在代码中表示这些，以便我能够 get/set 通过行和列 id 的距离值而不复制这些值？

Answer 1

您可以使用以两个城镇为关键字的字典。
将其包装在 class 中以隐藏实现细节并公开一种方法，您可以在其中以任何顺序检查城镇，这使得字典没有重复项成为可能。

public class Distances
{
    private readonly Dictionary<(string, string), int> _distances;

    public Distances()
    {
        _distances = new Dictionary<(string, string), int>
       {
           { ("Eilat", "Ashkelton"), 307 }
       };
    }

    public int? FindBetween(string town1, string town2)
    {
        if (_distances.TryGetValue((town1, town2), out var distance1))
        {
            return distance1;
        }

        if (_distances.TryGetValue((town2, town1), out var distance2))
        {
            return distance2;
        }

        return null;
    }
}

用法

var distances = new Distances();

var distance = distances.FindBetween("Eilat", "Ashkelton"); // 307

Answer 2

您可以将它们存储在顺序数组中，并从城市组合中提取数组的索引。这在存储方面很棒，但是当需要从城市名称搜索索引时有点慢。进一步优化可以加快速度。

public class DistanceMatrix
{
    // distances are stored in the following sequence. 
    // Example n = 6 cities
    // Array size = n*(n-1)/2 = 15
    // distances = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
    //
    // Represents the following array filled with the
    // index values for `distances`.
    // | -1  0  1  2  3  4 |
    // |  0 -1  5  6  7  8 |
    // |  1  5 -1  9 10 11 |
    // |  2  6  9 -1 12 13 |
    // |  3  7 10 12 -1 14 |
    // |  4  8 11 13 14 -1 |
    //
    float[] distances;

    public DistanceMatrix(params string[] cities)
    {
        this.Cities = cities;
        this.Count = cities.Length;
        this.distances= new float[Count*(Count-1)/2];
    }
    public int Count { get; }
    public string[] Cities { get; }
    int GetCountOfRow(int i) => Count-i-1;
    int GetIndexOfRow(int i) => i*(Count-(i+1)/2);
    int GetIndex(int i, int j)
    {
        if (i==j) return -1;
        if (i>j) return GetIndex(j, i);
        return GetIndexOfRow(i)+j-i-1;
    }

    public float this[int i, int j]
    {
        get
        {
            if (i==j) return 0;
            var index = GetIndex(i, j);
            if (index>=0 && index<distances.Length)
            {
                return distances[index];
            }
            return float.NaN;
        }

        set
        {
            var index = GetIndex(i, j);
            if (index>=0 && index<distances.Length)
            {
                distances[index] =value;
            }
        }
    }
    public float this[string city1, string city2]
    {
        get
        {
            int index1 = Array.IndexOf(Cities, city1);
            int index2 = Array.IndexOf(Cities, city2);
            if (index1==index2) return 0;
            if (index1>=0 && index1<Count
                && index2>=0 && index2<Count)
            {
                return this[index1, index2];
            }
            return float.NaN;
        }
        set
        {
            int index1 = Array.IndexOf(Cities, city1);
            int index2 = Array.IndexOf(Cities, city2);
            if (index1>=0 && index1<Count
                && index2>=0 && index2<Count
                && index1!=index2)
            {
                this[index1, index2] = value;
            }
        }
    }
}
class Program
{
    static void Main(string[] args)
    {
        var dist = new DistanceMatrix(
            "Eilat",
            "Jerusalem",
            "Tel-Aviv");

        dist[0, 1] = 307f;
        dist[0, 2] = 354f;
        dist[1, 2] = 59f;

        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                Console.WriteLine($"Distance from {dist.Cities[i]} to {dist.Cities[j]} is {dist[i, j]} km");
            }
        }
    }
}

与输出

Distance from Eilat to Eilat is 0 km
Distance from Eilat to Jerusalem is 307 km
Distance from Eilat to Tel-Aviv is 354 km
Distance from Jerusalem to Eilat is 307 km
Distance from Jerusalem to Jerusalem is 0 km
Distance from Jerusalem to Tel-Aviv is 59 km
Distance from Tel-Aviv to Eilat is 354 km
Distance from Tel-Aviv to Jerusalem is 59 km
Distance from Tel-Aviv to Tel-Aviv is 0 km

存储距离 table

Store distance table

c#

arrays

store