느린 신속한 문자열 성능

나는 Palindrome 파티셔닝 질문을 해결하려고합니다. 질문은 https://leetcode.com/problems/palindrome-partitioning/에 있습니다. 느린 신속한 문자열 성능

는 그리고 나는 해결책을했다 :

func partition(_ s: String) -> [[String]] { 

    var result: [[String]] = [] 

    func dfs(string: String, partiton: [String]) { 

     if string.characters.count == 0 { 
      result.append(partiton) 
      return 
     } 

     for length in 1...string.characters.count { 

      let endIndex = string.index(string.startIndex, offsetBy: length-1) 
      let part = string[string.startIndex...endIndex] 


      if isPalindrome(part) { 
       let leftPart = string[string.index(after: endIndex)..<string.endIndex] 
       print("string: \(string) part: \(part) leftpart: \(leftPart)") 
       dfs(string: leftPart, partiton: partiton + [part]) 
      } 
     } 
    } 

    func isPalindrome(_ s: String) -> Bool { 
     if String(s.characters.reversed()) == s { 
      return true 
     } else { 
      return false 
     } 
    } 

    dfs(string: s, partiton: []) 
    return result 
}

그러나 성능이 나쁜 것입니다. 시간 제한 초과.

그러나 파이썬 구현과 같은 생각을 전달할 수 있습니다

def partition(self, s): 
    res = [] 
    self.dfs(s, [], res) 
    return res 

def dfs(self, s, path, res): 
    if not s: 
     res.append(path) 
     return 
    for i in range(1, len(s)+1): 
     if self.isPal(s[:i]): 
      self.dfs(s[i:], path+[s[:i]], res) 

def isPal(self, s): 
    return s == s[::-1]

그것은 나에게 신속한 구현 및 이유 신속한 구현이 파이썬보다 느린을 개선하는 방법 것이 궁금합니다.

출처

2016-11-02 100mango

기민한 StringCharacter는 S의 집합이고, Character 하나 이상의 유니 스칼라 수있는 단일 확장 된 자모 클러스터를 나타낸다. 따라서 "첫 번째 N 문자 건너 뛰기"와 같은 일부 인덱스 작업이 느려집니다.

하지만 첫 번째 개선은 isPalindrome() 기능을 "단락"하는 것입니다. 대신 완전히 반전 캐릭터 라인을 구축, 그 반대 순서로 문자 시퀀스를 비교하고 즉시 을 중지 차이가 발견 같이

func isPalindrome(_ s: String) -> Bool { 
    return !zip(s.characters, s.characters.reversed()).contains { $0 != $1 } 
}

는 는 s.characters.reversed() 역 위해 새 컬렉션을 만들지 않습니다, 단지 열거

뒤에서 앞으로 문자. 그러나 귀하의 방법으로 String(s.characters.reversed())을 사용하면 역순 된 문자열 인 느리게 만드는 에 대한 새 모음을 만들어야합니다. 110 - 문자열

let string = String(repeating: "Hello world", count: 10)

이 들어

약 6 초 내 시험에서 1.2 초까지의 연산 시간을 감소시킨다.

다음,

let endIndex = string.index(string.startIndex, offsetBy: length-1)

같이 인덱스 계산을 피하고 대신 문자 인덱스 자체를 반복 :

func partition(_ s: String) -> [[String]] { 

    var result: [[String]] = [] 

    func dfs(string: String, partiton: [String]) { 
     if string.isEmpty { 
      result.append(partiton) 
      return 
     } 

     var idx = string.startIndex 
     repeat { 
      string.characters.formIndex(after: &idx) 
      let part = string.substring(to: idx) 
      if isPalindrome(part) { 
       let leftPart = string.substring(from: idx) 
       dfs(string: leftPart, partiton: partiton + [part]) 
      } 
     } while idx != string.endIndex 
    } 

    func isPalindrome(_ s: String) -> Bool { 
     return !zip(s.characters, s.characters.reversed()).contains { $0 != $1 } 
    } 

    dfs(string: s, partiton: []) 
    return result 
}

계산 시간은 이제 0.7 초이다.

다음 단계는 문자열 인덱싱을 완전히 피하고문자 배열로 작업하는 것입니다. 배열 인덱싱이 빠르기 때문입니다. 더 좋은 사용 어레이 슬라이스 만들 빠르며 일본어 배열 요소를 참조 :

func partition(_ s: String) -> [[String]] { 

    var result: [[String]] = [] 

    func dfs(chars: ArraySlice<Character>, partiton: [String]) { 

     if chars.isEmpty { 
      result.append(partiton) 
      return 
     } 

     for length in 1...chars.count { 
      let part = chars.prefix(length) 
      if isPalindrome(part) { 
       let leftPart = chars.dropFirst(length) 
       dfs(chars: leftPart, partiton: partiton + [String(part)]) 
      } 
     } 
    } 

    func isPalindrome(_ c: ArraySlice<Character>) -> Bool { 
     return !zip(c, c.reversed()).contains { $0 != $1 } 
    } 

    dfs(chars: ArraySlice(s.characters), partiton: []) 
    return result 
}

계산 시간이 지금은 0.08 초이다.

문자열에 "기본 다국어 평면"(즉,< = U + FFFF)를 대신 UTF-16 코드 포인트로 작업 할 수 있습니다 :

func partition(_ s: String) -> [[String]] { 

    var result: [[String]] = [] 

    func dfs(chars: ArraySlice<UInt16>, partiton: [String]) { 

     if chars.isEmpty { 
      result.append(partiton) 
      return 
     } 

     for length in 1...chars.count { 
      let part = chars.prefix(length) 
      if isPalindrome(part) { 
       let leftPart = chars.dropFirst(length) 
       part.withUnsafeBufferPointer { 
        dfs(chars: leftPart, partiton: partiton + [String(utf16CodeUnits: $0.baseAddress!, count: length)]) 
       } 
      } 
     } 
    } 

    func isPalindrome(_ c: ArraySlice<UInt16>) -> Bool { 
     return !zip(c, c.reversed()).contains { $0 != $1 } 
    } 

    dfs(chars: ArraySlice(s.utf16), partiton: []) 
    return result 
}

계산 시간이 이제 110 문자 테스트 문자열을 0.04 초이다. 스위프트 문자열로 작업 할 때 잠재적으로 성능을 향상시킬 수 있습니다

그래서 몇 가지 팁을 순차적으로 문자/인덱스를 통해

으로 반복합니다. 을 n 번째 위치로 "점프"하지 마십시오.
모든 문자에 대해 "임의"액세스가 필요한 경우 먼저 문자열을 배열로 변환하십시오.
문자열보기에서 UTF-16보기를 사용하면 문자보기로 을 작업하는 것보다 빠를 수 있습니다.

물론 실제 사용 사례에 따라 다릅니다. 이 응용 프로그램에서 우리는 계산 시간을 6 초에서 0.04 초로 줄일 수있었습니다. 은 150의 요소입니다.

출처

2016-11-10 21:04:12

느린 신속한 문자열 성능

답변

관련 문제