我有来自 API 的评论，这些评论要么是根评论，要么是子评论。这些评论来自该 API，是无序的，我必须在我这边对它们进行排序。
评论如下所示:
struct Comment: Codable, Equatable {
var depth = 0
var id: Int = 0
var parent: Int?
var content: String = ""
var created: Int = 0
var up: Int = 0
var down: Int = 0
var confidence: Double = 0
var name: String = ""
var mark: Int = 0
enum CodingKeys: String, CodingKey {
case id = "id"
case parent = "parent"
case content = "content"
case created = "created"
case up = "up"
case down = "down"
case confidence = "confidence"
case name = "name"
case mark = "mark"
}
init(from decoder: Decoder) throws {
let values = try decoder.container(keyedBy: CodingKeys.self)
id = try values.decode(Int.self, forKey: .id)
parent = try values.decodeIfPresent(Int.self, forKey: .parent)
content = try values.decode(String.self, forKey: .content)
created = try values.decode(Int.self, forKey: .created)
up = try values.decode(Int.self, forKey: .up)
down = try values.decode(Int.self, forKey: .down)
confidence = try values.decode(Double.self, forKey: .confidence)
name = try values.decode(String.self, forKey: .name)
mark = try values.decode(Int.self, forKey: .mark)
}
init(with message: String, name: String, depth: Int) {
self.depth = depth
self.up = 1
self.content = message
self.name = name
}
}
所以我开始制作一个树结构，并将这些注释放入节点中:
fileprivate class Node<T> {
var value: T
weak var parent: Node?
var children: [Node] = []
init(value: T) {
self.value = value
}
func add(child: Node) {
children.append(child)
child.parent = self
}
}
extension Node where T == Comment {
func search(id: Int) -> Node? {
if id == self.value.id {
return self
}
for child in children {
if let found = child.search(id: id) {
return found
}
}
return nil
}
var description: String {
"Id: \(value.id), parent: \(value.parent ?? -1)"
}
}
extension Node where T: Equatable {
func search(value: T) -> Node? {
if value == self.value {
return self
}
for child in children {
if let found = child.search(value: value) {
return found
}
}
return nil
}
}
因此传入的评论被分成两组，如下所示:
private func split(_ comments: [Comment]) {
let parentNodes = comments.filter { $0.parent == 0 }.map { Node(value: $0) }
let childNodes = comments.filter { $0.parent != 0 }.map { Node(value: $0) }
self.sortComments(parentNodes: parentNodes, childNodes: childNodes)
}
然后我用这个递归函数对它们的评论进行排序:
private func sortComments(parentNodes: [Node<Comment>], childNodes: [Node<Comment>]) {
let parentNodes = parentNodes
var childNodes = childNodes
if let firstChild = childNodes.first {
let parentId = firstChild.value.parent!
if let parentNode = parentNodes.first(where: { $0.value.id == parentId }) {
firstChild.value.depth = parentNode.value.depth + 1
parentNode.add(child: firstChild)
childNodes.removeFirst()
self.sortComments(parentNodes: parentNodes, childNodes: childNodes)
} else {
//Comment is child of child
//Search children for parent
//Search also parentNodes, they may have a child already that is the parent
//of the current child we are looking at
parentNodes.forEach {
if let foundNode = $0.search(id: parentId) {
firstChild.value.depth = foundNode.value.depth + 1
foundNode.add(child: firstChild)
childNodes.removeFirst()
self.sortComments(parentNodes: parentNodes, childNodes: childNodes)
}
}
childNodes.forEach {
if let foundNode = $0.search(id: parentId) {
firstChild.value.depth = foundNode.value.depth + 1
foundNode.add(child: firstChild)
childNodes.removeFirst()
self.sortComments(parentNodes: parentNodes, childNodes: childNodes)
}
}
}
} else {
let sortedNodes = parentNodes.sorted { $0.value.confidence > $1.value.confidence }
self.convertCommentNodesToArray(nodes: sortedNodes, currentArray: [])
}
}
最后我将节点转换为数组，以便我的 TableView 可以显示数据:
private func convertCommentNodesToArray(nodes: [Node<Comment>], currentArray: [Comment]) {
var nodes = nodes
var commentsArray = currentArray
if let firstNode = nodes.first {
commentsArray.append(firstNode.value)
if firstNode.children.count > 0 {
let remainingNodes = nodes.dropFirst()
let sortedChildren = firstNode.children.sorted { $0.value.confidence > $1.value.confidence }
convertCommentNodesToArray(nodes: sortedChildren + remainingNodes, currentArray: commentsArray)
} else {
nodes.removeFirst()
convertCommentNodesToArray(nodes: nodes, currentArray: commentsArray)
}
} else {
self.comments.value = commentsArray
}
}
这段代码在有相当多的注释的情况下工作得很好。但在某些时候，当我面对数千条评论时，该函数会因 stackoverflow 崩溃而崩溃。
所以我的问题是:如何使这个函数的性能更好，以免崩溃？我很高兴听到您的建议:)
最佳答案
最后一个函数中有几个点可以针对 Stack Overflow 崩溃进行一些优化:
迭代算法与递归算法
在提及内存优化之前，先看看这两种算法:
- 迭代方法可能看起来更丑陋且难以阅读，但它对内存大小几乎没有限制(基本上，您拥有设备提供的内存量)。
- 相反，递归方法通常更干净，但受到堆栈大小的限制(堆栈大小始终比整个内存大小小得多)。
在深入研究令人惊奇的递归方法之前，您应该真正注意要处理的输入的大小。如果它要处理超过数千个周期，那么您确实应该坚持使用迭代方法。
尽管您可能使用了各种内存优化，但如果您调用递归函数太多次，就会出现堆栈溢出。所以这是首先要考虑的一点。
值类型与引用类型
但是循环数量并不是唯一可能导致堆栈溢出的因素。如果您在堆栈中放入太多变量，也可能会发生这种情况。如果您考虑一下什么存储在哪里，这个问题就可以解决。
值类型总是在栈中分配，而引用类型通常在堆中分配。 (由于Stack Promotion，这并不总是正确的，但我想您现在可以忽略它)。
因此，对于初学者来说，您可以考虑将 Comment 结构实现为一个类。
或者至少您可以尝试通过将其分配回(再次)进入堆栈的另一个局部变量来避免在每个周期重复整个数组。
var commentsArray = currentArray
例如，使用上面的行，您不仅复制了数组(这是一个 valueType)，而且还复制了数组中的每一条注释(因为 Comments 是值类型)。并且您在每个周期上复制它们，使堆栈的大小呈指数级增长。
为了避免重复注释，您可以简单地使用类(这样您只会重复它们的引用)，但如果您也想避免重复数组，您可以直接传递它作为输入输出参数。
对于节点数组也可以这样说(但至少 Node 是一个类)。
最后，这是我在您的情况下会做的事情(但上述所有内容可能适用于其他情况):
- 将 Comment 作为一个类
- 使用迭代算法(甚至不需要传递数组，因此无需担心 inout 参数)
在您的情况下，迭代算法的最简单实现如下:
private func convertCommentNodesToArray(nodes: [Node<Comment>]) {
var nodes = nodes
var commentsArray = [Comment]()
while(!nodes.isEmpty) {
// get the first node
// insert all children of that node to the nodes array in the position you prefer
// then take that node comment and add it to the array
// finally remove that node from the array
}
self.comments.value = commentsArray
}
关于ios - 当使用大量输入调用时，Swift 中的递归函数会崩溃，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/61963061/