Poor performance converting python code to Go

Question

I'm trying to learn the basics of Go and started off by converting old exercises written for Codility in Python over. The code below had a worst-case execution speed of about a quarter second for large strings. When I converted it to Go however, it failed the Codility performance tests for large strings and executed in over 6 seconds.

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

Go implementation

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 
    }
}

Can anyone share some insight on how I can properly implement this in Go?

This is the question I'm trying to answer https://codility.com/programmers/lessons/7-stacks_and_queues/nesting/

score 1 · Accepted Answer · edited May 23 '17 at 11:53

1

Working directly with the []byte will improve your performance drastically.

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
    }
}

As mentioned in Yandry Pozo's answer.

You can make it faster by dropping the append to stack and use a counter instead.

Ref 1
Ref 2

edited May 23 '17 at 11:53

Community

1
1

answered Jan 05 '17 at 07:06

John S Perayil

6,001
1
32
47

3

You can directly use the literals `'('` and `')'` instead of the variables `open` and `close`: for they would be untyped Go constants, upon comparing them with the values of type `byte`, they would get the real type `byte`, and since their rune values fall in range `[0..127]` that would work just OK. – kostix Jan 05 '17 at 07:24

Yandry Pozo · Answer 2 · 2017-01-05T21:13:23.380

You can iterate over a string using range, keep in mind that you'll get a rune. You can save time avoiding append() using just a simple counter. Other consideration your algorithm can be even faster if you return early when you find a ')' and the stack is empty:

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
}

score 0 · Answer 3 · answered Jan 05 '17 at 07:59

0

The slow part of the code is this line:

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

To iterate over the bytes of a string:

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

To iterate over the code points of a string:

for i, c := range s {}

So just use the two-variable for loop.

answered Jan 05 '17 at 07:59

Roland Illig

40,703
10
88
121

1

BTW, at least with refernce Go 1.7 implementation, the byte slice in `for i, b := range []byte(s) {}` will be created over the actual bytes of the source string--no copying of the data will be involved. – kostix Jan 05 '17 at 08:04
1

To the OP: so, I'd use direct `range []byte(s)` combined with the accepted answer or the @yandry-pozo's one. To recap, the chief difference compared to Python here is in the way strings are represented and interpreted. Be sure to read [this article](https://blog.golang.org/strings) and articles it links to. – kostix Jan 05 '17 at 08:08

Poor performance converting python code to Go

3 Answers3