Swift 4 字符串索引在处理大字符串时偏移太慢

Question

我正在处理一个 csv 文件，其中最后一列的格式并不总是相同。 每行都有这样的结构:

"Root/Word1","some string","some string","some œ0'fqw[唃#”≠§
\nfw@\tfa0j
"
"Root/Word2","some string","some string","some string"
...

所以 6 列和最后一个可以包含\n。这使得很难按组件拆分。 另一个限制是所有字符串都可以是任何可能的特殊字符。这使得使用正则表达式变得困难。

我决定先用蛮力解决问题。 (是的，我已经看到索引偏移量为 O(n)。但无法提出替代方案。)

static func importData(_ db: DB) {
    let csvString = readDataFromCSV(fileName: "data", fileType: "csv")!

    let totalCharCount = csvString.count
    print("total: \(totalCharCount)")
    for i in 0..<totalCharCount {
        print(i)
        if i+5 >= totalCharCount {
            continue
        }
        let index = csvString.index(csvString.startIndex, offsetBy: i)
        let endIndex = csvString.index(csvString.startIndex, offsetBy:i+5)

        let part = csvString[index ..< endIndex]
        if part == "Root/" {
            let accum = lookInside(i: i, totalCharCount: totalCharCount, csvString: csvString)

            var rows = accum.components(separatedBy: "\",\"")

            if var lastt = rows.last {
                lastt.removeLast()
                lastt.removeLast()
                rows[rows.count-1] = lastt
            }
        }
    }
}

static func lookInside(i:Int, totalCharCount: Int, csvString: String) -> String {
    var accum = ""
    var found = false
    var j = i+5
    while !found {

        if j+5 >= totalCharCount {
            found = true
        }
        let index2 = csvString.index(csvString.startIndex, offsetBy: j)
        let endIndex2 = csvString.index(csvString.startIndex, offsetBy:j+5)

        if csvString[index2 ..< endIndex2] == "Root/" {
            found = true
            accum.removeLast()
        } else {
            accum += String(csvString[index2])
        }
        j += 1
    }

    return accum
}

基本上，我正在遍历整个字符串以寻找模式“Root/”。 找到后，我会从这一刻前进到模式的下一次出现。

问题是 csv 生成一个 200k 个字符长的字符串，当我在模拟器上运行它时它持续了太多时间(~30 分钟)。

所以现在我在这里寻求一些帮助，因为根据 Instruments，所有时间都在 String.index(offset by) 方法中消耗，该方法被调用了太多次。

Answer 1

Shlemiel gets a job as a street painter, painting the dotted lines down the middle of the road. On the first day he takes a can of paint out to the road and finishes 300 yards of the road. “That’s pretty good!” says his boss, “you’re a fast worker!” and pays him a kopeck.

The next day Shlemiel only gets 150 yards done. “Well, that’s not nearly as good as yesterday, but you’re still a fast worker. 150 yards is respectable,” and pays him a kopeck.

The next day Shlemiel paints 30 yards of the road. “Only 30!” shouts his boss. “That’s unacceptable! On the first day you did ten times that much work! What’s going on?”

“I can’t help it,” says Shlemiel. “Every day I get farther and farther away from the paint can!”

引自 Joel on Software

您需要了解字符串的工作原理。糟糕的字符串处理在 2001 年很慢，当时 Joel Spolsky 写了上面的故事。通过适当的 Unicode 处理，事情变得更加昂贵。

您并没有真正遍历字符串。您可以使用 String.startIndex 一次又一次地重新开始。

而是使用返回 String.Index 结果的函数。这是字符串的有效索引。用它来保存你的最后一个位置，然后相对于这个位置工作。如果您在开始时仅使用一次 String.Index，您的代码会更快。