xml - 以下基于 Swift 的 XML 解析器的瓶颈是什么？

Question

我写了一个简单的 xml 解析器。但是性能很糟糕。我无法弄清楚问题是什么以及我的代码在 macOS Sierra 上由 Swift 3.1 编译的瓶颈在哪里。当我在一些 XML 文件(大约有 43000 个字符)上测试代码时，解析该文件需要大约 4.5 分钟!这是我的源代码:

class Parser {

let ignorableChars : [String] = [" ", "\"", "=", "\r", "\n", "\t"]

var i : Int
var xmlString : String
var stack : [Element]

init(xmlString: String) {
    self.i = 0
    self.xmlString = xmlString
    self.stack = [Element]()
}

func ignoreProlog() -> Void {
    while self.xmlString[self.i] != "<" {
        self.i += 1
    }
    self.i += 1

    if self.xmlString[self.i] == "?" {
        self.i += 1
        while self.xmlString[self.i] == "?" && self.xmlString[self.i + 1] == ">" {
            self.i += 1
        }
        self.i += 2
    }
    else {
        self.i -= 1
    }

}

func ignoreMiscChars() -> Void {
    while self.ignorableChars.contains(self.xmlString[self.i]) {
        self.i += 1
    }
}

func extractType() -> String {
    var elementType : String = ""

    while self.ignorableChars.contains(self.xmlString[self.i]) == false && self.xmlString[self.i] != ">" {
        elementType.append(self.xmlString[self.i])
        self.i += 1
    }
    return elementType
}

func extractKey() -> String {
    var attrKey : String = ""

    while self.ignorableChars.contains(self.xmlString[self.i]) == false && self.xmlString[self.i] != "/" && self.xmlString[self.i] != ">" {
        attrKey.append(self.xmlString[self.i])
        self.i += 1
    }
    return attrKey
}

func extractValue() -> String {
    var attrValue : String = ""

    while self.xmlString[self.i] != "\"" {
        attrValue.append(self.xmlString[self.i])
        self.i += 1
    }
    self.i += 1
    return attrValue
}

func extractElement() -> (Element?, String?) {
    while self.xmlString[self.i] != "<" {
        self.i += 1
    }
    self.i += 1

    if self.xmlString[self.i] == "/" {
        self.i += 1
        let elementType = self.extractType()
        return (nil, elementType)
    }

    self.ignoreMiscChars()
    let elementType = self.extractType()

    var attributes = [String:String]()
    while self.xmlString[self.i] != ">" &&  self.xmlString[self.i] != "/"{
        self.ignoreMiscChars()
        let key = self.extractKey()
        if key == "" {
            break
        }
        self.ignoreMiscChars()
        let value = self.extractValue()
        attributes[key] = value
    }

    let element = Element(type: elementType)
    element.attributes = attributes

    if self.xmlString[self.i] == "/" {
        element.isCompleted = true
    }

    return (element, nil)
}

public func xmlParser() -> Element {
    self.ignoreProlog()
    while stack.isEmpty || stack[0].isCompleted == false {
        let element = extractElement()
        if element.0 == nil {
            if element.1 == stack[0].type {
                stack[0].isCompleted = true
                break
            }
            let lastElement = stack.last
            lastElement?.isCompleted = true
            stack.removeLast()
            stack[stack.endIndex - 1].chidren.append(lastElement!)
        }
        else if element.0?.isCompleted == true {
            stack[stack.endIndex - 1].chidren.append(element.0!)
        }
        else {
            stack.append(element.0!)
        }
    }

    let root = stack.last
    stack.removeAll()
    return root!
  }
}

Answer 1

试试这个快速技巧，看看字符串下标(即 self.xmlString[self.i])是否是您的瓶颈:

...
var i: Int
let xmlString: [Character]
var stack: [Element]

init(xmlString: String) {
    self.i = 0
    self.xmlString = Array(xmlString.characters)
    self.stack = [Element]()
}
...

自由索引一个 String 会很快降低你的性能，考虑到所有 Unicode 繁重的操作 happening under the hood .

相反，将 once 转换为 Character 数组，如上面的代码所做的那样，可能会大大提高您的性能。索引数组是一种廉价的 O(1) 操作(即，常数时间)。