oinume journal

Scratchpad of what I learned

GoでLRU Cacheを実装する

LRU Cacheは何かをキャッシュする際によく使うデータ構造の一つだと思う。よく使う一方でその実装はやったことがなかったので、今回Goで実装してみたよ、という話。

LRUCacheとは?

Least Recentry Used Cache のこと。一定のキャパシティを持つもので、キャパシティを超える場合使用された時間がもっとも古い要素から削除される。詳しくはWikipediaを見てもらうと良いと思う。

Goでの実装とその解説

まずは単純に実装してみた。テストも含めると上記の3つのファイルから構成されている。lru_cache.goには以下のようなGetとPutメソッドがinterfaceとして定義されており、その実装がdefault.goにある。

type LRUCache interface {
    // Get returns value for `key`. Returns -1 if not found
    Get(key int) int
    // Put sets value with key
    Put(key, value int)
}

使用例

example_test.go で使用例が書かれており、これを

   cache := lru_cache.NewDefault(2)
    cache.Put(1, 1)
    cache.Put(2, 2)

    fmt.Println(cache.Get(1)) // References key `1`

    cache.Put(3, 3) // This operation evicts key `2`
    // Output:
    // 1
    // -1
    fmt.Println(cache.Get(2))

上のコードにあるように、cache.Put(3, 3) によって一番参照が古いkey 2 がcacheから削除される。結果として、cache.Get(2)は-1を返す。これがLRU Cacheの基本的な動作である。

キャッシュのアイテム

キャッシュするアイテムはmapを使って管理する。この時、「いつ参照されたのか」を判断するために、mapのvalueには以下のようなitem構造体を保存する。

type item struct {
    value int
    age   int
}

なお、item.ageはそのアイテムがGetで参照された時またはPutで追加された時のageとなる。そのため、LRU Cacheの実装をしている defaultLRUCache ではGet/Putが呼ばれるたびにcurrentAgeというフィールドをインクリメントする。

type defaultLRUCache struct {
    capacity   int
    values     map[int]*item
    currentAge int
    mutex      *sync.Mutex
}

Get

Getの実装はシンプルで、以下を行うだけである

  • keyが存在しない場合: -1を返す
  • keyが存在する場合: 参照されたitemのageを更新し、currentAgeをインクリメントしてreturnする
func (c *defaultLRUCache) Get(key int) int {
    i, ok := c.values[key]
    if !ok {
        return -1
    }
    c.mutex.Lock()
    i.age = c.currentAge
    // `Get` also increment current age
    c.currentAge++
    c.mutex.Unlock()
    return i.value
}

Put

Getに比べるとPutはやや複雑である。

  • すでにitemがある場合: mapに存在するitemのageを更新する
  • itemがない場合
    • LRU Cacheのcapacityを超えている場合: mapの中で一番ageが小さいitemを見つけて削除する
    • 上記に加えて、mapにitemをセットする

という操作を行う。またそれぞれの操作で currentAgeをインクリメントする。

func (c *defaultLRUCache) Put(key int, value int) {
    c.mutex.Lock()
    defer c.mutex.Unlock()

    if i, ok := c.values[key]; ok {
        // If the key exists, update its value and increment its age for this key
        i.value = value
        i.age = c.currentAge
        c.currentAge++
    } else {
        if len(c.values) >= c.capacity {
            // Search key with least age when over capacity before setting key and value
            leastAge := math.MaxInt32
            leastAgeKey := 0
            for key, item := range c.values {
                if item.age < leastAge {
                    leastAge = item.age
                    leastAgeKey = key
                }
            }
            if leastAgeKey != 0 {
                // Evict least age key from cache
                delete(c.values, leastAgeKey)
            }
        }
        // Set key and value to cache
        c.values[key] = &item{
            value: value,
            age:   c.currentAge,
        }
        c.currentAge++
    }
}

この実装の問題点

このdefaultLRUCacheの実装には一つ大きな問題がある。というのは、capacityを超えている場合、ループで一番ageが小さいものを探しているため、O(n)のコストがかかる。これについては長くなるので別の記事でまとめようと思う。

まとめ

LRU Cacheのとてもシンプルな実装をやってみた。簡単なので面接の時の課題として出してみるのも面白いかなと思った。

Review on Jan 2020

What I did on Jan 2020

  • Got flu on the beginning of this year...
  • Went to GoDays 2020 in Berlin!
    • Went to Warsaw as a persona trip
  • Work, work, work

Output

Wrote a blog post about GitHub Actions.

Sleep

6 hours 50 min.

  • 1st week: many sleep hours but less deep sleep because of flu
  • 2nd week: OK
  • 3rd week: few sleep hours because of jet lag
  • 4th week: OK

Algorithms and datastructures

No progress...

English

  • Had 4 lessons in DMMEikaiwa
  • Learned new words with iKnow on almost every day
  • English chat lunch once every week
    • This is supported by my company, having a lunch with 4 people. This is very good to listen live English.
  • This blog post!

GitHub ActionsでReleaseが作成されたら次のバージョンのrelease branchを自動的に作る

はじめに

  • 自分のチームではA successful Git branching modelに近い感じで、リリースする前にrelease branchを作りそこにfeature branchをmergeしてからテストしてリリースする、という流れで開発からリリースまでのサイクルを回している。
  • リリースする前に誰かがrelease branchを作成するという作業が手間だったため、GitHub Actionsで自動化できないかと思い、実際やってみたところ意外と簡単にできたので、そこで得られた知識をこの記事にまとめる

実際のコードと説明

それでは実際のactionsのYAMLファイルをもとに細かく説明する。今回使用したYAMLファイルはここにあがっている。

on でフックしたいイベントを定義する

GitHub Actionsを作成すると、.github/workflows/xxx.yml が作成される。まずこのYAMLに定義するべきものがonである。これはワークフローを実行するためのトリガーの定義である。今回の例だと以下のように、releaseがpublish(公開)されたらワークフローを動かすようにしている。

on:
  release:
    types:
      - published

他にも branchにpushされたら、pull-requestが作成されたらなどをトリガーすることができる。詳細は以下の公式ドキュメントで詳しく説明されている。

jobsで実行する処理を定義する

jobsの下に行いたい処理の名前(job_id)を書いて、その下に行いたい処理を記述していく。

  • runs-on: 実行するmachine typeを指定する。指定できるmachine typeについては公式ドキュメントに書いてある
  • stepにはusesrunが定義できる
    • uses: 他のGitHub Actionsを使う
    • run: コマンドをshellで実行する。

jobs:
  build:
    runs-on: ubuntu-latest
    steps:
    - uses: actions/checkout@v2

環境変数のセット

何かしら計算した結果を保存して、次のstepで参照できるようにしたいことがある。そういう場合は環境変数をセットする。

    steps:
    ...
    - name: Create local changes
      run: |
        CURRENT_VERSION=$(echo $GITHUB_REF | sed 's/refs\/tags\///')
        echo "CURRENT_VERSION = $CURRENT_VERSION"
        NEXT_VERSION=$(echo $CURRENT_VERSION | perl -ne 'if ($_ =~ /^(\d+)\.(\d+)\.\d+$/) { $v = $2; $v++; print "$1.$v.0\n" } else { print "Invalid tag format."; exit 1 }')
        echo "NEXT_VERSION = $NEXT_VERSION"
        echo "::set-env name=NEXT_VERSION::$(echo $NEXT_VERSION)"

例えば上記のコードは以下の処理を行っている。

  1. GITHUB_REFにあるタグの値(refs/tags/0.1.0)を取得
  2. そこからバージョン部分を抜き出してCURRENT_VERSIONにセット
  3. perlで次のバージョンにインクリメントしてNEXT_VERSIONにセット
  4. ::set-envを使って環境変数NEXT_VERSIONをセット

構文が気持ち悪いが、set-envを使うことで環境変数をセットすることができ、後続のstepで参照することができる。

secrets

    steps:
    ...
    - name: Create a pull request with a new release branch
      uses: peter-evans/create-pull-request@v2
      with:
        token: ${{ secrets.GITHUB_TOKEN }}
        branch: release/${{ env.NEXT_VERSION }}
        base: master
        title: "Release ${{ env.NEXT_VERSION }}"
        body: "## Pull-requests in this release\n- TBD"

上記のコードはpull-requestを作る例だが、GitHub上のリポジトリに対して何か操作を行う場合はGitHubのTokenが必要になる。そういう場合は secrets に定義されているGITHUB_TOKENを使用する。また、secretsはリポジトリの設定画面から自分で値をセットすることもできるので、秘匿したい文字列などはsecretsを通してstep内で使用するのが良い。

GitHub Actionsの良いところは、デフォルトのsecretsとしてGITHUB_TOKENが定義されていて、GitHubのリポジトリに対して操作を行う場合はTokenのことを気にする必要がないことだと思う。

contexts, expressions, functions

GitHub ActionsのYAMLでは式を書くことができる。例えば以下のコードはpeter-evans/create-pull-request@v2の引数としてbranch: release/${{ env.NEXT_VERSION }} を渡しているが、{{ ... }}の中には式を書くことができる。

    - name: Create a pull request with a new release branch
      uses: peter-evans/create-pull-request@v2
      with:
        token: ${{ secrets.GITHUB_TOKEN }}
        branch: release/${{ env.NEXT_VERSION }}
        base: master
        title: "Release ${{ env.NEXT_VERSION }}"
        body: "## Pull-requests in this release\n- TBD"

また、この式の部分では env のようなあらかじめ定義されているcontextsが使える。他にどのようなcontextsがあるかはドキュメントを読むと良い。

さらに、あらかじめ定義されたfunctionsがあり、expressionの部分で呼び出すことが可能である。

GitHub Actions Marketplace

GitHub Marketplace · Actions to improve your workflow · GitHubを見るとたくさんのActionがあることがわかると思う。他の人が作った汎用的なActionがたくさん転がっているので、これを見ているだけでも「ああこんなこともできるのか」と参考になるし、いろいろ組み合わせて面倒な作業を自動化することができる。

まとめ

エンジニアの業務であるコードを書く、コードレビュー、リリースに関連した作業を自動化するならGitHub Actionsはとてもオススメ。

2020の抱負

新年あけましておめでとうございます。年末年始はインフルエンザになって寝込んでいて、そういえば今年は厄年だったことを思い出しました。もう1/15になってだけど2020年の抱負をあらためて書いておこうと思います。

1日6時間15分以上寝る

昨年は1日6時間以上寝る、ということが目標だったので今年は15分長くしてみる。理想は1日7時間睡眠なので最終的にはこれを目指したい。

アルゴリズムとデータ構造をもっと勉強する

昨年途中で投げ出してしまったヤツ。なお、ちゃんと解説をブログにアウトプットする。

  • Graph
  • オートマトン

アウトプット

1ヶ月に1つはちゃんとした記事を書く。昨年に引き続き継続は力なり、ということで。

英語

IELTS Overall 6.0を目指す。

2019年の振り返り

2019年も早いものであっという間に終わってしまった。以下が2019年初頭に考えていた抱負だったので、これをベースに振り返りをしてみよう。

journal.lampetty.net

アウトプット

ちゃんとした記事を月に一つは書く!というの目標に対しては以下のように未達だったけど、合計25個の記事を書いたし、未達だったのは3月と10月だけだったのでほぼ達成と言って良いのではないかと。

  • 1月: ◯
  • 2月: ◯
  • 3月: ✕
  • 4月: ◯
  • 5月: ◯
  • 6月: ◎
  • 8月: ◯
  • 9月: ◯
  • 10月: ✕
  • 11月: ◯
  • 12月: ◎

また、会社のAdvent Calendarでも以下の記事を書いた。3年半も勤めているのにこれが初めての記事だった...! はてブTwitterでもいろいろフィードバックされているのを見てとても勉強になったし、来年はもっとアウトプットしていこうという気持ちが強くなった。

tech.mercari.com

1日6時間以上寝る

iPhoneのヘルスケアアプリによると各月の平均睡眠時間は以下のような結果だった。2,4,5,9月以外は達成できているし、実感として昨年より良く寝れていて毎日のパフォーマンスも上がっている気がする。

  • 1月: データなし
  • 2月: 5h11min
  • 3月: 6h2min
  • 4月: 5h56min
  • 5月: 5h56min
  • 6月: 6h20min
  • 7月: 6h25min
  • 8月: 6h10min
  • 9月: 5h59min
  • 10月: 6h27min
  • 11月: 6h19min
  • 12月: 6h13min

アルゴリズムもっと勉強する

以下のような結果だった。Graphは中途半端なところで終わっているので再開したい。

暗号技術を勉強する

これはまったくやる暇がなかったのと、特に何かで必要なものではないので、目標設定をミスったかなという気がしている。

業務で必要なものを身につける

  • gRPC: ☓
  • Cloud Spanner: △
  • Cloud PubSub: ◯
  • SQLを復習する: ☓

これはそれぞれの項目でどこまでやるというゴールをちゃんと決めたほうが良かった。

英語を再開する

いつかは海外で働きたいと思っていて、自分の英語力をどう伸ばすかはずっと課題だったのでまずはIELTSを受けてみた。結果としては Overall: 5.0 であり「6.0ぐらいはあるかなー」という予想を大きく下回っていた。でも自分の実力がわかったし、これまでやってきたDMM英会話ベースでデイリーニュースを読むみたいな学習法だと英語力は伸びないということがわかったので、来年からは違う方法(カランメソッド)でやっていこうと思う。

  • Overall: 5.0
  • Listening: 5.5
  • Reading: 5.0
  • Writing: 5.0
  • Speaking: 5.0

あと、2年前から伸び悩んでいたTOEICも受けてみたのだけど、2年前より30点だけスコアが上がっていて自己ベストを更新したのが嬉しかった。DMM英会話をやめて単語ぐらいしか真面目に勉強していなかったけど、それでもまだスコアが伸びる余地があるということが実感できた。何よりも40歳を過ぎても何かの能力・スコアが上がるという実感が得られたのが嬉しい。

読んだ本

今年はほとんど本を読まなかった。真面目に読んだのは以下のみ。

Googleを支える技術

Googleの初期の検索システムの内部構造などについて詳しく書かれている本。とてもわかりやすく説明してあって楽しく読めた。

Googleを支える技術 ‾巨大システムの内側の世界 (WEB+DB PRESSプラスシリーズ)

Googleを支える技術 ‾巨大システムの内側の世界 (WEB+DB PRESSプラスシリーズ)

  • 作者:西田 圭介
  • 出版社/メーカー: 技術評論社
  • 発売日: 2008/03/28
  • メディア: 単行本(ソフトカバー)

脳を鍛えるには運動しかない!

運動後に何かを勉強すると学習効率が上がるなど、実験結果の事例から運動と脳の関係性について説明する本。運動することはメンタルヘルスにも良い影響があるということで、これを読んだあとから必ず週に2回はジムで有酸素運動をするようにしている。

脳を鍛えるには運動しかない!  最新科学でわかった脳細胞の増やし方

脳を鍛えるには運動しかない! 最新科学でわかった脳細胞の増やし方

Go言語による並行処理

Goの並行処理についてとにかく丁寧にわかりやすく解説している良い本。Goは一通り書けるけど、channelやgoroutineを使いこなせていないと感じている人にはぜひオススメしたい。

Go言語による並行処理

Go言語による並行処理

  • 作者:Katherine Cox-Buday
  • 出版社/メーカー: オライリージャパン
  • 発売日: 2018/10/26
  • メディア: 単行本(ソフトカバー)

IntelliJ IDEAハンズオン

IntelliJについて詳しく解説してある本。ほぼ独学で使っているIntelliJについて、体系的に学び直せたのは良かった。

IntelliJ IDEAハンズオン――基本操作からプロジェクト管理までマスター

IntelliJ IDEAハンズオン――基本操作からプロジェクト管理までマスター

エンジニアの知的生産術

これが2019年の中でベストな本だった。まだ読み終わっていないけど、どうすれば効率的に本を読めるかなどが体系的に書かれているし、すぐに実践できる内容でもある。

エンジニアの知的生産術 ──効率的に学び、整理し、アウトプットする (WEB+DB PRESS plusシリーズ)

エンジニアの知的生産術 ──効率的に学び、整理し、アウトプットする (WEB+DB PRESS plusシリーズ)

  • 作者:西尾 泰和
  • 出版社/メーカー: 技術評論社
  • 発売日: 2018/08/10
  • メディア: 単行本(ソフトカバー)

育児

息子も5歳になって、0歳〜2歳の時に比べると本当に手がかからなくなってきたように思う。元気に育っていてそれが一番ありがたいし(元気すぎて困る)、今年だけで以下のアビリティを習得している(すごい!)。

  • 自転車に乗れるようになった!
  • ひらがなを全部読めるようになった
  • 自分の名前をひらがなで書けるようになった
  • (体操の)前転と後転がすごく上手になった
  • レゴをほぼ自分だけで組み立てられるようになった
  • 英単語を少しだけ覚え始めた
  • 箸を持てるようになった(練習中)

また、奥さんの海外出張が今年も2回あったけど、去年よりはうまく乗り切れた気がする。去年は出張中は寂しくて泣いてしまう時が多かったけど、今年は1,2回しか泣かなかったし、なるべく休みの日は鉄道博物館とか、今までに行ったことがないところに連れて行って楽しくやれたんじゃないかと思う。

まとめ

2019年は2018年に比べると仕事も忙しかったけど、学びやアウトプットは昨年よりこなせたかなと思う。2020年も引き続き目標を明確にして頑張っていきたいなと思う。