计算Swift中多维数组的维数

Question

假设我有一些函数，我想使用多维数组（例如张量 class）填充我的数据结构：

class Tensor {
   init<A>(array:A) { /* ... */ }
}

虽然我可以添加 shape 参数，但我更愿意根据数组本身自动计算维度。如果您先验知道维度，那么读取它就很简单了：

let d1 = array.count
let d2 = array[0].count

但是，不太清楚如何为 N 维数组执行此操作。我在想可能有一种方法可以通过扩展数组 class:

extension Int {
   func numberOfDims() -> Int {
      return 0
   }
}

extension Array {
   func numberOfDims() -> Int {
     return 1+Element.self.numberOfDims()
   }
}

不幸的是，这不会（理所当然地）编译，因为 numberOfDims 没有为大多数类型定义。但是，我没有看到任何约束 Element 的方法，因为数组的数组让事情变得复杂。

我希望其他人可能对如何解决这个问题有一些见解（或解释为什么这是不可能的）。

Answer 1

不幸的是，我无法使用 Swift 数组执行此操作，但您可以轻松地将 swift 数组转换为 NSArray。

extension NSArray {
    func numberOfDims() -> Int {
        var count = 0
        if let x = self.firstObject as? NSArray {
            count += x.numberOfDims() + 1
        } else {
            return 1
        }
        return count
    }
}

Answer 2

这个问题问得好极了！

明确一点：我在下面谈论的是使用最外层数组的泛型类型参数计算维数的方法。正如 Tyrelidrel 所示，您可以递归地检查第一个元素的运行时类型——尽管这种方法对 [[[1], 2], 3].

等异构数组给出了无意义的答案

基于类型的调度无法工作

正如您所注意到的，您编写的代码不起作用，因为 numberOfDims 并未为所有类型定义。但是有解决方法吗？这个方向通向某处吗？

不，这是一条死胡同。原因是扩展方法是针对非 class 类型静态分派的，如以下代码片段所示：

extension CollectionType {
  func identify() {
    print("I am a collection of some kind")
  }

  func greetAndIdentify() {
    print("Hello!")
    identify()
  }
}

extension Array {
  func identify() {
    print("I am an array")
  }
}

[1,2,3].identify()         // prints "I am an array"
[1,2,3].greetAndIdentify() // prints "Hello!" and "I am a collection of some kind"

即使 if Swift 允许您扩展 Any（但事实并非如此），Element.self.numberOfDims() 会总是调用numberOfDims()的Any实现，即使Element.self的运行时类型是数组。

这种严重的静态调度限制意味着即使这种看起来很有前途的方法也会失败（它可以编译，但总是 returns 1）：

extension CollectionType {
  var numberOfDims: Int {
    return self.dynamicType.numberOfDims
  }

  static var numberOfDims: Int {
    return 1
  }
}

extension CollectionType where Generator.Element: CollectionType {
  static var numberOfDims: Int {
    return 1 + Generator.Element.numberOfDims
  }
}

[[1],[2],[3]].numberOfDims   // return 1 ... boooo!

同样的约束也适用于函数重载。

型式检查不行

如果有办法让它工作，那就是沿着这些思路，它使用条件而不是基于类型的方法分派来遍历嵌套数组类型：

extension Array {
  var numberOfDims: Int {
    return self.dynamicType.numberOfDims
  }

  static var numberOfDims: Int {
    if let nestedArrayType = Generator.Element.self as? Array.Type {
        return 1 + nestedArrayType.numberOfDims
    } else {
        return 1
    }
  }
}

[[1,2],[2],[3]].numberOfDims

上面的代码编译 - 非常混乱 - 因为 Swift 将 Array.Type 作为 Array<Element>.Type 的快捷方式。这完全挫败了解包的尝试。

有什么解决方法？没有一个。这种方法行不通，因为我们需要说“如果 Element 是某种 Array”，但据我所知，Swift 中没有办法说“array of任何东西，”或“只是 Array 类型，而不考虑 Element。”

无论你在哪里提到 Array 类型，它的泛型类型参数都必须在编译时具体化为具体类型或协议。

作弊可以奏效

那么反思呢？有一种方法。这不是一个好方法，但有一个方法。 Swift的Mirror目前还不足以告诉我们元素类型是什么，但是还有一个反射方法足够强大：将类型转换为字符串。

private let arrayPat = try! NSRegularExpression(pattern: "Array<", options: [])

extension Array {
  var numberOfDims: Int {
    let typeName = "\(self.dynamicType)"
    return arrayPat.numberOfMatchesInString(
        typeName, options: [], range: NSMakeRange(0, typeName.characters.count))
  }
}

可怕、邪恶、脆弱，可能在所有国家/地区都不合法 — 但它有效！

Answer 3

如果您想要获取嵌套数组的深度（Swift 的标准库 技术上 没有为您提供 multi-dimensional数组，仅锯齿状数组）——然后，如所示，您可以使用 'dummy protocol' 和类型转换。

protocol _Array {
    var nestingDepth: Int { get }
}

extension Array : _Array {
    var nestingDepth: Int {
        return 1 + ((first as? _Array)?.nestingDepth ?? 0)
    }
}

let a = [1, 2, 3]
print(a.nestingDepth) // 1

let b = [[1], [2, 3], [4]]
print(b.nestingDepth) // 2

let c = [[[1], [2]], [[3]], [[4], [5]]]
print(c.nestingDepth) // 3

^{（我相信这种方法在您最初发布问题时仍然有效）}

在 Swift 3 中，这也可以在没有虚拟协议的情况下实现，而是通过转换为 [Any]。但是，如链接的问答中所述，这是低效的，因为它需要遍历整个数组才能将每个元素装箱在一个存在的容器中。

另请注意，此实现假定您是在同类嵌套数组上调用它。，它不会给出 [[[1], 2], 3] 的正确答案。

如果需要考虑这一点，您可以编写一个递归方法，该方法将遍历每个嵌套数组并返回嵌套的最小深度。

protocol _Array {
    func _nestingDepth(minimumDepth: Int?, currentDepth: Int) -> Int
}

extension Array : _Array {

    func _nestingDepth(minimumDepth: Int?, currentDepth: Int) -> Int {

        // for an empty array, the minimum depth is the current depth, as we know
        // that _nestingDepth is called where currentDepth <= minimumDepth.
        guard !isEmpty else { return currentDepth }

        var minimumDepth = minimumDepth

        for element in self {

            // if current depth has exceeded minimum depth, then return the minimum.
            // this allows for the short-circuiting of the function.
            if let minimumDepth = minimumDepth, currentDepth >= minimumDepth {
                return minimumDepth
            }

            // if element isn't an array, then return the current depth as the new minimum,
            // given that currentDepth < minimumDepth.
            guard let element = element as? _Array else { return currentDepth }

            // get the new minimum depth from the next nesting,
            // and incrementing the current depth.
            minimumDepth = element._nestingDepth(minimumDepth: minimumDepth,
                                                 currentDepth: currentDepth + 1)
        }

        // the force unwrap is safe, as we know array is non-empty, therefore minimumDepth 
        // has been assigned at least once.
        return minimumDepth!
    }

    var nestingDepth: Int {
        return _nestingDepth(minimumDepth: nil, currentDepth: 1)
    }
}

let a = [1, 2, 3]
print(a.nestingDepth) // 1

let b = [[1], [2], [3]]
print(b.nestingDepth) // 2

let c = [[[1], [2]], [[3]], [[5], [6]]]
print(c.nestingDepth) // 3

let d: [Any] = [ [[1], [2], [[3]] ], [[4]], [5] ]
print(d.nestingDepth) // 2 (the minimum depth is at element [5])

计算Swift中多维数组的维数

Calculate the number of dimensions of a multi-dimensional array in Swift

swift

multidimensional-array

dimensions

基于类型的调度无法工作

型式检查不行

作弊可以奏效