Go / Drkcore

Goでheapの実装

Tue, 13 Sep 2011 20:47:07 +0919

IntVectorってのはsortのInterfaceを実装しているのでsortはなにも定義しなくても普通にOK

package main

import  (
    "container/vector"
    "sort"
    "fmt"
)

func main() {
    v := new(vector.IntVector)
    v.Push(3)
    v.Push(2)
    v.Push(4)
    v.Push(1)

    sort.Sort(v)
    fmt.Println(v)
}

続いて、heapの実装。godoc container/heapすると

type Interface interface {
    sort.Interface
    Push(x interface{})
    Pop() interface{}
}

となっていて、sortのインターフェースとPush,Popが実装されていればイイ。IntVectorにはPushとPopも実装されているのでOKかなと思ったがこれはだめ。

package main

import  (
    "container/vector"
    "container/heap"
    "fmt"
)

func main() {
    v := new(vector.IntVector)
    heap.Push(v,3)
    heap.Push(v,2)
    heap.Push(v,4)
    heap.Push(v,1)
    fmt.Println(heap.Push(v))
    fmt.Println(heap.Push(v))
    fmt.Println(heap.Push(v))
    fmt.Println(heap.Push(v))
}

これをコンパイルしようとすると

$ 6g myheap.go
myheap.go:11: cannot use v (type *vector.IntVector) as type heap.Interface in function argument:
    *vector.IntVector does not implement heap.Interface (wrong type for Pop method)
        have Pop() int
        want Pop() interface { }

といって怒られる。じゃぁメソッドってオーバーライドできるのかなと。

package main

import  (
    "container/vector"
    "container/heap"
    "fmt"
)

func (v *vector.IntVector) Push (i interface{}) { v.Push(i.(int)) }
func (v *vector.IntVector) Pop ()  interface{}  { return v.Pop() }

func main() {
    v := new(vector.IntVector)
    heap.Push(v,3)
    heap.Push(v,2)
    heap.Push(v,4)
    heap.Push(v,1)
    fmt.Println(heap.Push(v))
    fmt.Println(heap.Push(v))
    fmt.Println(heap.Push(v))
    fmt.Println(heap.Push(v))
}

これをコンパイルしようとすると

$ 6g myheap.go
myheap.go:9: method redeclared: vector.IntVector.Push
    method(p *vector.IntVector)func(x int)
    method(v *vector.IntVector)func(i interface { })

結局構造体を作ってこんな感じにした。

package main

import  (
       "container/vector"
       "container/heap"
       "fmt"
)

type heapq struct {
       hq vector.IntVector
}

func (h *heapq) Len() int          { return h.hq.Len() }
func (h *heapq) Less(i,j int) bool { return  h.hq.Less(i,j) }
func (h *heapq) Swap(i,j int)      { h.hq.Swap(i,j) }
func (h *heapq) Push(i interface{}){ h.hq.Push(i.(int)) }
func (h *heapq) Pop() interface{}  { return h.hq.Pop() }

func main() {
       hq := new(heapq)
       heap.Push(hq,3)
       heap.Push(hq,2)
       heap.Push(hq,4)
       heap.Push(hq,1)
       fmt.Println(heap.Pop(hq))
       fmt.Println(heap.Pop(hq))
       fmt.Println(heap.Pop(hq))
       fmt.Println(heap.Pop(hq))
}

結構面倒くさい。単に面倒くさい方法を選択しているだけなのだろうか？よくわからんです。

godoc便利だ

Mon, 12 Sep 2011 21:17:36 +0919

interfaceの情報出てくる

$ godoc container/Heap

TYPES

type Interface interface {
    sort.Interface
    Push(x interface{})
    Pop() interface{}
}
Any type that implements heap.Interface may be used as a
min-heap with the following invariants (established after
Init has been called):

    !h.Less(j, i) for 0 <= i < h.Len() and j = 2*i+1 or 2*i+2 and j < h.Len()

Heapを使いたい時にはsortのインターフェースにあわせてPushとPopを実装するべしということですね。

Goで個数制限付き部分和問題

Sun, 11 Sep 2011 15:39:27 +0919

プログラミングコンテストチャレンジブック(2-3)

数字の種類と個数が幾つか与えられたときに足し算で任意の数が作れるかという問題。DPで解く

プログラミングコンテストチャレンジブック
秋葉拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )

配列を0以外の数で初期化する方法が分からなかったので、初期化してから全ての要素に-1を放り込むためにループを回したけど、ここはどうするのがいいんだろう。あと本のコード間違ってるよね。dp[0]には0じゃなくてmiを入れないと。

package main

import "fmt"

const MAX_N = 100

func main() {
    n := 3
    a := []int{3,5,8}
    m := []int{3,2,2}
    K := 17
    dp := [MAX_N]int{}
    for i,_ := range(dp) {
        dp[i] = -1
    }

    for i := 0; i<n; i++ {
        dp[0] = m[i]
        for j := 0;j<=K;j++ {
            if dp[j] >= 0 {
                dp[j] = m[i]
            } else if j < a[i] || dp[j - a[i]] <= 0 {
                dp[j] = -1
            } else {
                dp[j] = dp[j - a[i]] - 1
            }
        }
    }
    if dp[K] >= 0 {
        fmt.Println("yes")
    } else {
        fmt.Println("no")
    }
}

Goでナップサック問題

Sun, 11 Sep 2011 09:36:20 +0919

プログラミングコンテストチャレンジブック(2-3)

プログラミングコンテストチャレンジブック
秋葉拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )

Dynamic Programmingで解く

package main

import "fmt"

const MAX_N int = 100
const MAX_W int = 10000

type knapsack struct {
    weight int
    value int
}

func max(i,j int) int{
    if i > j {
        return i
    }
    return j
}

func main() {
    W := 5
    N := 4
    knap := []knapsack{{2,3},{1,2},{3,4},{2,2}}
    dp := [MAX_N][MAX_W]int{}
    for i := 0; i<N; i++ {
        for j :=0; j<=W; j++ {
            if j < knap[i].weight {
                dp[i+1][j] = dp[i][j]
            } else {
                dp[i+1][j] = max(dp[i][j], dp[i][j - knap[i].weight] + knap[i].value)
            }
        }
    }
    fmt.Println(dp[N][W])
}

Best Cow Line (Go)

Sun, 11 Sep 2011 06:42:51 +0919

プログラミングコンテストチャレンジブック(2-2)

プログラミングコンテストチャレンジブック
秋葉拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )

Goにはwhileがないけどforで同じことができる。文字列はbyteの配列のように振る舞うので出力するときにstringで変換しないと数字が出力される。それから配列の参照時に、インクリメント、デクリメントステートメントは使えない、つまりS[a++]という書き方はできない。

package main

import "fmt"

const MAX_N int = 2000

func main() {
    N := 6
    S := "ACDBCB"
    a := 0
    b := N-1

    for a <= b {
        left := false
        for i := 0; a+i < b; i++ {
            if S[a+i] < S[b-i] {
                left = true
                break
            } else if S[a+i] > S[b-i] {
                left = false
                break
            }
        }

        if left {
            fmt.Printf("%s",string(S[a]))
            a++
        } else {
            fmt.Printf("%s",string(S[b]))
            b--
        }
    }
    fmt.Printf("\n")
}

Goで区間スケジューリング問題

Sat, 10 Sep 2011 12:10:58 +0919

プログラミングコンテストチャレンジブック(2-2)

プログラミングコンテストチャレンジブック
秋葉拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )

本ではpairを使ってソートして解いているのだが、Goにはpair型がないっぽいので、擬似的に2要素の配列とそのスライスに名前をつけてsort出来るようにした。

package main

import (
    "fmt"
    "sort"
)

type pair [2]int
type Pi []pair

func (p Pi) Len() int          { return len(p) }
func (p Pi) Less(i,j int) bool { return  p[i][1] < p[j][1] }
func (p Pi) Swap(i,j int)      { p[i],p[j] = p[j],p[i] }

func main() { 
    s := [5]int{1, 2, 4, 6, 8}
    t := [5]int{3, 5, 7, 9, 10}
    itv := make(Pi, 5)
    for i := 0; i<len(s); i++ {
        itv[i] = pair{s[i],t[i]}
    }
    sort.Sort(itv)
    ans := 0
    time := 0
    tasks := []int{}
    for j := 0; j<len(s); j++ {
        if time < itv[j][0] {
            ans++
            time = itv[j][1]
            tasks = append(tasks, j)
        }
    }
    fmt.Printf("%d tasks %v\n", ans,tasks)
}

書いてて、あれ、配列のスライスは辞書順でソートしてくれるかな?と思い、

itv := make([][2]int,5)

に変更してコンパイルしてみたらやはり通らなかった。

schedule.go:22: cannot use itv (type [][2]int) as type sort.Interface in function argument:
    [][2]int does not implement sort.Interface (missing Len method)

ちょっと、スライスの使い方がわかってきたような気がする。

GoでGreedy algorithm

Fri, 09 Sep 2011 20:32:46 +0919

プログラミングコンテストチャレンジブック(2-2)

「できるだけ少ない数の硬貨で支払うには？」というよくある問題。minとかmaxが見当たらなかったので自分で定義した。

package main

import "fmt"

func min(i,j int) int {
       if i < j {
               return i
       }
       return j
}

func main() {
       ans := ""
       A := 620
       coins := [6]int{500,100,50,10,5,1}
       num := [6]int{2,0,3,1,2,3}
       for k, coin := range(coins){
               t := min(A/coin,num[k])
               A -= t * coin
               ans += fmt.Sprintf("%d: %d ",coin,t)
       }
       fmt.Printf("%s\n",ans)
}

まだまだ初級編

プログラミングコンテストチャレンジブック
秋葉拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )

GoでDFS

Thu, 08 Sep 2011 20:16:46 +0919

プログラミングコンテストチャレンジブック2-1のLake Counting

プログラミングコンテストチャレンジブック
秋葉拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )

次のような水たまり(Wで八方向に繋がっている)の数を数える

W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

コード

package main

import "fmt"

const MAX_N = 100
const MAX_M = 100
var N,M int

func makeTable(lake []byte, field *[MAX_N][MAX_M]byte, width,height int) {

    for y := 0; y < height; y++ {
        for x := 0; x < width; x++ {
            field[y][x] = lake[y*width+x]
        }
    }
}

func dfs (field *[MAX_N][MAX_M]byte, x, y int) {
    var nx,ny int
    field[x][y] = '.'
    for dx := -1; dx <= 1; dx++ {
        for dy := -1; dy <= 1; dy++ {
            nx = x + dx
            ny = y + dy
            if 0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'W' {
                dfs(field, nx, ny)
            }
        }
    }
}

func main() {
    N = 10
    M = 12
    res := 0
    field := new([MAX_N][MAX_M]byte)

    lake := []byte("W........WW..WWW.....WWW....WW...WW\
    ..........WW..........W....W......W...W.W.....WW.W.\
    W.W.....W..W.W......W...W.......W.")

    makeTable(lake,field,M,N)

    for i := 0; i<N; i ++ {
        for j :=0; j<M; j++ {
            if field[i][j] == 'W' {
                dfs(field, i, j)
                res++
            }
        }
    }
    fmt.Printf("result: %d\n", res)
}

Goにはpermutationとかあんのかなぁとふと思った。

stackoverflowで参考になった質問(Go)

Thu, 08 Sep 2011 19:41:14 +0919

新しい言語を学ぶときにsofを取りあえずなめとくのはもはや定番だと思うが、goのタグ付いてるのが400問ちょいだったので、全部眺めてみて役だったものをリストアップしてみた。

入門ドキュメント

answerに載ってたドキュメントが面白そう。

GO programming language book or tutorial

文字列関連

文字列の操作は結構はまった。というかいまでもよくわからん部分が多い。取りあえず配列とスライスの違いは理解したが。

プロファイラ

google-perftoolsってのを使えばいいらしい。

Is there a Go profiler?

配列のコピー

コピーはちょっとめんどくさそう

How to copy array into part of another in Go?

インターフェース

ダックタイピングみたいなもん。結構わかりやすい説明だった。

Usage of interface in Go

channelをhaskellでエミュレートするには？

面白そうなんだけどまだちゃんと読んでないというか、channelをきちんと理解してないから後で読む。

How can I emulate Go's channels with Haskell?

Goでフィボナッチのメモ化

Wed, 07 Sep 2011 19:31:22 +0919

Goでつくる簡易Wikiのサンプルは楽しいですね。標準ライブライブラリにhttpやHTML5用のパーサが入っているのはポイント高いですな。あとGAEにも対応したしね。

なかなか楽しいので少し覚えるためにプログラミングコンテストチャレンジブックをGoで書いていくことにしようかなと。

プログラミングコンテストチャレンジブック
秋葉拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )

定番のフィボナッチ（メモ化）

package main

import "fmt"

var memo [100]int

func fib(n int) int {
   if n <= 1 {
       return n
   }
   if memo[n] != 0 {
       return memo[n]
   }
   memo[n] = fib(n-1) + fib(n-2)
   return memo[n]
}

func main() {
   fmt.Println(fib(10))
}

こっちはPythonで

memo = [0]*100

def fib(n):
    if n <= 1:
        return n
    if memo[n] != 0:
        return memo[n]
    else:
        memo[n] = fib(n-1) + fib(n-2)
        return memo[n]

if __name__ == '__main__':
    print fib(10)