りんごとバナナとエンジニア

エンジニア修行の記録

Pythonで深さ優先探索を実装する

前の記事で幅優先探索を実装したので、ついでにこちらも。
問題はAtCoder Typical Contest 001A。一応解説スライドはあるが、スタックを使った実装方法が書いてないので、自分でやってみることにした。

実装

from collections import deque

def dfs(maze, visited, sh, sw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.pop()
        if maze[h][w] == "g":
            return "Yes"
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
               new_w < 0 or new_w >= W:
                continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == 0:
                visited[new_h][new_w] = 1
                stack.append([new_h, new_w])
    
    return "No"

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    for i in range(H):
        if maze[i].find("s") != -1:
            sh = i
            sw = maze[i].find("s")
            break

    visited = [[0]*W for _ in range(H)]
    print(dfs(maze, visited, sh, sw))

基本的には、幅優先探索の場合と流れはほぼ同じ。
ただし、今回は後入先出のスタックを使っているため、上下左右にマスが分岐する際に、どれかひとつをこれ以上進めなくなるまで調べ尽くす。

今回の問題のように、単にゴールまでのルートがあるかを素早く調べるには、深さ優先探索の方がよいだろう。

Pythonで幅優先探索を実装する

アルゴリズムの勉強のために、幅優先探索を書いてみた。
使ったのはAtCoder Beginers Contest 007Cの問題。この頃はアルゴリズムがそのまま出題されてたようだ。

特殊事項として、この問題ではスタートからゴールまでは必ず行くことができる前提がある。さらに周り中が壁で囲まれているので、盤面からはみ出すのを考慮する必要がない。

実装

from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])

if __name__ == "__main__":
    R, C = map(int, input().split())
    sy, sx = map(int, input().split())
    gy, gx = map(int, input().split())
    sy, sx, gy, gx = sy-1, sx-1, gy-1, gx-1

    maze = [input() for i in range(R)]
    visited = [[-1]*C for j in range(R)]
    print(bfs(maze, visited, sy, sx, gy, gx))

たった25行で書けた。

原理としては、今いるマスから上下左右に隣り合うマスの座標をキューに入れるとともに、visitedリストにも記録していくという繰り返し。
キューは先入先出なので、今いるマスから上下左右に隣り合うマスを全て探索した後、それらの上下左右に隣り合うマスを探索する、というように探索を行っていく。
全マス調べるため時間はかかるが、ゴールへの最短ルートを確実に求められる。

速度アップの工夫

実をいうと、上記のコードは2度目の提出だった。
その前に書いたバージョンでは、bfs関数を以下のようにしていた。

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    count = 0
    while queue:
        //ここでforループを回している
        for _ in range(len(queue)):
            coord = queue.popleft()
            visited[coord[0]][coord[1]] = 1
            if coord == [gy, gx]:
                return count
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                next_coord = [coord[0]+j, coord[1]+k]
                if maze[next_coord[0]][next_coord[1]] == "." and \
                   visited[next_coord[0]][next_coord[1]] != 1:
                    queue.append(next_coord)
        count += 1

visitedリストの値を0=未訪問と1=訪問のみとしていたため、bfs関数の中のwhile queue以下でforループを回して、ループを何回まわったかをカウントしスタートからの距離を求めていた。しかし、テストケースの最初の4分の1くらいで実行時間が2秒を超え、あえなくTLEに。
そこで、visitedリストの値にスタートからの距離を直接書かせることにした。まずスタートマスの値を0、未訪問のマスの値を-1としておく。そして新しいマスを探索するときは、visitedリストから前にいたマスの値を取り出し、それに1を足した値を新たに書けばよい。
こうすることで、forループをひとつ減らすことができ、実行時間も全体で25msと大幅に速くなった。リストをうまく使うことで、回数カウント目的のforループをなくすというテクニックは、他の問題でも応用できそうだ。

teratail MANABIYAに行きました

manabiya.tech

ふだん質問者としても回答者としてもお世話になっているteratailが主催の、初めての大規模カンファレンスです。

会場は秋葉原にある廃校になった中学校です。ふだん勉強会といえばIT企業でやるのが当たり前なので、なんか新鮮な感じがします。
今日はとりあえず全部聞くのではなく、自分が聞きたくてたまらないと思うセッションに絞ってみました。参加したのは3つだけですが、とても満足してます。

技術者としての成長のための技術トレンド

www.slideshare.net

わー人工知能AWSだ競プロだといろいろ目移りして、どれも中途半端に終わってしまっているという課題感があったので、セッション中絶えず身につまされてました。
なんでも1万時間学べば100人に1人の人材になり、その軸が3つあれば100万人に1人の逸材になれるという有名な話があります。けれどそれは、1万時間(=仕事外だけだとだいたい10年)という膨大な時間を何に費やすかという選択でもあるわけです。
なので、新しく学ぶものは今メインにしている技術からなるべく離れていて、かつ心からワクワクできるものにすべきというのが、エンジニアが取るべき成長戦略になります。
自分が本当にやるべきこと・やりたいことを、目移りせずに絞っていけるようになりたいものです。
(ちなみに「本当は仕事外だけじゃなくてそれを仕事にしちゃうのが一番ですよ〜」とも言われました。身もふたもない)

2018年のWeb標準

speakerdeck.com

Service Worker, Web Components, Web Paymentsのざっくりした紹介。人が部屋からあふれる盛況ぶりでした。
実際にそれぞれデモを見せてもらったのですが、特にWeb ComponentsとWeb Paymentsは衝撃的でした。
Web Componentsがあれば、<fancy-button>みたいな独自のHTML要素を定義・再利用するのが当たり前になる!
Web Paymentsが普及すれば、決済フォームというものがなくなって、ECサイトの体験がまるきり変わるかもしれない!
という感じで、心の中で一人盛り上がってました。
もちろん、いろいろな細かい制約もたくさんあるでしょうし、そもそも本当に普及するかどうかもわからないのですが、わくわくするようなトレンドの種があれば、今のうちに勉強しておくのもいいかもしれないと思いました。

オブジェクト指向型言語と関数型言語

オブジェクト指向言語と関数型言語 | κeenのHappy Hacκing Blog

内容がとても多く、濃い密度で進んだセッションでした。
関数型プログラミングは全く知らないのですが、「オブジェクト指向はデータを抽象化し、関数型は処理を抽象化する」という説明はわかりやすかったです。
私含め世の中の多くのエンジニアは、オブジェクト指向プログラミングを当たり前のものとして日々過ごしていると思うのですが、それとは全く違うパラダイムがあり、しかもその世界は同じくらい広くて深いとわかると、やっぱりわくわくしますね。

その他

  • 10%オフにつられてオライリーの技術書を買いました。重い。
  • DataChainのブースで資料のかわりにどら焼きをもらいました。
  • 給食風カレーうどんは本当に給食風でした。
  • 空き時間にTwilio Challengeをやってマグカップをもらいました。APIをいじるのは楽しいです。

振り返ってみると意外と満喫してました。カンファレンスでの過ごし方がうまくなってきてるかもしれません。
次回があればまた参加したいです。

Javaでスレッドを作ってみる

JVMでは並行処理を実現するために、スレッドを作ることができる。
並列処理を使わなくてもよい処理を書いていたが、せっかくなので公式ドキュメントを見ながらスレッドを作ってみた。

スレッドを作る方法

スレッドを作るには2つの方法がある。ひとつはThreadクラスを継承してrunメソッドをオーバーライドすること。
公式に載ってた「初期値より大きい素数を計算する」コードを書いてみた。

class PrimeThread extends Thread {
    long minPrime;
    long nextNum;
    public PrimeThread(long minPrime) {
        this.nextNum = minPrime;
    }
    
    public void run() {
        System.out.println(calculate());
    }

    public long calculate() {
        do this.nextNum += 1; while (!isPrime(this.nextNum));
        return this.nextNum;
    }
    
    public boolean isPrime(long num) {
        if (num == 2) return true;
        if (num % 2 == 0) return false;
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) return false;
        }
        return true;
    }   
}

public class SampleThread {
    public static void main(String[] args) {
        PrimeThread primeThread = new PrimeThread(140);
        primeThread.start();
    }
}

もうひとつは、Runnableインターフェースを実装すること。

class PrimeRun implements Runnable {
    long minPrime;
    long nextNum;
    public PrimeRun(long minPrime) {
        this.nextNum = minPrime;
    }
    
    public void run() {
        System.out.println(calculate());
    }

       \\ 以下同様なので中略
}

public class SampleThread {
    public static void main(String[] args) {
        PrimeRun primeRun = new PrimeRun(140);
        new Thread(primeRun).start();
    }
}

2つのやり方の違い

この2つのやり方はどう違うのかと思ったけれど、そこまで違いはなさそうだ。
Threadクラスのstartメソッドのコードは以下のようになっている。

public synchronized void start() {

        if (threadStatus != 0)
            throw new IllegalThreadStateException();

        boolean started = false;
        try {
            start0();
            started = true;
        } finally {
            try {
                if (!started) {
                    group.threadStartFailed(this);
                }
            } catch (Throwable ignore) {
                /* do nothing. If start0 threw a Throwable then
                  it will be passed up the call stack */
            }
        }
    }

    private native void start0();

    @Override
    public void run() {
        if (target != null) {
            target.run();
        }
    }

startメソッドは、C++で実装されたstart0メソッドを呼び出している。そしてstart0メソッドがrunメソッドを呼ぶのだが、このrunメソッドはオーバーライドされることが前提であり、親クラスの中の処理は何の意味も持たない。 ※ちなみにC++内でどんな処理をしているかは、以下の記事が詳しい。

Thread.javaのstart()はrun()をどのように呼ぶのか?(備忘録) - Qiita

一方Runnableインターフェースは、当然だが抽象メソッドとしてrunメソッドを定義しているだけだ。

public interface Runnable {
    public abstract void run();
}

どちらのやり方を使っても、結局runメソッドは全部自前のものを使うことになる。

GitHubでやらかしたコミット履歴を(ほぼ)見えなくする方法

Gitを覚えたての初心者が一番よくやらかすミスは、パスワードやAPIキーをハードコーディングしたものをリモートリポジトリにプッシュしてしまうことじゃないだろうか。
もちろん速やかにパスワードやキーの変更をすることは前提だが、問題は恥ずかしいコミット履歴がその後も残ってしまうことだ。
そんなときにどうすればいいか、この前teratailで他の人の回答を見る機会があったので実際に試してみた。

はじめに

この方法は、ざっくり言えば歴史を改変することに等しい。多人数で開発をしているときに何の断りもなく使うと、トラブルが起こる可能性が高いので注意すること。

やらかしたコミットを作る

実際にリポジトリを作り、プッシュを2回行った。内容はteratailのAPIを叩くサンプルコードだ。
github.com

$ git log --oneline 
bd6c846 (HEAD -> master, origin/master) アクセストークンを追加
b7ee88e initial commit

2回目でうっかりアクセストークンが見える状態のコードをコミットし、気づかずにそのままプッシュしてしまった。この履歴を消したい。

git rebaseでコミットを消す

git rebaseは、過去のコミットを編集してコミット履歴を整理するためのコマンドである。
本来の使い方ではないが、これを使ってやらかしたコミットを履歴から消すことができる。

git rebase -i b7ee88eのように、消したいコミットのひとつ前のコミット識別番号を指定する。

pick b41300e アクセストークンを追加 

# Rebase b7ee88e..b41300e onto b7ee88e (1 command)
#
# Commands:
# p, pick = use commit
# r, reword = use commit, but edit the commit message
# e, edit = use commit, but stop for amending
# s, squash = use commit, but meld into previous commit
# f, fixup = like "squash", but discard this commit's log message
# x, exec = run command (the rest of the line) using shell
# d, drop = remove commit
#
# These lines can be re-ordered; they are executed from top to bottom.
#
# If you remove a line here THAT COMMIT WILL BE LOST.
#
# However, if you remove everything, the rebase will be aborted.
#
# Note that empty commits are commented out

エディタが開いたら、pickの部分を変えることで様々な編集ができる。今回はdropに変更して保存することで、そのコミットを消せる。

$ git log --oneline
b7ee88e (HEAD -> master) initial commit

やらかしたコミットが消えた。
あとはプッシュするだけ。プッシュする際は、普通にgit push origin masterとするとrejectされるので、git push --force origin masterのようにする。
今回使ったリポジトリを確認してほしい。initial commitしか見えないはずだ。

【参考】厳密には消えてない

ただしGitは歴史を全て保存するので、厳密には消えたわけではない。
git reflogコマンドを叩くと、git logでは出てこないものも含めた全ての履歴が表示される。git rebaseで編集した跡も残っている。

$ git reflog
b7ee88e (HEAD -> master, origin/master) HEAD@{0}: rebase -i (finish): returning to refs/heads/master
b7ee88e (HEAD -> master, origin/master) HEAD@{1}: rebase -i (start): checkout b7ee88e
b41300e HEAD@{2}: rebase -i (finish): returning to refs/heads/master
b41300e HEAD@{3}: rebase -i (pick): アクセストークンを追加
27ce491 HEAD@{4}: rebase -i (pick): initial commit
9d36eb3 HEAD@{5}: rebase -i (pick): initial commit
17ff75b HEAD@{6}: rebase -i (start): checkout 17ff75b6f56acea009e986d19a152298efb7dabb
bd6c846 HEAD@{7}: rebase -i (finish): returning to refs/heads/master
bd6c846 HEAD@{8}: rebase -i (start): checkout HEAD~1
bd6c846 HEAD@{9}: rebase -i (finish): returning to refs/heads/master
bd6c846 HEAD@{10}: rebase -i (start): checkout b7ee88e
bd6c846 HEAD@{11}: commit: アクセストークンを追加
b7ee88e (HEAD -> master, origin/master) HEAD@{12}: commit (initial): initial commit

コミット識別番号がわかれば、そのコミットが見える。
GitHub上でも、以下のURLを叩くと今回やらかしたコミットが見えてしまう。
https://github.com/Udomomo/changeHistory/commit/bd6c846

もっとも、コミット識別番号がわからない限り見ることができないため、赤の他人に漏れる心配はほとんどない。
GitHub社員はユーザのリポジトリのreflogを見られるようだが、それを悪用したら当然サービスとしての信頼が失墜するので、基本的には考慮しなくてよいだろう。

注意点

  • initial commitでやらかしてしまった場合、通常のrebaseでは対応できない。
    このサイトによれば、git rebase -i --rootとしなければいけないようだ。

d.hatena.ne.jp

  • GitHubでは、やらかしたコミットを使ってプルリクエストを投げてしまうと、それを消すことはできない。
    そもそもプルリクエストを完全に削除する方法が存在しないらしい。

  • 最後になるが、多人数での開発時はむやみにrebaseを使わないこと。やらかしたらまずパスワードやキーを変えること。
    そして一番大事なのは、大事な情報をハードコードしない習慣をつけること。いいですね?

Eclipseでのデバッグ超基本編

最近Eclipse上でコードを実行した際によくわからない挙動が起きたが、先輩にデバッグツールの使い方を教えてもらって無事解決できた。
Eclipseに限らず、今までデバッグツールというものがよくわからなくてまともに使ったことがなかったのだが、今回使ってみて「これはマジで生産性10倍以上になるぞ...」と思ったので、忘れないようにやり方を書いておく。

今回起こった挙動

とあるクラスのインスタンスが保持していた値をDBに書き込むコードを扱っていたのだが、DBに書き込まれた値が想定と異なっていた。
書き込み前に、どこかで変数の値が変わってしまっている可能性が高い。

ブレークポイントをつける

まず、デバッグ時に処理を止めたい行にブレークポイントをつける。行の左側をダブルクリックすればいい。

デバッグモードで走らせる

今回は実行時にargumentを渡さないといけないコードだったので、Run -> Debug Configurationを選んで起動時の設定をしておく。あるいは、虫マークの横にあるプルダウンから選んでもよい。
特に設定が必要なければ、普通にDebugで走らせればよい。 デバッグモードで実行すると、「Perspectiveを開きますか」というポップアップが出るので、Yesを選択して開く。

行を進める

ブレークポイント以降は、行を手動で進めていく。主な処理は以下の3つ。
* Step Over: 次の行に進む。
* Step In: メソッドが実行されている行の場合、その中のコードに入る。
* Step Return: メソッドの中にいる場合に、処理を全て行ってメソッドから抜ける。

変数の値を確認

今いる行の時点での変数の値は、画面右上の「変数」欄で確認できる。しかし、この欄の中の項目は行を進めるごとに折りたたまれてしまうため、変数が多いと探すのが大変になる。
そこでより便利なのが、Show View -> Expressionsを開くこと。
ここにはJavaの式を書くことができ、それを評価してくれる。つまり、ここに変数名を書いておけばすぐに値を見られるようになる。
後は行を進めつつ、変数の値がどこで変化するか確かめていく。

他にもEclipseにはデバッグ機能がいろいろついているようなので、使いこなせるようになっておきたい。
今まで他の言語でよくデバッグツールを使わずにやってきたなあとしみじみ振り返っている。

Sublime Text3の使ってみたいコマンド

まだエンジニアになったばかりの頃になんとなくSublime Text3を使い始めたが、まだその全てを使いこなせていない自覚があった。
何のエディタを使うにせよ、その真の力を知らないでいるのはもったいない。

Sublime Text便利なショートカットコマンドはたくさんあるが、その中でも自分が知らなくて、ぜひ使ってみたいと思うものをまとめた。

Cmd + ↑ / Cmd + ↓ : 文書の先頭/最後に移動

Cmd + →で行の最後に行くのは知っていたけど、文書の端に行くコマンドは恥ずかしながら知らなかった。

Cmd + /: 行をコメントアウト

カーソルがいる行を、今使っている言語での形式に合わせてコメントアウトしてくれる。
実装のやり方を試行錯誤しているときに、ある行の処理をコメントアウトしてそこだけ新しい処理に変えたりすることがよくあるので、このコマンドは重宝しそう。

同じ単語を全て操作

Cmd + dで今カーソルが載っている単語と同じ単語が全てハイライトされ、Cmd+gでカーソル選択状態にして次の単語に行くことができる。
Cmd + Ctrl + gなら同じ単語を全て選択できる。

変数の名前を変えるときなどに威力を発揮するだろう。
個人的にはハイライトされた同じ単語の一部だけ選択しないでスキップする機能があるとよかったが、そのコマンドはなさそうだ。

複数行の行末にカーソルをつける

Cmd + Ctrl + lで、今ハイライトされている行全ての行末にカーソルが当たる。 複数行に後からクォーテーションをつけて配列や辞書を作りたいときに使える。

ちなみに、各行の頭にもクォーテーションをつけたいときはさらに一工夫が必要。
上記コマンドでできた複数カーソルを普通に左右キーで動かすと、各行の文字数が違うので行頭でカーソルが揃わず収拾がつかなくなる。 ここでは行頭に行くコマンドが必要。Cmd + ←コマンドは、インデントを除いた各行の最初の文字の前にカーソルが揃う。Ctrl + aコマンドはインデントも文字とみなし、行頭にカーソルが揃う。 再び行末で揃えるにはCmd + →Ctrl + eを使う。

Cmd + Pでファイル間ジャンプ

「ファイルを開く」メニューを使わなくても、ファイル名を途中まで入力するだけですぐに開ける。
さらに、続けて#hogeと入力すれば最初にhogeが出てくるところに移動し、:50なら50行目に行ける。@funcならfuncという関数(あるいはクラス)の場所に飛べる。
対象となるのはあらかじめSublime Textで開いてあるフォルダ内のみのようだが、フォルダ内でファイルを分割してコーディングするのは日常なので、これはとても便利そうだ。

教訓:エディタの売りはよく読もう

後半の方の機能は、Sublime Text3のトップページに堂々と書いてあった...
使い始めた頃はこれらの機能がどう良いのかよくわからなかったが、今ならその価値がわかる。
当時はコーディング作業のイメージがわかなかったので仕方ない面もあるが、エディタ選びは単なる口コミだけではなく、自分のストレスややりたいことをベースに選ぶのが一番いいだろう。