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

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

  •  
  •   Elethom ·
    Elethom · 2019-01-13 16:46:42 +08:00 · 13385 次点击
    这是一个创建于 2174 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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 条附言  ·  2019-01-13 18:28:38 +08:00

    试了一下用 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
    xiri
        1
    xiri  
       2019-01-13 16:51:20 +08:00 via Android
    leetcode 的那个运行时长统计一点也不准确。
    你把你的答案重新提交几次,会发现每次的运行时长都会有很大的差别
    Elethom
        2
    Elethom  
    OP
       2019-01-13 16:57:00 +08:00
    @xiri
    试着稍微修改过重新提交,几次都耗时很长。前面做的几道题都是 faster than 99% 的,这个应该是我自己的问题。
    lihongming
        3
    lihongming  
       2019-01-13 16:59:01 +08:00 via iPhone
    直接 copy 前面的代码试试,有可能也很慢。因为 testcase 变了
    Elethom
        4
    Elethom  
    OP
       2019-01-13 17:01:08 +08:00
    @lihongming
    我用的 Swift ……感觉这个真的是我自己的问题。

    目前有两个猜测,一个是 Dictionary 的效率问题,一个是从 String 截取 Character 的效率问题。不过还没想到替代方案。
    SingeeKing
        5
    SingeeKing  
       2019-01-13 17:36:52 +08:00
    这个时间。。同一语言同一代码相同 testcases 连续提交两次都不一定一样…… 还是别跨语言比较了
    Elethom
        6
    Elethom  
    OP
       2019-01-13 17:43:46 +08:00 via iPhone
    @SingeeKing
    LeetCode 的运行效率是按同语言计算百分比的。
    flicker317
        7
    flicker317  
       2019-01-13 18:03:08 +08:00 via iPhone
    目测问题出在 swift 操作字符串上 话说上一次看文档还是 2.0 不知道 api 又变成什么样了
    Elethom
        8
    Elethom  
    OP
       2019-01-13 18:19:10 +08:00
    @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.
    KylinRoc
        9
    KylinRoc  
       2019-01-13 18:23:42 +08:00
    可以开始这样一下:

    ```swift
    let characters: [Character] = Array(string)
    ```
    Elethom
        10
    Elethom  
    OP
       2019-01-13 18:32:04 +08:00
    @KylinRoc
    谢谢,试了下速度和上面的解法差不多。可能剩下那 15% 更快的解法是默认了字符限定在 ASCII 内。
    KgM4gLtF0shViDH3
        11
    KgM4gLtF0shViDH3  
       2019-01-14 06:52:31 +08:00 via iPhone
    前两天刷的时候已经没有超过百分之多少人的显示了啊,现在又回来了?
    wezzard
        12
    wezzard  
       2019-03-07 15:38:28 +08:00 via iPhone   ❤️ 1
    Swift String 每次進行索引操作時都會臨時探測 grapheme break,改用 Objective-C 字符串應該就好了。字典預分配一下速度也可以更快。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1053 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 20:01 · PVG 04:01 · LAX 12:01 · JFK 15:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.