0

我有两节课

class CSparseMatrix:
{
            public int NumberOfDimensions { get; set;}
            public int DefaultNumber { get; set; }
            List<int> dimensionsRanges = new List<int>(); // that's specify dimension of ranges, f.e. {100, 100, 100, 120..}

            List<CSparseCell> cells = new List<CSparseCell>(); // contains only values different from default for this matrix
}
class CSparseCell {
            public int Value { get; set; }
            public List<int> coordinates = new List<int>();
}

问题是：如何循环CSparseMatrix并输出所有范围的值，格式如下：[0, 0, 0, 0] - *value*, [0, 0, 0, 1] - *value*, [0, 0, 0, 2] - *value*, ...[dimensionsRanges[0]-1, dimensionsRanges[1]-1, dimensionsRanges[2]-1, dimensionsRanges[3]-1] - *value*所以通过所有范围并输出所有值（我们可以有任意数量的这种维度）。这意味着在程序中我们必须输出矩阵的所有值，它可以有任意数量的维度和范围可以不同。但是我们不知道这个维数是多少，所以不能使用 n 嵌套循环，实际上我不知道如何迭代所有值的算法或方法List<int> dimensionsRanges

我们从这个“矩阵”中得到具体值的方式是

            public int GetValueFromCell(List<int> coordinate)
            {
                foreach(CSparseCell cell in cells)
                {
                    if(cell.coordinates.All(coordinate.Contains)) {
                        return cell.Value;
                    }
                }
                return DefaultNumber;
            }
4

2 回答 2

1

既然您说您的矩阵很大，请避免CSparseCell通过将Value查找推送到答案计算来返回。

您创建一个方法来返回稀疏矩阵中的所有坐标，使用辅助方法来增加坐标。注意：我将坐标增量方法更改为使用for循环，而不是do更容易理解（？）。

void IncCoord(ref List<int> aCoord) { // ref not needed, just for documentation
    for (var curDim = NumberOfDimensions - 1; curDim >= 0; --curDim) {
        if (aCoord[curDim] == dimensionsRanges[curDim] - 1) // handle carry
            aCoord[curDim] = 0;
        else {
             ++aCoord[curDim];
            break;
        }
   }
}

public IEnumerable<List<int>> AllCoords() {
    var curCellCoord = Enumerable.Repeat(0, NumberOfDimensions).ToList();
    var numCells = dimensionsRanges.Product();
    for (int j1 = 0; j1 < numCells; ++j1) {
        yield return curCellCoord.ToList();
        IncCoord(ref curCellCoord);
    }
}

现在您可以使用此方法获取所有Values 并且您可以根据需要格式化输出。假设t是CSparseMatrix：

var ans = t.AllCoords().Select(c => $"[{c.Join(",")}] - {t.GetValueFromCell(c)}");

使用了几个辅助扩展方法：

public static class IEnumerableExt {
    public static int Product(this IEnumerable<int> src) => src.Aggregate(1, (a,n) => a * n);
}

public static class StringExt {
    public static string Join<T>(this IEnumerable<T> items, string sep) => String.Join(sep, items);
}
于 2020-11-20T01:13:06.403 回答
0

我会提出几个建议。首先将坐标和值联系在一起会使事情复杂化。把这两个分开会好很多。

其次，必须搜索整个数组才能找到单个单元格，这使得效率非常低。您可以从字典中创建一个简单的稀疏矩阵。这根本不是最好的方法，但是由于您给出的未知关键要求，它至少比阵列好。（如果键是 1..n 真的是矩阵吗？）

这是一个例子。首先，我们将坐标设置为自己的类型。

readonly struct SparseCoord : IEquatable<SparseCoord>
{
    public static SparseCoord ToCoordinate(params int[] coords)
    {
        return new SparseCoord(coords);
    }

    public SparseCoord(int[] c)
    {
        this.Coordinate = new int[c?.Length ?? 0];

        if (null != c)
            c.CopyTo(this.Coordinate, 0);
    }

    public int[] Coordinate { get; }

    public bool Equals([AllowNull] SparseCoord other)
    {
        return Enumerable.SequenceEqual(this.Coordinate, other.Coordinate);
    }

    public override bool Equals(object obj)
    {
        if (obj is SparseCoord c)
            return this.Equals(c);

        return false;
    }

    public override int GetHashCode()
    {
        var hash = new HashCode();
        foreach (var i in this.Coordinate)
            hash.Add(i);

        return hash.ToHashCode();
    }

    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();
        sb.Append('(');
        foreach (var i in this.Coordinate)
        {
            sb.Append(i);
            sb.Append(',');
        }
        sb.Length = sb.Length - 1;
        sb.Append(')');
        return sb.ToString();
    }
}

然后我们使用字典作为存储创建一个稀疏矩阵。请注意，这显然是不完整的，因为无法部分或完全清除它，但这只是一个示例。

class SparseMatrix : IEnumerable<KeyValuePair<SparseCoord, int>>
{
    Dictionary<SparseCoord, int> cells = new Dictionary<SparseCoord, int>();

    public int this[SparseCoord coord]
    {
        get
        {
            if (this.cells.TryGetValue(coord, out var ret))
                return ret;
            return 0;
        }
        set
        {
            this.cells[coord] = value;
        }
    }

    public IEnumerator<KeyValuePair<SparseCoord, int>> GetEnumerator()
    {
        return this.cells.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

然后您可以添加值并迭代内容：

    static void Main(string[] _)
    {
        SparseMatrix matrix = new SparseMatrix();

        matrix[SparseCoord.ToCoordinate(1, 2, 3)] = 1;
        matrix[SparseCoord.ToCoordinate(5, 6, 7)] = 2;

        foreach (var value in matrix)
            Console.WriteLine(value);
    }

最后我要重申，如果你的矩阵真的会像你在评论中所说的那样变得“大”，那么你应该花一些时间来研究一些众所周知的稀疏矩阵实现。

于 2020-11-20T14:35:47.400 回答