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/

Community · Accepted Answer · 2017-05-23 11:53:46Z

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, 2017 at 11:53

CommunityBot

11 silver badge

answered Jan 5, 2017 at 7:06

John S Perayil

6,3751 gold badge34 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

kostix Over a year ago

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.

Yandry Pozo · Accepted Answer · 2017-01-05 21:13:23Z

1

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
}

edited Jan 5, 2017 at 21:13

answered Jan 5, 2017 at 7:47

Yandry Pozo

5,1333 gold badges27 silver badges28 bronze badges

Comments

Roland Illig · Accepted Answer · 2017-01-05 07:59:20Z

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 5, 2017 at 7:59

Roland Illig

41.9k12 gold badges91 silver badges127 bronze badges

2 Comments

kostix Over a year ago

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 Over a year ago

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 and articles it links to.

Collectives™ on Stack Overflow

Poor performance converting python code to Go

3 Answers 3

1 Comment

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related