

お気楽goプログラミングというサイト  
<http://www.geocities.jp/m_hiroi/golang/puzgo01.html>  
で幅優先探索を学んでいましたが、  
makePathを使うところでappendと使うと  
[0 2 4 6]を２回出力します。  
プリントデバッグしたところ何度か同じものをキューに入れていますが  
どうしてそのような動きをしているのかわかりません  
appendでスライスに元となる配列部分を超えたところに代入をしようとすると元の配列をコピーした別の配列を作りその配列を参照しようとしているのだと思っていましたがそこが間違いではないかと思います。  
元となるものではどうしてmakePathを定義したのか、私のプログラムはなぜ失敗したのか教えてください。  
コードは  
<https://play.golang.org/p/8s1-bf7qFd>  
に置きました。


CC BY-SA 3.0
2015-03-09T15:40:46.760
7671
2015-05-10T00:52:43.697
2015-03-09T23:59:10.730
8198
8198
question
アルゴリズム go
Goで幅優先探索をしてみようとして不思議な挙動に出会う


`append`したときにコピーが返されるのは配列のキャパシティが不足したときです。

[code]

    package main
    
    import "fmt"
    
    func main() {
        a := []int{1,2,3,4}
    
        fmt.Println(cap(a))           // => 4
        fmt.Println(cap(a[:3]))       // => 4
    
        fmt.Println(append(a[:3], 5)) // => [1 2 3 5]
        fmt.Println(a)                // => [1 2 3 5]
    
        b := append(a[:4], 5)         // キャパシティ不足
        fmt.Println(append(b[:3], 6)) // => [1 2 3 6]
        fmt.Println(a)                // => [1 2 3 5]
    }
    
[/code]

また、`append`したあとのスライスのサイズとキャパシティが一致するとは限りません。  
以下のコードを実行してみるとキャパシティは8なのでまだコピーなしで`append`できる余裕があります。

[code]

    package main
    
    import "fmt"
    
    func main() {
        a := []int{1,2,3,4}
        b := []int{5,6}
        c := append(a, b...)
        fmt.Println(len(c), cap(c)) // => 6 8
    }
    
[/code]

よって、質問者さんのコードでは`append`したときにスライスがコピーされる保証がありません。

スライスを確実にコピーしたい場合は、空の配列と`append`するという方法があります。  
つまり、`makePath`はもっと短く書くことができます。

[code]

    func makePath(path []int, x int) []int {
        return append(append([]int(nil), path...), x)
    }
    
[/code]


CC BY-SA 3.0
2015-03-10T12:47:28.727
7737
2015-03-10T23:56:34.417
2015-03-10T23:56:34.417
3639
3639
7671
answer