Reference type confusing in Go language

Question

I tried to make Trie data structures by Go Language, but somehow it stuck with References problem, Here it is. http://play.golang.org/p/ASSGF5Oe9R

// Package main provides ...
package main

import "fmt"

type RootTrie []Trie

type Trie struct {
    subtrie []Trie
    index   byte
}

func (trie *Trie) Insert(data string) *Trie {
    if data != "" {
        if trie.index == 0 {
            trie.index = data[0]
        }
        if next := trie.containsIndex(data[1:]); next != nil {
            //Problem Point
            fmt.Println(string(data[1]), "found follwing", string(data[0]))
            next.Insert(data[1:])
        } else {
            nt := &Trie{}
            trie.subtrie = append(trie.subtrie, *nt.Insert(data[1:]))
        }
    }

    return trie
}
func (trie *Trie) containsIndex(next string) *Trie {
    if next != "" {
        for _, st := range trie.subtrie {
            if st.index == next[0] {
                return &st
            }
        }
    }
    return nil
}

func main() {
    t := &Trie{}
    t = t.Insert("hanyang")
    fmt.Println("result:", t)
    t = t.Insert("hanyKk")
    fmt.Println("result:", t)
    t.Insert("hanyK")
}

The following problems happen in second "Insert", the where I put, //Problem Point

I made containsIndex method for searching next linked trie, and it searched well actually. But when I updated next property which containsIndex given, its not affected its mother struct trie though.

What I don't understand is I gave it reference type when returning containsIndex, but its still act liked 'value copied', Why does it not affected its mother structure(trie)?

Thanks!

I don't get the -1--there're language nits, but it explains the nature of the problem and there's code you can mess around with. — twotwotwo
– twotwotwo, Commented Dec 30, 2014 at 17:43

wonsky · Accepted Answer · 2014-12-30 08:33:40Z

3

The problem is in method containsIndex. Golang range by default creates copy each element in slice and assigns copy of this value to st (in your example). Usually to preserve reference to element in slice you should use original slice and its index. In you case method containsIndex should look something like this:

func (trie *Trie) containsIndex(next string) *Trie {
    if next != "" {
        for i, st := range trie.subtrie {
            if st.index == next[0] {
                return &trie.subtrie[i]
            }
        }
    }
    return nil
}

answered Dec 30, 2014 at 8:33

wonsky

5032 silver badges7 bronze badges

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

4 Comments

Etienne Bruines Over a year ago

Does this also imply a performance difference when using just indices, instead of values as well?

twotwotwo Over a year ago

@EtienneBruines -- Maybe. It might be it's negligible, or there might be no difference if the compiler recognizes it can optimize the copy away sometimes. If you run into this choice in a performance-critical inner loop, you can always test.

Etienne Bruines Over a year ago

@twotwotwo Thank you for your response. I've ran some benchmarks: in non-complicated cases, there is no performance difference at all. github.com/EtienneBruines/go-range-performance-analysis

tomahawk28 Over a year ago

Thanks, @wonsky. and I found some interesting answers there I examine about address differences link

Collectives™ on Stack Overflow

Reference type confusing in Go language

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related