为什么Swift中的数组运算性能会变慢？

Question

[当我尝试解决Leetcode 1208中的问题时，我注意到Swift代码比Objective-C慢得多。

这是我在Swift中的代码：

func equalSubstring(_ s: String, _ t: String, _ maxCost: Int) -> Int {
    let list = zip(s,t).map { $0 }
    var costList = [Int].init(repeating: 0, count: list.count)
    for item in list.enumerated() {
        costList[item.offset] = abs(Int(item.element.0.asciiValue!) - Int(item.element.1.asciiValue!))
    }

    var maxLen = 0
    for i in 0..<costList.count {
        var len = 0, cost = maxCost
        for j in i..<costList.count {
            cost -= costList[j]
            if cost >= 0 {
                len += 1
            } else {
                break
            }
        }
        if len > maxLen {
            maxLen = len
        }
    }

    return maxLen
}

[maxCost 93020处理100000长度的输入需要496.363秒。Test case

但是，如果我在Objective-C中使用相同的方法，则只需19s：

- (int)equalSubstring:(NSString *)s t:(NSString *)t maxCost:(int)maxCost {
    NSMutableArray *costList = [[NSMutableArray alloc] init];
    for (int i=0; i<s.length; i++) {
        [costList addObject:@(abs([s characterAtIndex:i] - [t characterAtIndex:i]))];
    }

    int maxLen = 0;
    for (int i=0; i<costList.count; i++) {
        int cost = maxCost, len = 0;
        for (int j=i; j<costList.count; j++) {
            cost -= [costList[j] intValue];
            if (cost >= 0) {
                len += 1;
            } else {
                break;
            }
        }
        if (len > maxLen) {
            maxLen = len;
        }
    }

    return maxLen;
}

使用Javascript会更快：

var equalSubstring = function(s, t, maxCost) {

    var maxLength = 0;
    for (var i=0; i<s.length; i++) {
        var cost = maxCost, len = 0;
        for (var j=i; j<s.length; j++) {
            let c = Math.abs(s.charCodeAt(j) - t.charCodeAt(j));
            cost -= c;
            if (cost >= 0) {
                len += 1;
            } else {
                break;
            }
        }
        if (len > maxLength) {
            maxLength = len;
        }
    }

    return maxLength;
};

可能是为什么Swift这么慢的原因？问题会出在语言本身吗？

Answer 1

这可以通过避免重复累加相同的值来有效解决。找到一个较大的子字符串后，如果您在子字符串中添加一个附加值（如果超过maxCost），则减去该子字符串中第一项的值，然后从startIndex + 1开始该子字符串。

通过这样做，您只需要对字符串进行一次传递。

此功能在Leetcode上以48ms运行：

func equalSubstring(_ s: String, _ t: String, _ maxCost: Int) -> Int {

    let costList = zip(s,t).map { abs(Int($0.0.asciiValue!) - Int($0.1.asciiValue!)) }

    var maxLen = 0
    var cost = 0
    var startIndex = 0

    for i in costList.indices {
        cost += costList[i]
        if cost <= maxCost {
            maxLen = i - startIndex + 1
        } else {
            cost -= costList[startIndex]
            startIndex += 1
        }
    }

    return maxLen
}