將Python代碼轉換爲Go性能不佳

我在學習Go的基礎知識，並開始轉換爲Python中的Codility編寫的舊練習。下面的代碼對於大型字符串的執行速度最差約爲四分之一秒。但是，當我將它轉換爲Go時，它對大字符串的Codility性能測試失敗並在6秒內執行。將Python代碼轉換爲Go性能不佳

def solution(S): 
    stack = [] 
    for i in S: 
     if len(stack) and stack[-1] == "(" and i == ")": 
      stack.pop() 
      continue 
     stack.append(i) 

    return 1 if len(stack) == 0 else 0

去實現

package solution 

func Solution(S string) int { 
    stack := make([]string, 0) 
    for i := range S { 
     s := string([]rune(S)[i]) 
     ln := len(stack) 
     if ln > 0 && stack[ln-1] == "(" && s == ")" { 
      stack = stack[:ln-1] 
      continue 
     } 
     stack = append(stack, s) 
    } 
    if len(stack) == 0 { 
     return 1 
    } else { 
     return 0 
    } 
}

任何人都可以分享我如何能正確執行這個圍棋一些見解？

這是我想回答 https://codility.com/programmers/lessons/7-stacks_and_queues/nesting/

來源

2017-01-05 user2989731

直接與[]byte合作將大大提高你的表現的問題。

Results

func Solution(S string) int { 

    b := []byte(S) 
    stack := make([]byte, 0) 

    for i, s := range b { 

     ln := len(stack) 
     if ln > 0 && stack[ln-1] == '(' && s == ')' { 
      stack = stack[:ln-1] 
      continue 
     } 
     stack = append(stack, s) 
    } 
    if len(stack) == 0 { 
     return 1 
    } else { 
     return 0 
    } 
}

如Yandry Pozo的答覆中提到。

您可以通過將追加放入堆棧並使用計數器來使速度更快。

Ref 1
Ref 2

來源

2017-01-05 07:06:36

您可以直接使用文字''（'和''）''而不是變量'open'和'close'：因爲它們將是無類型的Go常量，將它們與類型爲'byte '，他們會得到真正的'byte'類型，並且由於它們的符文值落在範圍'[0..127]'中，所以它可以正常工作。 – kostix

可以使用範圍遍歷字符串，請記住，你會得到一個rune。您只需使用一個簡單的計數器就可以節省時間，避免使用append()。其他考慮因素，如果你回到年初，當你發現你的算法能更快一「）」和堆棧是空的：

func Solution(S string) int { 
    stack := make([]rune, len(S)+1) 
    top := 0 // keep track of the stack top 

    for _, r := range S { 
     if r == '(' { // i got a '(' 
      stack[top] = r 
      top++ 
     } else { // i got a ')' 
      top-- 
      if top < 0 { // the stack is emtpy, early return 
       return 0 
      } 
     } 
    } 

    if top == 0 { 
     return 1  
    } 
    return 0 
}

來源

2017-01-05 07:47:07

代碼的緩慢部分是這一行：

s := string([]rune(S)[i])

要通過遍歷字符串的字節數：

for i, b := range []byte(s) {}

要遍歷一個字符串的代碼點：

for i, c := range s {}

所以只需使用雙變量for循環。

來源

2017-01-05 07:59:20

順便說一句，至少在參考Go 1.7實現時，會在源字符串的實際字節上創建'for i，b：= range [] byte（s）{}中的字節片段 - 不復制數據將參與其中。 – kostix

對於OP：所以，我會直接使用'range [] byte（s）'與接受的答案或@ yandry-pozo的結合。總而言之，與Python相比，Python的主要區別在於字符串被表示和解釋。請務必閱讀[本文]（https://blog.golang.org/strings）及其鏈接的文章。 – kostix

將Python代碼轉換爲Go性能不佳

回答

相關問題