JUNのブログ

JUNのブログ

活動記録や技術メモ

ダイクストラ法試してみた

最近早水先生の講義を見ているのですが, そこでダイクストラ法の説明があり, 実装したくなったので実装した.

www.youtube.com

import heapq

INF = float("inf")

# 各駅間の道を (行き先, 重み) という要素の隣接リストの形で保持する.
graph = [
    [(1, 16), (2, 8), (3, 15)],
    [(0, 16), (2, 13), (4, 27), (6, 78)],
    [(0, 8), (1, 13), (3, 21), (4, 10), (5, 17)],
    [(0, 15), (2, 21), (5, 33)],
    [(2, 10), (1, 27), (6, 15)],
    [(2, 17), (3, 33), (6, 52)],
    [(1, 78), (4, 15), (5, 52)],
]
# 英語バージョン
"""
stations = [
    "Tokyo",
    "Shibuya",
    "Shinagawa",
    "Sinjuku",
    "Shinyokohama",
    "Yokohama",
    "Odawara",
]
"""
# 日本語バージョン
stations = [
    "東京",
    "渋谷",
    "品川",
    "新宿",
    "新横浜",
    "横浜",
    "小田原",
]


def dijkstra(s, n):  # (始点, ノード数)
    dist = [INF] * n
    hq = [(0, s)]  # (distance, node)
    heapq.heapify(hq)
    dist[s] = 0
    prevs = [-1] * n  # 前の駅(経路復元用)
    seen = [False] * n  # ノードが確定済みかどうか
    while hq:
        cost, v = heapq.heappop(hq)  # ノードをpopする
        seen[v] = True
        for to, cost in graph[v]:  # ノードvに隣接しているノードに対して
            if seen[to] == False and dist[v] + cost < dist[to]:
                print(f"{stations[to]}のコストを更新! {dist[to]} -> {dist[v]+cost}")
                dist[to] = dist[v] + cost
                prevs[to] = v
                heapq.heappush(hq, (dist[to], to))
    return dist, prevs


# (出発, 到着)
start, end = input().split()

if start not in set(stations) or end not in set(stations):
    print("指定された駅は無いよ!")
    exit(1)

dist, prevs = dijkstra(stations.index(start), len(stations))
print(f"{start}から{end}の所要時間は {dist[stations.index(end)]}")

# 経路復元
def restore_path(prevs, v):
    if prevs[v] != -1:
        restore_path(prevs, prevs[v])
    print(f"{stations[v]}", end="->" if v != stations.index(end) else "\n")

restore_path(prevs, stations.index(end))

実行すると

$ python3 dijkstra.py
東京 小田原
渋谷のコストを更新! inf -> 16
品川のコストを更新! inf -> 8
新宿のコストを更新! inf -> 15
新横浜のコストを更新! inf -> 18
横浜のコストを更新! inf -> 25
小田原のコストを更新! inf -> 94
小田原のコストを更新! 94 -> 33
東京から小田原の所要時間は 33
東京->品川->新横浜->小田原

とこんな感じで講義動画と同じような経路更新が出来ている.

f:id:JUN_NETWORKS:20210801130052p:plain
離散数学入門#5: 最短経路問題:ダイクストラ法とワーシャル–フロイド法」より

他の経路も試してみる

$ python3 dijkstra.py
渋谷 新宿
東京のコストを更新! inf -> 16
品川のコストを更新! inf -> 13
新横浜のコストを更新! inf -> 27
小田原のコストを更新! inf -> 78
新宿のコストを更新! inf -> 34
新横浜のコストを更新! 27 -> 23
横浜のコストを更新! inf -> 30
新宿のコストを更新! 34 -> 31
小田原のコストを更新! 78 -> 38
渋谷から新宿の所要時間は 31
渋谷->東京->新宿

$ python3 dijkstra.py
渋谷 横浜
東京のコストを更新! inf -> 16
品川のコストを更新! inf -> 13
新横浜のコストを更新! inf -> 27
小田原のコストを更新! inf -> 78
新宿のコストを更新! inf -> 34
新横浜のコストを更新! 27 -> 23
横浜のコストを更新! inf -> 30
新宿のコストを更新! 34 -> 31
小田原のコストを更新! 78 -> 38
渋谷から横浜の所要時間は 30
渋谷->品川->横浜

$ python3 dijkstra.py
小田原 東京
渋谷のコストを更新! inf -> 78
新横浜のコストを更新! inf -> 15
横浜のコストを更新! inf -> 52
品川のコストを更新! inf -> 25
渋谷のコストを更新! 78 -> 42
東京のコストを更新! inf -> 33
渋谷のコストを更新! 42 -> 38
新宿のコストを更新! inf -> 46
横浜のコストを更新! 52 -> 42
小田原から東京の所要時間は 33
小田原->新横浜->品川->東京

正しく求められているっぽい.

感想

早水先生の講義わかり易すぎてビビる.

乗り換えアプリとかも基本的にはこういう感じで作られているのかなぁと思った.

最小値を取り出すところはPriotiryQueueを使うと最小値を計算時間(O(log N))で取得出来て良い感じ.

参考にしたサイト

Linux環境でも放送大学の授業を受けたい!

放送大学の授業はテレビ,ラジオ,ブラウザで視聴することが可能なのですが, このブラウザ視聴の対応OSにLinuxが入っていません.

www.ouj.ac.jp

Linux(Ubuntu 20.04) の Chrome から放送大学の授業科目動画のサンプル(授業の第一回目)を視聴しようとするとエラーメッセージが表示されてページにアクセス出来ません.

f:id:JUN_NETWORKS:20210722014401p:plain
Ubuntu20.04のGoogle Chromeから視聴ページにアクセスするとエラーが発生する

www.ouj.ac.jp

解決方法

以下のページに書いてある通り推奨環境はPCの場合はWindowsMacです.

www.ouj.ac.jp

じゃあどうやって放送大学側はLinuxChromeからのリクエストを識別しているかと考えれば, まぁ普通はHTTPの User-Agent だろうなという予想はつくわけです. なのでChrome側のUser-AgentWindowsChromeの文字列に書き換えてメッセージを送ってみます.

f:id:JUN_NETWORKS:20210722014759p:plain
`User-Agent` をWindowsChromeに書き換えることで視聴できる

User-Agentの書き換え方はChrome公式が紹介しているのでそれを参考にしました.

developer.chrome.com

で, 毎回毎回こんな感じでChromeデベロッパーツールを開いてUser-Agentを書き換えるのはめんどいのでUser-Agentドメインごとに切り替えるChrome拡張を入れます.

chrome.google.com

User-Agent Switcher and Manager のオプションを開いて, 以下の内容を貼り付ければ放送大学ドメインではWindowsChromeUser-Agentでリクエストを送信するようになります.

{
  "ouj.ac.jp": "Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/91.0.4472.114 Safari/537.36"
}

これで放送大学の授業をLinux環境のChromeから視聴出来るようになりました!

感想

Linux環境のChromeから放送大学の授業を視聴できなくて, 調べても情報が無かったので備忘録として書いておきました.

放送大学さん, Linux環境からも普通に授業が視聴できるようにしてくれると嬉しいです.

シェル実装の課題を完走した

42Tokyoで minishell という課題があり, 完走したので感想書きます.

minishellについて

minishellとはbashっぽいシェルをC言語で実装する課題.

実装する機能は以下の通り

  • readlineを使った入力と履歴の実装.
  • 絶対パス もしくは $PATH 環境変数を使った実行ファイルの実行 (/bin/lsls)
  • ビルトインコマンド
    • echo (-nオプションのみ対応)
    • cd (相対か絶対パス)
    • pwd (オプションなし)
    • export (オプションなし)
    • unset (オプションなし)
    • env (オプションなし)
    • exit (オプションなし)
  • シングルクオートとダブルクオート
  • 入出力リダイレクション (<, >, >>) と heredocument (<<)
  • パイプ (|)
  • 環境変数$?
  • ctrl-C(SIGINT), ctrl-\(SIGQUIT), ctrl-D(EOF)

っていう感じでbashっぽい小さなシェル(minishell)を作るという課題です.

この課題はチーム課題で, torusさん とチームを組んで取り組みました.

実装

実装したコードはここにあります.

github.com

動いている様子

gyazo.com

シェル全体の構成

全体を超大雑把に分けると以下のようなコンポーネントに分解できます.

  1. 入力処理(readline): JUN
  2. Lexer & Parser: torus
  3. CommandExecution: JUN

JUNと書いてあるのが自分が主に担当した部分で, torusと書いてあるのがtorusさんが主に担当した部分です.

大まかな設計は The Architecture of Open Source Applications という本の中にあるbashの章の中のbashコンポーネントアーキテクチャ図を参考にしてコンポーネントを分け, その後それぞれに担当を決めました.

ここから先はこれらコンポーネントそれぞれについての説明を書くのですが, 自分が担当した部分に関しては詳細に書けるのですが, 自分が担当していない部分に関しては少し大雑把な説明になるかもしれないです.

入力処理

入力処理はreadlineを使って良いとのことなので, 使いました.

正直 readline が便利すぎてあまり入力処理について説明することは無いです. 強いて言うならシグナルハンドリングは少し気をつける必要がありますが, The GNU Readline Libraryを使ったを見ればなんとかなります.

実はこの入力処理についてはちょっとした小話があるのですが, それはまた後ほど...

Lexer & Parser

Lexer (字句解析)

Lexerとは字句解析機であり, 入力文字列を解釈し, 字句(ひとつの意味のある文字列単位)単位で取り出せるみたいな感じです. 字句はToken, 字句解析機はTokenizerとも呼ぶみたいです.

例えば入力が echo Hello I am "JUN" 'san' | cat なら以下のように取り出せるイメージです.

Token Type
echo EXPANDABLE
Hello EXPANDABLE
am EXPANDABLE
JUN EXPANDABLE_QUOTED
san NON_EXPANDABLE
| PIPE
cat EXPANDABLE

ja.wikipedia.org

Parser (構文解析)

Lexerで字句単位に文字列を取り出せるようになったのでここでは取り出した字句を元に構文解析を行い抽象構文木(AST)を作成します.

シェルが受け付ける文字列の文脈自由文法(課題に必要な部分のみ)は バッカス・ナウア記法(BNF) を用いて以下のように表される.

command_line ::=
      "\n"
    | sequencial_commands delimiter "\n"
    | sequencial_commands "\n"

delimiter ::=
      ";"

sequencial_commands ::=
      piped_commands delimiter sequencial_commands
    | piped_commands

piped_commands ::=
      command "|" piped_commands
    | command

command ::=
      arguments

arguments ::=
      redirection
    | redirection arguments
    | string
    | string arguments

string ::=
      expandable <no_space> string
    | expandable
    | not_expandable <no_space> string
    | not_expandable
    | expandable_quoted <no_space> string
    | expandable_quoted

redirection ::=
      "<" string
    | ">" string
    | ">>" string
    | "<<" string

この文法に基づいて再帰下降構文解析を行いASTを生成する.

f:id:JUN_NETWORKS:20210701232046p:plain
abc def | file < infile ; xyz ; のパース結果

CommandExecution

Lexer, Parser の処理が完了し, ASTが生成できたら今度はそれを元に実際にリダイレクションの処理やコマンドの実行などを行います.

今回は "Lexer & Parser" と "CommandExecution" を完全に分けて実装したので, ASTをそのまま使って実行するのではなくCommandExecution側で受け取りたい構造体(t_command_invocation)というのを予め定義しておき, ASTとt_command_invocationを変換する関数を最終的に作ることによって同時並行でそれぞれの担当箇所を実装できると共に, どちらか一方に変更があっても変換関数を修正すれば良いだけになります.

t_command_invocation は具体的には以下のような構造体です.

typedef struct s_command_invocation
{
    t_cmd_redirection           *output_redirections;
    struct s_command_invocation    *piped_command;
    t_cmd_redirection           *input_redirections;
    const char                    **exec_and_args;
    pid_t                       pid;
}   t_command_invocation;
  • t_cmd_redirection はリダイレクションに関する情報を持つ片方向連結リストの構造体です. 具体的には以下の情報を持っています.

    • ファイルパス (heredocの場合は入力された文字列)
    • リダイレクションの種類(追記かどうか, heredocかどうかなど)
    • リダイレクションで指定されたファイルディスクリプタ
    • 次のリダイレクションへのポインタ
  • piped_command はパイプの次のコマンドへのポインタです.

  • exec_and_args は実行するプログラムに渡す文字列配列です. int main(int argc, char **argv) と書いたら受け取れる argv の部分です.

  • pid はコマンド(プログラム)が子プロセスで実行された時のプロセスIDです. fork() して作成した子プロセスを wait() して終了ステータスを取得するために使います. あと, fork()して作成した子プロセスを正しくwait()してあげないとゾンビプロセスになってしまうのでこれを避けるためにも子プロセスのpidは必要です.

リダイレクションの処理

リダイレクションの処理は基本的には dup2() などを使って標準入出力のfd(2>3<みたいなfd指定の場合は指定のfd)をファイルのfdに置き換えれば出来ます.

気をつけるべき点としては, bashでは複数リダイレクションが存在する時, そのfdのリダイレクションの中で最後リダイレクションのみが書き込みや読み込みが行われることです.

bashecho hello > file1 > file2 > file3 と実行するとfile1file2はファイルは作成されるが, 何も書き込まれておらず, file3にのみ"hello"が書き込まれています. ちなみにzshの場合だと全てのファイルに"hello" が書き込まれるという違いがあります.

入力の場合も同様で, cat < file1 < file2 の場合, 実際にcatコマンドの標準入力に繋がれるのは file2 のみです.

heredocument

heredocument はbash特有の概念ではなく, いろんな言語に実装されている.

en.wikipedia.org

要は複数行文字列リテラルということみたいです. bashにおいては << と区切り文字の組み合わせで始まり, もう一度区切り文字が出現するまでの文字列をコマンドの標準入力に流し込むというものになっています.

f:id:JUN_NETWORKS:20210701040100p:plain
heredocumentの例

f:id:JUN_NETWORKS:20210701040157p:plain
複数heredocumentの例

f:id:JUN_NETWORKS:20210701040746p:plain
パイプとheredocumentを組み合わせた例

まぁ大体雰囲気はこんな感じです.

で, 実装の方なんですが, heredocumentの入力タイミングはParserの後, ASTをt_command_invocationに変換する関数内で行うようにしました. つまり, cat << EOF はparserが処理して, そこから先入力される文字列はParserではなくCommandExecution側で入力を受け付けて, 入力された文字列を構造体のメンバに保存します.

fd周りについてですが, ファイルのリダイレクションだとopen()すればよいのですが, heredocument はファイルを入力としているわけではないので, リダイレクションとは分けて考えるべきです.

しかし, 最初どういう風に実装されているか全然わからなかったのでbashのソースコードを見に行きました. そうするとどうやら親プロセスから子プロセスに対してheredocument用のpipeを繋いで文字列を渡しているようです.

先程紹介した "パイプとheredocumentを組み合わせた例" を例に図にすると以下のような感じです.

f:id:JUN_NETWORKS:20210701170325p:plain

パイプラインのコマンド間のパイプ以外にも, シェルのプロセスと子プロセス間のheredocument用のパイプを作成し, そのpipeに対してheredocumentで入力された文字列をwrite()することで実現出来ます.

プログラムの実行

今回自分はシェルのパイプラインの実装はループで子プロセスを生成していくやり方にしました. echo hello | wc -l | cat を例として考えると以下の様になります.

f:id:JUN_NETWORKS:20210701171159p:plain

シェルのパイプライン処理の実装方法はいくつかあるのですが, 複数コマンドが同時に動くという点(並列実行)に気をつけましょう.

例えば bashcat | ls とすると, catの実行が完了する前にlsの出力が先に出現します. これはcatの実行が完了してからlsを実行する逐次的な実行ではなく, catls を並列に実行させているからです.

f:id:JUN_NETWORKS:20210701174911p:plain
`cat` と `ls`が同時に実行され `cat` が入力待ちになっている

ビルトインコマンド

ビルトインコマンドというのはシェル側で実装してシェルに組み込まれているコマンドです.

ビルトインコマンドの実装自体は基本的にはbashのビルトインコマンドのヘルプとかを読みながら関数として実装すれば良いです.

で, 問題となるのはコマンドそのものというよりかはビルトインコマンドの実行方法です. ビルトインコマンドは外部のプログラムを呼び出すわけではないので execvp() などはしません.

ビルトインコマンドは単体で実行される場合とパイプラインとして実行される場合で実行方法が異なります.

ビルトインコマンド単体で実行される場合はfork()せずにシェルのプロセス上で対象の関数を呼び出します.

その際にリダイレクションが含まれている場合は標準入出力をdup() などを使って保存しておき, 後に復元する必要があります. こうしないとその後標準入出力が使えなくなります.

例えば echo hello > output.txtが入力された時, もしechoが外部コマンドならSTDOUT_FILENOopen("output.txt", O_WRONLY | O_CREAT)で出力先ファイルのfdを使ってdup2(fd, STDOUT_FILENO) のように置き換えれば良いだけです. なぜなら外部コマンドを実行しているプロセスはシェルのプロセスではなく, シェルのプロセスからfork()された子プロセスであり, 子プロセスのfdがどうなろうと親プロセスには影響しないからです.

しかし, シェルのプロセスで実行するビルトインコマンドは話が違います. そのまま愚直にdup2(fd, STDOUT_FILENO)などとしようものなら標準出力はcloseされ, その後シェルが標準出力に書き込む手段が無くなります. なのでこのような悲惨な事態を避けるために dup(STDOUT_FILENO) のようにリダイレクション用のfdとは別に標準入出力のfdを複製して保持しておきます. そしてリダイレクションの処理を行っている時に複製した標準入出力のfdとリダイレクションで指定されたfd(2> みたいなやつ)が被ったらもう一度dup(複製した標準入出力のfd)をしてからファイルのfdに置き換えることで標準入出力のfdを失わないようにしながらリダイレクションを処理する必要があります.

そしてリダイレクションなどの処理が終わり, ビルトインコマンド関数の実行が完了したらリダイレクション用に開けていたfdを閉じて, 標準入出力のfdを元のfdに戻して完了です.

このようにビルトインコマンド単体の場合はシェルと同じプロセスで実行されるためリダイレクション周りなどは注意を払う必要が有ります.

次にパイプラインの中にビルトインコマンドがある場合, 例えば echo hello | cat のような場合です.

この場合, 外部コマンドを実行する時と同じ様にfork()して子プロセスを生成します. 違いはexecvp()で外部のプログラムを読み込んでメモリを別のプログラムに置き換えることはせず, ビルトインコマンドに対応した関数を呼び出して終了する点です.

ここまでの話で説明したとおりビルトインコマンドは単体の場合はシェルのプロセスで, パイプライン内の場合はシェルの子プロセスで実行されます. そして子プロセスの環境変数やfdの変更, メモリの操作, カレントディレクトリの変更 は親プロセスに影響しません.つまりどういうことが起きるかというと, 以下のようなことが起きます.

f:id:JUN_NETWORKS:20210701215039p:plain
bashでの実行例

パイプライン内で export した環境変数が反映されていませんね. これは export環境変数を追加したけれど, コマンドがパイプライン内にあるのでexportは子プロセスで実行され, 親プロセスであるシェルのプロセス内の環境変数には反映されていないのです.

cdでも同様にパイプライン内で実行するとシステムコールchdir()が子プロセス内で実行されるためシェルのcwdは変わりません.

f:id:JUN_NETWORKS:20210702031526p:plain
bashでの実行例

こういうのを知るとなぜ exportunset, cdなどがビルトインコマンドとしてシェルに組み込まれているかがわかりますね.

その他

環境変数の保持方法

初めのころは, 環境変数は文字列配列environをそのまま保持していて, 環境変数を追加する時は文字列配列のメモリ領域を確保し直し(課題の制約でrealloc()は使えないので), environにもともと入っていたデータを新しい配列にコピーしその後最後の要素に新しい環境変数の文字列("key=value"形式)を入れるようにしていました.

しかし, この方法はおすすめできません. なぜなら環境変数の取得や追加, 削除などの操作に多くの手間が必要になりバグの原因になりますし拡張性が低いです. なので良い子は連結リストやハッシュテーブルなどの扱いやすいデータ構造で環境変数を保持しておき, コマンドを実行する時に文字列配列に変換する関数を作りましょう.

今回自分は連結リストで環境変数を保持するようにしました. 速度ガー! って思うかもしれませんが, 環境変数の数なんて大して大きくなることは無いはずなので問題ないと判断しました. (問題が起きそうなら別のデータ構造に変えればいいだけ)

typedef struct s_var {
    const char            *key;
    const char            *value;
    bool               is_shell_var;
    struct s_var       *next;
}                       t_var;

入力処理に関しての小話

入力処理に関してはreadlineを使ったから苦労してない的なことを書きましたが, 実は自分のチームが課題を始めたころはreadlineは使えずTermcapを使って実装する必要がありました. (Termcapの部分はtorusさんがやってくれました)

en.wikipedia.org

このtermcapがかなり曲者のようでして, 入力処理の実装はかなり苦労していました. しかし, 自分達が課題を提出直前に課題変更があり, readlineが使えるようになりTermcapを使う必要が無くなったのと, 課題要件にheredocの追加が行われ, 話し合った結果Termcapによる入力処理の実装は破棄し, readlineによる入力処理を実装することにしました.

課題変更前はTermcapによる入力処理と履歴機能と文字列編集の実装のためにロープ木)による文字列編集が実装されていました.

GitHub - torus/42-minishell at termcapありのバージョン からTermcapを使ったバージョンのコードが見れます. (heredocumentは実装されていません)

豆知識

ここではminishellをやる上で役に立つかもしれない豆知識を書いておきます. (自分用の備忘録でもある)

bashのコードリーディング

bashのコードは1996年頃に書かれていて, 現代のC言語のコードとは書き方が一部異なっており, それを知らないととても読みづらいです.

具体的には

  • インデントのサイズはスペース8
  • 古いC言語の規格では引数の型は関数ヘッダーの次の行に書く必要がある.

en.wikipedia.org

この書き方をK&Rスタイルと言うらしいです.

なのでbashのコードを読む時はエディタのインデントサイズを8にして, 古いC言語の書き方を頭の片隅に置いておくとスムーズにコードが読めると思います.

GNUフラグパーサー

echo -n -n helloecho -nnnn hello と書いた時に echo -n hello と同じ挙動をするのはGNUのフラグパーサーライブラリであるgetoptの仕様によるものである.

en.wikipedia.org

www.gnu.org

完走した感想

いやー, 長かった. 4月に課題に取り組み始めてから提出するまで約3ヶ月かかりました. まぁ3ヶ月の間全てminishellやっていたというわけではなく競プロやったりフラクタルの実装したりちょくちょく寄り道したりしてましたが, それでも大変でした.

コミット数も42の課題では初めて1000コミット超えました. まぁPRやrevertなどのコミットがいっぱい入っているので全てのコミットがコードの実装を含んでいるというわけでもないですが.

f:id:JUN_NETWORKS:20210702032135p:plain

この課題をするまでシェルというものが自分で実装できるものというイメージは全くありませんでしたが, 今回実装してみてシェルの内部での処理やUNIXプログラミングについて少し詳しくなり, シェルくらい頑張れば実装できるっしょっていう気持ちになりました.

また, 今回シェルを作ったことでこの課題に取り組む前と後でシェルに対する意識が大きく変わったように思えます. 課題に取り組む前は, シェルはブラックボックスって感じで, とりあえずなんか知らんけどコマンドを入力したら実行してくれるって感じでしたが, 今では内部でどのような処理が行われているかがわかっているためシェルを触っている時にシェルの実装側からの視点というものがわかるようになった気がします.

この記事ではあまり深堀りしてませんでしたが, cdを含むいくつかのビルトインコマンドはbashのhelpコマンドでは出てこない挙動などがあり, それを知るためにbashソースコードを読んだりもしました. コミットが25年前(1996年)とかが普通にあり, 自分より年上のコードを読むのは新鮮でした. 25年前ともなると現在のC言語の文法やインデントスタイルなどが違っていたりして読むのが大変でした.

今回始めてUNIXプログラミングと呼ばれるものを行っったのですが,「詳解UNIXプログラミング」という本がとてもとても役に立ちました.

UNIXとはなんぞやという説明からUNIXにおけるファイルの扱い, シグナルやプロセス等々...UNIXプログラミングを行う上で必要な知識がここに書かれています. この本のおかげでminishellなんとかクリア出来たと言っても過言では無いくらいに役に立ちました. (自分の中では勝手に聖書と呼んでいます)

また, 今回一緒にチームを組んだtorusさんはキャリアの長いプログラマーの方で, 多くのことを教えて頂き大変勉強になりました. 豆知識のセクションに書いてある知識はtorusさんから教えてもらったものだったりします.

あと, 提出する直前で課題が大幅に変更されたのは堪えました. 特にtorusさんはその時点で既にTermcapに関わる入出力関係のコードを数週間掛けて千行以上書いていました. しかし, Termcapでの入出力をheredocに対応させる(複数行入力対応)こととreadlineの実装に切り替えるという2つの選択肢を考えた時に, ここまで書いてきた千行以上のコードを破棄し, readlineでの実装に舵を切ったのは凄いなぁと思いました. もし自分だったら惜しくて既存のコードに固執してしまうかもしれません.

f:id:JUN_NETWORKS:20210702013616p:plain
Termcapの削除に関するPR

github.com

今回の課題は今までの課題で一番重く, 実装量も多いため記事内で全てを解説しませんでした. 具体的なコードが見たい人はGitHubリポジトリを見てください.

github.com

とても大変でしたが, やりがいと学びのある良い課題でした.

といったところで今日はこのへんで. ではでは〜〜👋👋

参考リンク

bash関係

シェル関係

パーサー関係

readline

Termcap

その他

AWS Academy Cloud Foundations 修了した

42TokyoでAWSから提供されている学生向けプログラム AWS Academy Cloud Foundations が受講可能だったので受講して修了したので完走した感想.

AWS Academy Cloud Foundations とは

AWS Academy Cloud Foundations とはAWSが学生向けに提供している教育プログラム AWS Academy のうちの1つ.

aws.amazon.com

内容としては Cloud Foundations というくらいなので基礎的な内容が多い. AWSアカウントの登録から初期設定, ネットワークの基礎知識とVPC, EC2やS3, Lambda, オートスケーリング, それらクラウドサービスを使うことによって生じるメリットと従来のオンプレミスとの比較など.

基本的に各章の構成は 動画とラボ(後で説明), PDF, 知識確認テスト という感じ.

動画は AWS Academy の人が色々解説してくれる. PDFはその動画内で使ってるスライドが見れる. 知識確認テストはAWS認定試験の一部問題を抜粋しているっぽかった

で, ラボなんだけど, これがめっちゃ良かった. このラボというのはAWS側が学生用に一時的なAWSサンドボックス環境を提供してくれて, そこで試せるって感じ.

個人でAWSを試しに触ってみるってセキュリティ対策やら請求額のモニタリングとアラームとか何も知識が無い初学者には少しハードルが高い気がするので, こういう環境でお金やセキュリティのことを心配せずにAWSのサービスを実際に触れるのはとても良いと思った.

完走した感想

自分は昔バイトでMLOps用にAWSアーキテクチャを設計したことがあり, AWSを全く触ったことがないというわけではなく, このコースの範囲なら割と知っている内容が多かった. でもちょくちょく知らないサービスがあったり, なんとなく使い方までは知っているけど他サービスとの違いとか新しいことを知れたので良かった. あと, 単純にここ1年くらいAWS触ってなかったので復習にもなって良かった.

このコースはAWSを触ったこと無い人にとっては最高の教育プログラムだと思った. ラボの説明のところでも書いたけど, AWSをいきなり一人で触ると請求アラームの設定やIAM垢の設定などが大変だと思うので, 個人で触る前にこういうコースである程度AWSの概要とある程度のベストプラクティスを知ってから触ると安心してAWS触れそうだし, 始めの第一歩としてこのコースはとても良いと感じた.

ただ, ある程度AWSでの設計や運用をしたことある人からしたら知ってることが多くて物足りないかも? (まぁ Cloud Foundations コースなのでそりゃそうですが)

個人的にはAWSアーキテクチャの設計について深く知りたかったなぁと思ったら, AWS Academy Cloud Architecting というコースが Cloud Foundationsコース の次にあるらしく, 恐らくこれがアーキテクチャ設計とかに関してのコースだと思う.

AWS Academy Cloud Architecting

この中級レベルのコースでは、AWS で IT インフラストラクチャを構築するための基礎を学び、学生が AWS 認定ソリューションアーキテクト – アソシエイトの認定を取得するために必要なスキルを習得するのに役立ちます。このコースには、講義やハンズオンラボ、およびプロジェクト作業を通じて配信される約 40 時間のコンテンツが含まれています。

学生には、このコースを受講する前に、AWS Academy Cloud Foundations または同等のコースを受講することをお勧めします。

AWS Academy

まぁ, てな感じでAWSの復習と少し抜けていた知識などが補填出来て満足でした.

後Certificationバッジがもらえてそれがカッコよくて良いです.

という感じで AWS Academy Cloud Foundations を楽しく修了しましたよーというお話でした.

ではでは今日はこのへんで. ばいばい〜👋👋

フラクタル((マンデルブロ|ジュリア)集合)生成プログラムを書いた

42の課題でフラクタル(マンデルブロ集合とジュリア集合)を描画する課題があり, それが完了したので感想とか色々.

フラクタルとはなんぞや

Wikipediaによると

図形の部分と全体が自己相似(再帰)になっているものなどをいう。

フラクタル - Wikipedia

らしいです.

以下のようなやつとかですね.

Sierpinski zoom.gif
I, Avenafatua, CC 表示-継承 3.0, リンクによる

まぁ他にもフラクタルはいくつか種類があったり, 数学的な定義とか色々ありますが, まぁズームしていくと終わりが無くどんどん図形が出てくるやつのことです.

So Doge. Much fractal.
imgur.com

マンデルブロ集合

で, マンデルブロ集合 (Mandelbrot set) とはなんぞやという話ですが, マンデルブロ集合とは以下の漸化式が  n \rightarrow {\infty} で発散しない集合のことです.


    \begin{cases}
        {Z_{n+1} = Z_{n}^2 + C}\\
        {Z_0 = 0}
    \end{cases}

ここで  Z C複素数の式  a + bi です. また,  C複素数平面上の座標に対応しています.

マンデルブロ集合のわかりやすい説明は以下の動画とサイトがわかりやすいです.

www.youtube.com

azisava.sakura.ne.jp

で, 実装するときには  n \rightarrow {\infty} が発散するかどうかを判定しようとすると永遠に終わらないので, 適当に  n \rightarrow 100 とかにします. また, 発散するかどうかの判定は  |Z_n|が2を超えなければ集合に入っているということにします.

なんで2にしたかというと, マンデルブロ集合が実数, 虚数共に-2から2の範囲にあるからです.

で, これをコードとして書くと以下のような図が出てくるわけです.

f:id:JUN_NETWORKS:20210612144640p:plain

これを拡大していくと再帰的にどんどん色んな形が描画されていくのです.

https://user-images.githubusercontent.com/26608037/121766483-f454f300-cb8c-11eb-8718-dca049b76985.gif

github.com

ジュリア集合

ジュリア集合は基本的なコンセプトはマンデルブロ集合と同じです. 違う点は,  Z C の扱いで, ジュリア集合では  Z複素平面上の座標に対応させ,  Cが定数となっています.

以下の動画がめっちゃわかりやすいので見ると良いです.

www.youtube.com

たとえば  C=0.4-0.325i とすると以下のような形が出てきます.

f:id:JUN_NETWORKS:20210612145154p:plain
C=0.4-0.325i

 C=-0.8+0.156i だと以下のような形が出る.

f:id:JUN_NETWORKS:20210612145752p:plain
C=-0.8+0.156i

こんな感じで Cを変えると Cの値によって色んな形が出現します.

今回自分はマウスの座標によって Cの値を変えれるようにしました.

https://user-images.githubusercontent.com/26608037/121676176-4ba48600-caef-11eb-901c-ffa427d6c0a3.gif

はい. かっこいい.

バーニングシップ

課題のボーナスで「更にもう一個別のフラクタル作りなはれ」というのがあったのでバーニングシップ(Burning Ship)というのを作りました.

en.wikipedia.org

www.youtube.com

基本的なコンセプトはマンデルブロ集合と同じなのですが, イテレーションごとに行う計算( Z_{n+1}を求める計算)が少し違います.


    \begin{cases}
        {Z_{n+1} = (|Re(Z_n)| + i|Im(Z_n)|)^2 + C}\\
        {Z_0 = 0}
    \end{cases}

イテレーションごとに行う計算でそのまま2乗するのではなく, 絶対値を取るのがマンデルブロ集合との違いです.

これを実装して描画すると以下のような図形が出てきます.

f:id:JUN_NETWORKS:20210612154839p:plain

燃えてる船(Burning Ship)っぽいですね.

これを拡大していくと

https://user-images.githubusercontent.com/26608037/121768051-03d93980-cb97-11eb-9252-adf67edd0b29.gif

再帰的にどんどん船の形が出てきますね! かっこいい!

ただ, バーニングシップに関しては深くズームしまくると途中で行き止まりに当たるんで実装が正しくない可能性があるかも.

色付けに付いて

マンデルブロ集合, ジュリア集合, バーニングシップ は実装自体は難しくないです. ただ, 美しく描画するとなるとむずいんすよね...

今回の課題でも一応 color range shift を実装するという項目があったので, 単純にイテレーション回数に応じてHSVの色相(Hue)を変えるというので実装していて, 綺麗ではあるんですがYouTubeとかに上がっている動画の方みたいに綺麗なものを実装するのはなかなか難しそうです.

f:id:JUN_NETWORKS:20210612162636p:plain
自分の実装

www.youtube.com

JSr07885.gif
By Maxter315 - Own work, CC BY-SA 4.0, Link

Wikipediaマンデルブロ集合の色付けについての記事があったので見てみたのですが, 色付けって奥が深いですね...

en.wikipedia.org

完走した感想

完走した感想ですが, 楽しかったです(小並感).

マンデルブロ集合, ジュリア集合の描画に関しては1日で実装できましが, マウスのカーソルの場所に向かってズームする処理(Google map的なアレ)がくっそむずかったです.

というのも最初はズーム倍率と中心座標を保持してその値を変えることによって実現させようと思ったのですが, まる一日やっても上手くいかず, 結局ggったり他の人のコード読んだりして最終的には描画する左右上下両端の値(min_re, max_re, min_im, max_im)を保持し, それらを使って描画するようにしました. そこにマウスのウィンドウサイズからの相対座標を使って掛けたり割ったりしてうまいことズームしたり平行移動したりするようにしました.

あと, ループ内で変数代入するタイミングをミスってデバッグに1日溶かしました.

とか色々あって大体4日くらいかかりました.

この課題以外にも2Dゲームの課題とかがあったのですが, ジュリア集合のGIFアニメーションがかっこよすぎたのでこの課題にしました.

マウスで Cの値を変動させるというのは課題要件に無いので別にやる必要はなかったのですが, かっこいいを求めてやりました. 結果的にはかっこよくなったので大満足です.

この課題はそこまで重くない課題なので最初は記事を書くモチベはさほどなかったのですが, 実は提出するのをやらかしてLinterに引っかかって0点を食らったので供養のために書いていたりしますw

f:id:JUN_NETWORKS:20210612165431p:plain

ちゃんと課題提出前に確認するのと, 眠い時はちゃんと寝ましょう.

それではまた次の記事でお会いしましょう. ではでは〜👋👋

GitHub PullRequest を簡単にローカルにfetchできる設定

github の PullRequest を簡単にローカルに落とせる設定を書いたのでメモ.

設定

~/.gitconfig に以下の内容を追加する

[alias]
  pr = "!f() { if [ !${2+x} ]; then git fetch origin pull/${1}/head:pr/${1} ; else git fetch ${2} pull/${1}/head:pr/${1} ; fi }; f"

何をしているかというと,

  • 引数が1つの場合は origin から${1}番プルリクエストを pr/${1} という名前でfetchする.
  • 引数が2つの場合は ${2} からfetchする. それ以外は引数が1つの場合と一緒.

ホントは引数1つの場合, origin ではなく デフォルトのリモートリポジトリにしたかったんだけど, デフォルトのリモートリポジトリ名の取得方法がわからんのでな... (.git/config を解析して情報取り出せばいけると思うけど)

自分の.gitconfig は以下のリンクから見れます.

github.com

使い方

git pr {PR番号} という風に実行すれば良い. 例: git pr 73

また, origin以外から取得する場合は git pr {リモートリポジトリ名} {PR番号} とすればできる. 例: git pr remote2 73

f:id:JUN_NETWORKS:20210430214029p:plain

参考にしたサイト

qiita.com

参考にしたというか, この記事のコマンドを簡単に使えるようにした感じ.

「Winny 天才プログラマー金子勇との7年半」を読んだ

Winny 天才プログラマー金子勇との7年半」という本を読んだので感想.

金子勇については多くの記事があるので, 気になる人は以下の記事などを読んでみてください.

wired.jp

www.newsweekjapan.jp

感想

この本は2004年から2011年の約7年間に渡って行われたWinny裁判についての本である.

ja.wikipedia.org

この本の中で金子勇という人物の人物像や経歴, 思想などが垣間見えたが, 本当に優秀なプログラマーだったんだなぁ と思うと同時に, こんなに優秀な人間を日本のおかしな司法が潰してしまったのかと悲しくなってしまった.

家宅捜索から事情聴取, 裁判中にいたるまで如何にに京都府警と京都地裁が狡い手を使い, 金子勇を罪人と陥れようとしていたのが見えて胸糞が悪かった. 日本の刑事裁判の起訴後有罪率は99.9%と言われているが, この数字はこのような異常な取り調べによるものなんだなだとしたら日本の司法制度は相当狂っていると感じた.

また, 本書は裁判やその周辺について時系列順で語っているのだが, その中で金子勇が裁判に時間を費やしている中で世間ではiTunesYouTubeが誕生し, P2PをベースとしたSkypeが誕生し, mixiからTwitterに移行し, と裁判に拘束される彼を余所に時代が流れ, 技術が進歩していくのが残酷だった. もし, 彼がこの7年間を裁判のためではなくコードを書くことに使っていたらどうなっていたかなど誰にもわかりはしないが, 少なくとも今のようなアメリカの後追いをするだけの日本ではなく, ソフトウェアに関するいくつかの分野で最先端をいくような未来があったのかなと思ってみたりした.

このWinny事件もそうだが, この事件にに限らず, 自分が知っている近年の事件でも, 「アラートループ事件」や「Coinhive事件」などがあり, 日本の司法や警察は本当に何も学んでいないんだなと思った.

ja.wikipedia.org

ja.wikipedia.org

金子勇が後継の技術者のために7年という時間を費やして戦ってくれたのに, 日本の司法行政は何も変わっていなくて悲しい気持ちと同時に正直諦めの気持ちがある.

また, 日本国内で何かしらの成果物を公開する際, 特にそれが最先端の技術を含む場合には Coinhive事件 と同じ道を辿る可能性がある(逮捕されるかもしれない)ので, 日本国内でコードを書くなら最低限被疑者となった際の権利や原則, それらに関する法律や憲法などは頭に入れておいた方が良いと思った.

ascii.jp

www.atmarkit.co.jp

日本国内でコードを書いていたらある日突然逮捕されるというのは冗談ではなく本当にありえることだと思うので, 一度上記の記事のどちらかを軽く読んで頭の片隅においておくと実際に逮捕された時に少しは役に立つかも知れません. (逮捕されないのが一番ですが...)

結局「出る杭は打たれる」というのが日本なのだと思った. それと同時に, 本当に優秀な人, 特に新しい技術 の研究開発を行っている人は日本ではなく, 人類のために予算が潤沢で新しい技術などに理解がある(と自分は思っている)米国などで研究開発してほしいという自分の個人的な意見がさらに強くなった.

完走した感想

という感じで「Winny 天才プログラマー金子勇との7年半」を読んだ感想でした.

この本はWinny事件の裁判に対する弁護士側からの視点の本でしたが, コードを書く開発者側の人間としてはWinny自体に興味があったりするので, 本書の中でも言及されていた金子勇が裁判のために書いた本「Winnyの技術」というのがあり, こちらはWinnyのプログラムやそれに使われている技術について書かれているようなのでまた今度読んでみようと思う.

Winnyの技術

Winnyの技術

本書及びこのこの裁判は "駄目な司法が天才プログラマーを潰す" という読んでいて気持ちの良いものではないけれど, 日本の情報技術の発展ために戦ってくれた偉大なプログラマーについては少し知っておくべきではないだろうか. 是非興味があったら読んでみてください.

では今日はこのへんで. ではでは〜〜👋👋