rustlingsでRustの基本的な読み書きに慣れる

Rustことはじめの一環として、GoでいうところのA tour of Goに相当するものがRustでもないのだろうかと考えていた。そこで、rustlingsというRustの基本的な読み書きに慣れるための良さそうなエクササイズ集がGitHubにあることを知り、早速トライしてみることにした。

github.com

使ってみる

リポジトリのREADMEでガイドされているOS毎のインストール手順を行ったら、コマンドラインからrustlingsのディレクトリに移動する。rustlingsのディレクトリ内には、コンパイルエラーを誘発する不正なrsファイルが沢山含まれており、それら一つ一つが問題である。

rustlings watchで起動することで、ターミナル上に(特定の問題の)エラーメッセージが表示されるので、該当する問題のrsファイルをVS Codeのようなエディタで開きデバッグを行っていくのが一連の流れ。

回答の手順

例えば以下の問題についてのエラーメッセージが表示されていたとする。

// variables3.rs
// Make me compile! Execute the command `rustlings hint variables3` if you want a hint :)

// I AM NOT DONE

fn main() {
    let x = 3;
    println!("Number {}", x);
    x = 5;
    println!("Number {}", x);
}

これはJavaScriptのような言語に慣れ親しんだ人からすると、一見正常なコードに見えるかもしれないが、Rustの場合だとコンパイルエラーとなる。おそらく、以下のようなエラーメッセージが表示されるはず。

f:id:p0ny:20200322225844p:plain

Rustは変数の宣言を行う際にmutというキーワードでミュービリティを宣言しない限りは、その変数の束縛を変更することが許可されない(デフォルトでは変数の宣言時にはすべてイミュータブル)。したがって、最初のxの変数宣言時にmutを含める必要がある。

let mut x = 3;

エラー箇所を修正すると、rustlingsがコードの変更を自動で検出して正誤判定をしてくれる。正答した後は、// I AM NOT DONEコメントアウト箇所を削除することで、次の問題をrustlingsがガイドしてくれる。

もし、問題がわからない場合は以下のコマンドを実行することでヒントが表示される救済措置もある。

rustlings hint exercise_name

ちなみにローカルで環境を構築するのが面倒な人向けに、Rust Playgroundを使ったWEB版もある。

雑感

現在、rustlingsの全項目のうち大体7割ほどの問題を解きおえた。rustlingsは言語機能毎に問題のセクションが分かれており、なおかつ難易度順に問題のガイドを行ってくれるので、Rustビギナーのステップアップのための教材としてはこの上なく最適だ。

Rustについてはまだ触り始めて間もないということもあり、コンパイルを通すので精一杯というのが正直なところ。個人的にRustはコンパイルエラー時のメッセージがかなり丁寧且つ的確なので、毎回のコンパイルエラー時に学びがある所がとても気に入っている。

rustaceanを目指してどんどん問題を解いていこう!🦀

CourseraのThe Bits and Bytes of Computer Networkingの受講を終えた

CourseraでGoogleが提供しているITサポート専門家の養成を支援するためのトレーニングコース、The Bits and Bytes of Computer Networkingの受講を終えた。このコースはネットワークがテーマであり、前提知識は一切無くても受講することが可能である(但し言語はすべて英語、英語字幕アリ)。

www.coursera.org

コース内容

コースは全6週で構成される(なので大体2ヶ月が修了の目安である)。1つの動画は大体5分から10分ほどで視聴できるようになっている親切設計。そして各週の最後に理解度チェックのための確認テストがある。今回は課金をせず無料受講を選択したため、一部のリソースにはアクセス出来なかったが特に支障はなかった。

各週で取り扱うテーマは以下のとおり。

Week1 - Introduction to Networking

  • The TCP/IP Five-Layer Network Model
  • The Basics of Networking Devices
  • The Physical Layer
  • The Data Link Layer

Week2 - Network Layer

Week3 - Transport and Application Layers

  • The Transport Layer
  • The Application Layer

Week4 - Networking Services

  • Name Resolution
  • Dynamic Host Configuration Protocol
  • Network Address Translation
  • VPNs and Proxies

Week5 - Connecting to the Internet

  • POTS and Dial-up
  • Broadband Connections
  • WANs
  • Wireless Networking

Week6 - Troubleshooting and the Future of Networking

  • Verifying Connectivity
  • Digging into DNS
  • The Cloud
  • IPv6

まずはOSI参照モデルを基本として、物理層から順にその仕組みについて辿っていき、その後はDNSDHCP、NAT、VPNとプロキシについて学ぶ。ネットワークの接続方式についてもカバーされている。そして、コースの終盤にはIPv6クラウドといった最新のネットワーク技術、dignslookupといったコマンドを使ったトラブルシューティングのHow toについても触れられている。

参考書籍

当初は補助教材として、この分野ではド定番とも言えるマスタリングTCP/IP 入門編を読もうと思ったが、無理に背伸びはせず平易に書かれていそうな書籍を幾つか選んだ。

絵で見てわかるITインフラの仕組み 新装版

絵で見てわかるITインフラの仕組み 新装版

また、コースで躓いた際に非常に役立ってくれたオンラインリソースも追加で載せておく。

www5e.biglobe.ne.jp

感想

さすがにこのコースを一巡しただけで「ネットワークを完全に理解した!」とはならないが、もし今後ネットワークで分からない事があれば、まずはこのコースのどこかにその答え、あるいはそのための糸口があるのではないかと思えるほど充実したコース内容であった。また、ネットワークの知識については日々断片的に仕入れてはいたものの、どこかでそれを体系的に整理、あるいは束ねてくれるような機会を欲していたので、このThe Bits and Bytes of Computer Networkingはその最良の機会となってくれた!

1. Two SumのRustの解答を読み解く①

今年はRustをじっくりと学びたいと思っていたので、LeetCodeのHello worldとも言うべき問題Two SumをRustで書くとどうなるのだろうか、とふと思った。

当の問題の解法(最適なアルゴリズム)は既に知っているので、では言語の学習に、と全く0の状態からガイドを見ながら解いてみることにした。しかしながら、かなり厳格な言語であるようで、全くコンパイルが通らずエラー地獄となってしまった。

そこで、Discussion Forumで掲載されていた解答コードのリーディングを行うことにした。

1. Two Sum

leetcode.com

数値を含んだ配列とtargetという数値が与えられるので、配列内の2つの数値を足し合わせた値がtargetに等しくなる場合を探る。同じ数値を二度使うことは不可で、こうしたtargetに等しい組み合わせが最低でも1つあることが保証されている。そして、それぞれの足し合わせた数値のインデックスを配列にして返すことが期待される。

Brute Force

いわゆる二重ループを用いて解く方法。おそらくLeetCodeでこの問題を初めて解く場合、大半の人がこのアプローチを取ると思う。ひとときのAC(Accepted)に安堵してしまい、後々この問題の本質の価値に気付く、というのは多くのLeetCoderが経験するお約束のパターン。

時間計算量は言わずもがなO(N^{2})。空間計算量は O(1)

このトピックで掲載されていたコードをそのまま引用する。

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        for ind in (0..nums.len() - 1)
        {
            for comp_ind in (ind+1..nums.len())
            {
                if nums[ind] + nums[comp_ind] == target
                {
                    return vec![ind as i32, comp_ind as i32];
                }
            }
        }
        return vec![0;2];        
    }
}

今回は、ループ、ベクタ、キャストの3つについて取り上げたい。

ループ

Rustのループはloop while forの3つがあるようだが、そのうちの1つforループの処理については、以下のように記述することができる。

for x in 0..10 {
    println!("{}", x);
}

0..nと書けるのが特徴で、Pythonでいうところのrange(0, n)だ。forループといえば、以下のような記述が標準だけど、どうやらRustでは非推奨らしい。Pythonに慣れ親しんだ自分としては少し助かる。

for (x = 0; x < 10; x++) {
    printf( "%d\n", x );
}

理由は以下のとおり。

Rustでは意図的に「Cスタイル」 for ループを持ちません。経験豊富なC開発者でさえ、 ループの各要素を手動制御することは複雑であり、また間違いを犯しやすいのです。

せっかくなので、if文を少し調べつつFizzBuzzを書いてみた。

fn main() {
    for i in 1..101 {
        if i % 3 == 0 && i % 5 == 0 {
            println!("{} : {}",i, "FizzBuzz!")
        } else if i % 3 == 0 {
            println!("{} : {}",i, "Fizz!");
        } else if i % 5 == 0 {
            println!("{} : {}", i, "Buzz!")
        }
    }
}

https://doc.rust-jp.rs/the-rust-programming-language-ja/1.6/book/loops.html

ベクタ

ベクタとは、動的あるいは拡張可能な配列である(PythonのリストやGoのスライスに相当)。vec!というマクロによってベクタの生成が可能。今回は入力で与えられたベクタ、numsのサイズを取得したいので、len()を呼び出している。

以下、サンプルコード。

fn main() {
  let v = vec![1, 2, 3, 4, 5];
  println!("{}", v.len()) // 5
}

std::vec::Vec - Rust

型のキャスト

asによって型を安全にキャストすることが可能。今回は出力の形式がVec<i32>で関数内で指定されているので、ベクタ内の要素の型はi32にする必要がある。i32は32ビットの符号付整数型。

以下、サンプルコード(型を呼び出すメソッドについては省略)。

use std::any::type_name;

fn type_of<T>(_: T) -> &'static str {
    type_name::<T>()
}

fn main() {
  let x: i32 = 5;
  println!("{}", type_of(x)); // i32

  let y = x as i64;
  println!("{}", type_of(y)); // i64
}

as - Rust

次回はもう一つのアプローチ、ハッシュマップを用いたアルゴリズムの場合のコードについて、リーディングを行いたい。

余談

このコードの実行速度は36 msでメモリ使用量は2.2MBだった。

ハッシュマップを用いたO(N)アルゴリズムアプローチを用いてPythonで提出した結果が履歴に残っており、実行速度は48 msでメモリ使用量は14.1 MBであった。Rustがいかに高速な言語であるということを思い知らされる!(インタプリタ言語とコンパイル言語を比較するのはやや不適切な気もするけど...)

参考

doc.rust-jp.rs

49. Group Anagramsを解いた

49. Group Anagrams

leetcode.com

文字列を含んだ配列が与えられるので、アナグラムが同一の文字列でグルーピングする。

My Answer

時間計算量はO(n * mlogm)、空間計算量はO(n * m)となった。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = {}
        for s in strs:
            sorted_s = "".join(sorted(s))
            if sorted_s not in dic:
                dic[sorted_s] = [s]
            else:
                dic[sorted_s].append(s)
        return [dic[s] for s in dic]

与えられた文字列を(アルファベット順に)ソートし、ソートした文字列をKeyとして辞書に格納していく。後は、辞書からそのまま取り出した値を指定の配列の形で返してやればよい。

実行速度は100 msとなり、全体の72.20 %の参加者より速い結果となった。

Best Answer

Categorize by Count

解説のページを見ると、さらによいと思われるアプローチが存在した。アルファベットを0から25の数字に対応付けて、それらの出現回数をカウントしたものをキーとする。

https://leetcode.com/problems/group-anagrams/Figures/49_groupanagrams2.png

サンプルコードは以下のとおり。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = collections.defaultdict(list) 
        for s in strs: # n
            count = [0] * 26 # m
            for c in s:
                count[ord(c) - ord('a')] += 1
            ans[tuple(count)].append(s)
        return ans.values()

自分が提出したコードのソートのO(mlogm)の処理部分をO(m)に置き換えることができるので、若干の改良が見込める。

また、サンプルコードからは以下のTipsが得られた。

  • アルファベットを数字で対応付けたいときord("a")から差分を用いる。
  • defaultdict(type)を使って辞書を生成することで、キーの存在の有無の判定を省略することができる。
  • values()dict_valuesのクラスを返す。例えば今回はlist(hoge.values())などでreturnすることも可能。

参考

qiita.com

note.nkmk.me

997. Find the Town Judgeを解いた

997. Find the Town Judge

leetcode.com

町にN人住んでおり、彼らは1からNの数字でラベリングされている。 この中に一人だけ裁判官がいるという噂があるので、それを特定する。

裁判官が存在する場合の条件は以下のとおり。

  1. 裁判官は誰も信じない
  2. (裁判官を除く)全員が裁判官を信じる
  3. この1.と2.を満たす人が1人だけいる

trustという配列が与えられ、trust[i] = [a, b]aはbを信じるということを意味する。上記条件が満たされる場合はそのラベルを返し、それ以外の場合は-1を返す。

Example 5:

Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]

Output: 3

My Answer

以下のようなコードになり、2回目の提出でAC(Accepted)が出た。時間計算量はO(n+t)、空間計算量はO(n)となる。

class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        ppl = set()
        score = [0 for i in range(N)]
        for i in range(len(trust)):
            ppl.add(trust[i][0])
            ind = trust[i][1]
            score[ind-1] += 1 
        if len(ppl) == N:
            return -1
        maxNum = max(score)
        if score.count(maxNum) == 1:
            return score.index(maxNum) + 1
        return -1

実行速度は780 msとなり、全体の85.63 %の参加者より速い結果となった。単純な英語力不足から、問題の意味を正しく理解するのに時間がかかってしまった。最終的に、問題を翻訳していて上記コードはたまたまACしているだけと気付いた。

Best Answer

この問題の解答はプレミアム会員でないと閲覧することができなかった。こういう時は大抵問題についてのディスカッションフォーラムを参照するかYouTubeにある解説動画を探すようにしている。

www.youtube.com

動画内の説明はJavaで記述されていたので、Pythonで書き直した。

class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        count = [0] * (N+1)
        for t in trust:
            count[t[0]] -= 1
            count[t[1]] += 1
        for i in range(1, N+1):
            if count[i] == N-1:
                return i
        return -1

裁判官は誰も信じないので、信用する側を-1で調整するというアプローチ。そして、2回目の線形探索でN-1と一致するのであればそいつが裁判官だ。実行速度結果は812 ms(42.32%)になってしまったが、コードはかなりすっきりしたこともあり、こちらの方が解答としては望ましいだろう。

338. Counting Bitsを解いた

338. Counting Bits

leetcode.com

非負整数numが与えられるので、0からnumまでのiについて、2進数に変換したiに含まれる1の数を数えていき、それらを配列にしたものを返すことが求められる。

Example 1:

Input: 2

Output: [0,1,1]

注意点としてはFollow upとして時間計算量をO(n)で解くことを、ベストソリューションとして求められている点である。

Brute Force

初回の提出は、以下のようなコードになった。これは上記のFollow upを無視した解答であり、計算量はO(n*sizeof(integer))となる。

class Solution:
    def countBits(self, num: int) -> List[int]:
        res = []
        for i in range(num+1):
            res.append(str(bin(i)).count("1"))
        return res

実行速度の結果は92 msとなり、これは全体の45.81 %の参加者より速い結果となった。

ボトルネックとなっているのはcount()を使用している部分であると推察した。文字列に特定の文字がいくつ含まれるかという操作は、線形探索O(n)であるので、iの数が大きくなるにつれ計算量は増加してしまう。これをどうにかしたい。

Optimize

最終的に以下のようなコードとなった。任意の数字までを2進数表記したものを紙面上に書き出して眺めていると、bitの桁数が増加することで1の数は1つ増加することに加え、その桁数で表現できる数値範囲は、1つ前の桁数の数値範囲に依存することがわかった。直前の結果を再利用することができるので、DP(Dynamic Programming)の適用が考えられる。

class Solution:
    def countBits(self, num: int) -> List[int]:
        res = [0, 1]
        if num == 0:
            return [0]
        if num == 1:
            return res
        count = 2
        lim = 2
        ind = 0
        
        while count != num + 1:
            if lim == ind:
                lim *= 2
                ind = 0
            res.append(res[ind] + 1) 
            count += 1
            ind += 1
        return res

実行速度の結果は80 msとなり、これは全体の84.49 %の参加者より速い結果となった。劇的な実行速度の変化は生じていないが、他との比較値を見てみると十分に改善が行われたのではないだろうか。

デューク大学の「Java Programming: Solving Problems with Software」を修了しました

オブジェクト指向について本格的に学ぶために、以下のコースを受講しました。

 

www.coursera.org

  

ちなみに、全4コース構成となるため、今回のコースはオブジェクト指向についてはあまり触れられておらず、現在受講している第2コースの「Java Programming: Arrays, Lists, and Structured Data」でようやく話が出た程度です。

 

コース難易度は初心者向けと設定されていますが、全くの未経験者がこの講座から学習をスタートするのはおすすめしません。現にレビュー欄でも、初学者には難しすぎるといった意見も見受けられました。


各セクションの課題では、0からクラスファイルを作成する必要があります。大まかな全体設計の指示は入りますが、それでも大半のコードを自分で記述しなければならず、試験パートでは、課題で作成したプログラムを実際に実行させて回答をする必要があるため、きちんと動作しなければ次の週へ進むことができません。

自分がこれまで受けてきた講座では、あらかじめスクリプトが与えられておりその中の一部のコードを書き換えるものや、作成した一つの関数のみを提出するといった比較的ライトな課題が多く、受講当初は非常に負荷が大きかったことを覚えています。良い感じに補助輪が外せてきたということでしょうか。


自分はこのコースを受講するにあたって、以下のコースとオンラインクイズが前提知識として役立ちました。


・少なくとも1つのプログラミング言語について学ぶ

www.coursera.org

 

参考:Pythonを0から学びたいなら、ミシガン大学のPython for Everybodyという講座がおすすめ

 

Javaの肩慣らし

codingbat.com

 

参考:CodingBatに取り組んでいます

 

 

内容

- 1週目:イントロダクション&Javaの構文とセマンティクス

おなじみのHello World!からになります。この週のみでJavaの基礎の殆どをカバーするという中々のスピードっぷりです。Pythonでこうした基礎はある程度理解していたものの、そもそもクラス、インスタンス化とは何ぞや?という状態だったので、イントロダクションにも関わらず全週のなかで一番時間がかかりました。

 

- 2週目:Javaの文字列

おなじみ文字列操作です。Javaの実行においては環境構築をする必要はなく、BlueJという統合開発環境を用います。ただこのBlueJ、あまり評判がよろしくなく、自分の場合は主にVS Codeで課題を進めることが多かったです。


- 3週目:JavaCSVファイルと基本統計

以下のパッケージを使用して、CSVファイルを呼び出し、そこから任意の情報を取り出すプログラムを作成します。

 

www.dukelearntoprogram.com

 

- 4週目:ミニプロジェクト:赤ちゃんの名前

いわゆるキャップストーンプロジェクトになります。

 

雑感

このコースを受講してよかったと思えるのが、これまではやや座学中心でパッシブな講座が多かったのに対して、完全に課題が中心となってカリキュラムが進むので、各週に乗り越えるべき壁がきちんと設けられていたことです。自分で考えなければいけない部分がこれまでのコースに比べて格段に増え、最初は時間はかかりましたが良い感じにステップアップをすることができました。

 

ではでは。