首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  LeetCode

[ Swift ] LeetCode 一道题,同样的逻辑用 Swift 写出来运行就超慢,请问性能问题出在哪里?

  •  
  •   Elethom · 247 天前 · 8712 次点击
    这是一个创建于 247 天前的主题,其中的信息可能已经有所发展或是发生改变。

    https://leetcode.com/problems/longest-substring-without-repeating-characters/

    刚注册 LeetCode 账号准备补习一下算法。我用 Swift 写了一个自认为效率应该还可以的解,提交之后发现仅比 6% 的答案快。结果翻了一下推荐的最优 solution,逻辑和我写的是完全一样的,不知道性能瓶颈在哪里。求解答,谢谢。

    我自己写的( Swift ):

    class Solution {
        func lengthOfLongestSubstring(_ s: String) -> Int {
            var result = 0
            var map: [Character:Int] = [:]
            var start = 0
            for i in 0 ..< s.count {
                let c = s[s.index(s.startIndex, offsetBy: i)]
                if let last = map[c] {
                    start = max(start, last + 1)
                }
                result = max(result, i - start + 1)
                map[c] = i
            }
            return result
        }
    }
    

    LeetCode 推荐的( Java ):

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int n = s.length(), ans = 0;
            Map<Character, Integer> map = new HashMap<>(); // current index of character
            // try to extend the range [i, j]
            for (int j = 0, i = 0; j < n; j++) {
                if (map.containsKey(s.charAt(j))) {
                    i = Math.max(map.get(s.charAt(j)), i);
                }
                ans = Math.max(ans, j - i + 1);
                map.put(s.charAt(j), j + 1);
            }
            return ans;
        }
    }
    
    第 1 条附言  ·  247 天前

    试了一下用 unichar,把用了 subscript 部分换成了 (s as NSString).character(at: i),结果:

    Runtime: 48 ms, faster than 84.82% of Swift online submissions for Longest Substring Without Repeating Characters.

    12 回复  |  直到 2019-03-07 15:38:28 +08:00
        1
    xiri   247 天前 via Android
    leetcode 的那个运行时长统计一点也不准确。
    你把你的答案重新提交几次,会发现每次的运行时长都会有很大的差别
        2
    Elethom   247 天前
    @xiri
    试着稍微修改过重新提交,几次都耗时很长。前面做的几道题都是 faster than 99% 的,这个应该是我自己的问题。
        3
    lihongming   247 天前 via iPhone
    直接 copy 前面的代码试试,有可能也很慢。因为 testcase 变了
        4
    Elethom   247 天前
    @lihongming
    我用的 Swift ……感觉这个真的是我自己的问题。

    目前有两个猜测,一个是 Dictionary 的效率问题,一个是从 String 截取 Character 的效率问题。不过还没想到替代方案。
        5
    SingeeKing   247 天前
    这个时间。。同一语言同一代码相同 testcases 连续提交两次都不一定一样…… 还是别跨语言比较了
        6
    Elethom   247 天前 via iPhone
    @SingeeKing
    LeetCode 的运行效率是按同语言计算百分比的。
        7
    flicker317   247 天前 via iPhone
    目测问题出在 swift 操作字符串上 话说上一次看文档还是 2.0 不知道 api 又变成什么样了
        8
    Elethom   247 天前
    @flicker317
    谢谢。试了一下用 unichar,把用了 subscript 部分换成了 (s as NSString).character(at: i),结果:
    Runtime: 48 ms, faster than 84.82% of Swift online submissions for Longest Substring Without Repeating Characters.
        9
    KylinRoc   247 天前
    可以开始这样一下:

    ```swift
    let characters: [Character] = Array(string)
    ```
        10
    Elethom   247 天前
    @KylinRoc
    谢谢,试了下速度和上面的解法差不多。可能剩下那 15% 更快的解法是默认了字符限定在 ASCII 内。
        11
    bestkayle   246 天前 via iPhone
    前两天刷的时候已经没有超过百分之多少人的显示了啊,现在又回来了?
        12
    wezzard   194 天前 via iPhone   ♥ 1
    Swift String 每次進行索引操作時都會臨時探測 grapheme break,改用 Objective-C 字符串應該就好了。字典預分配一下速度也可以更快。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2911 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 24ms · UTC 10:47 · PVG 18:47 · LAX 03:47 · JFK 06:47
    ♥ Do have faith in what you're doing.