カテゴリー: Kotlin

LeetCodeでプログラミング学習

この記事は最終更新から3ヶ月以上が経過しています。情報が古い可能性があります。

最近LeetCodeというサイトを利用してプログラミングの学習をしている。学習と腕試しと頭の体操を兼ねてというのが正確なところだろうか。

自分の中では頭の体操的な位置づけが大きい。設定された問に対して、どうやったら解けるか自分で考え実装してみる。実装の過程で、ついでにKotlinの勉強にもなったらなぁなんて感覚である。

そう、Kotlinで解いている。つい最近も、groupingByなるメソッドが用意されていることを知ったが、問題を解いている最中にこういった新たな発見に出会えるかもしれないというのが、Kotlinの勉強にもなるかなあと思っている所以である。

競技プログラミングという観点で見れば、日本語でできるAtCoderが有名だろう。こっちのほうが計算量やら書いたプログラムの効率性をちゃんと測れて良いと思う。LeetCodeでも処理時間は出るが、Kotlinで解いた場合、同じコードでもSubmitするたびに100msくらいの誤差が出る場合があって、まったく指標として役に立たない。ついでにKotlinで解いている人は少ないのか、提出されたコードの100%より早いです=自分が初めてKotlinで提出した、なんてパターンがあってさらに指標にならない。

そもそも競技プログラミングとしてやっているというよりは、先にも書いたとおり、私の場合は学習のためという面が大きい。その観点で見ると、LeetCodeは英語であることを除けばやりやすかった。AtCoderだと標準入力から入力を読み取る部分からやらないといけないのに対して、LeetCodeは引数として渡ってくるので純粋に解法に集中できるのが良かった。あとはAtCoderだとKotlinのバージョンが1.0.0で、対してLeetCodeが1.2.50だったというのも理由の1つではある。

英語であることは、障壁というよりは英語の学習にもなっていいかもしれないと考えている。英語の学習とはならなくとも、英語に慣れるのに役に立つだろう。ちなみに問題によっては英語が理解できずにそもそも解く以前の問題で詰まってしまうこともあるけれど、そういう場合は他の理解できる問題をやるようにしている。

LeetCodeのいいなと思ったところは、問題を解く以外にも学習用コンテンツがあることが挙げられる。

例えばIntroduction to Data Structure – Binary Treeは二分木についてのコーナーである。一部は課金しないとアクセスできないが、無料でもできる部分がいくつかある。

各ノードを巡回するにはどうしたらよいかという問いにすら苦労するのだが、だからこそ勉強になる。わかるわかる、再帰使えばいいんでしょと思っても、実際に適用しようとすると手が止まってしまった。

これに限らないのだが、再帰処理をすれば解けそうという場合に、どこからどこまでが再帰処理に必要なのかがすぐに言語化できない。だからなかなかコードに落とせない。LeetCodeをやったからと言ってすぐに言語化できるようになるわけではないのだが、実際に問題に直面して解くという経験を通じて徐々に理解を深めていけたらいいなぁと思っている。

そういえば感覚で理解しているといえば、lambda式も結構感覚で使っている。こう書いたらこうなるんでしょというノリで使っているということか。

こういう問題には自分でアプリを作るだけではなかなか出会えないので、こういうサイトを利用して学習するのもよいのではないかなと思う。

問題の探し方

私はProblems→Difficultyで難易度選択、Listsで「Top 100 Liked Questions」にチェックを入れてフィルタリング、その上でSolutionつきの問題を解くようにしている。

問題の質は玉石混交で「なんやねんこれ」というような問題もあったりする。likeが多い問題はそれだけ勉強になると思った人や面白いと思った人が多いということになる。さらに解説付きであれば解法の勉強にもなるだろうからなおおすすめである。

Solutionがないやつは、ディスカッションで他の人の解法を見ることも可能ではあるが、解説になっているとは限らないのでSolutionつきのものを選んでいる。

KotlinのgroupingByについて調べてみた

この記事は最終更新から3ヶ月以上が経過しています。情報が古い可能性があります。

KotlinにgroupingByなる関数があることを知った。

https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/grouping-by.html

Groupingソースなるものを作成するための拡張関数で、listとか配列で使うことができる。

https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-grouping/index.html

例えば”I have a pen”で各アルファベットが何回出現しているかを調べるのに使える。

val result = "I have a pen".groupingBy { it }.eachCount()
println(result) // {i=1,  =3, h=1, a=2, v=1, e=2, p=1, n=1}

groupingBy自体は続く関数オブジェクトで求められるkeyを元にしたMapへ集計できるようにするためのインターフェースで、これ自体呼び出しても何も起こらない。上記の例でいうとeachCount()を呼び出して初めて集計が行われる。

groupByとの違い

keySelectorを引数に取るのはgroupBygroupingByも同じ。

groupByだと指定したkeyごとの要素をListにもつMapを返す。イメージ的にはmapに近い処理。

groupingByはそれ自体は何もしない。keyを元に集計処理を行うインターフェースを用意するだけのメソッドなので、その後に別途集計処理が必要になる。forEachを拡張したものと考えるといいかもしれない。

両者の使い分けは、keyを元にした要素のリストがほしいのか、それともその要素を何らかの処理をして集計した結果だけが欲しいのかで使い分けることになるだろう。集計した結果のみが必要なのであれば、その中間形態であるkeyごとの要素リストは不要なので、groupingByを使ったほうが効率的である。

集計処理

groupingByだけでは集計処理は行われないので、その後に以下のいずれかを利用して集計を行う。

  • aggregate
  • fold
  • reduce
  • eachCount

それぞれ別にxxxToという処理も用意されていて、違いは集計先のMapが指定できるかどうか。Toがついている方は、既存のMapが集計先に利用されるので、前の集計結果にさらに付け足すのに使える。Toがつかない方は空のMapが集計先として利用される。

groupingBy自体は要素のグルーピングを行うわけではなく、aggregateなどを呼び出すことで初めて要素のグルーピングと集計が行われる。

fold / reduce / eachCount の使い分け

よほど特殊な事情がない限り、aggregateを直接使うことはないと思われる。大体のケースでfoldを使ったほうが便利だろう。

というのも、aggregateは要素がkeyによるグルーピングを行った最初の要素かどうかを判定したりするのも全て自分で書く必要があるからだ。要素が初出の場合に初期値を用意し、そうでない場合に集計処理をするというのがfoldなので、大抵のケースでfoldで事足りるはず。

最終的にはどれを使ってもList<何らかの型>Map<指定したキー, 集計後の結果>に集計される。(元のデータがListとは限らないけれど、最終的にMapに集約されるのは変わらない)

eachCount

keyごとの要素の個数が欲しい場合にこれを使う。引数もいらないので最もシンプル。

foldとreduce

要素の集計にロジックが必要な場合にこちらを利用する。オブジェクトの特定のフィールドだけが集計対象であるときなどに利用することが考えられるだろうか。

どちらも集計処理を行う関数オブジェクトを引数にとるのは同じ。

違いはfoldは集計値の初期値を設定する必要があるが、reduceは初期値すら省略できるというところ。reduceはkeyごとに出現した最初の要素が初期値に使われるからである。

集計処理を行う関数オブジェクトは、集計後の値を返すような関数オブジェクトにすればいい。この関数オブジェクトの戻り値が、次の要素のaccumulatorの値になる。

foldとreduceの違い

集計結果が要素と同じ型になるのかどうかが使い分けの分岐点となる。集計結果が元の要素と同じ型ならreduceを使ったほうが便利(初期値の指定がいらないので)。

というのもreduceの初期値はkeyごとに最初に出現した要素になるからである。だから型の変換が行えない。

data class SalesInfo(val id: String, val date: Date, val sales: Int)

val dailySales = listOf(...) // 日々の売上データ
// 商品IDごとに売上を集計
val sum = dailySales.groupingBy { it.id }
  .fold(0) { _, acc, element ->
    acc + element.sales 
  }
println(sum["hoge"]) // 商品ID"hoge"の1ヶ月分の売上を表示

上記の例で言えばSalesInfo型の要素をInt型に集計している。このケースではreduceは使えない。

data class ShootInfo(val name: String, val try: Int, val hit: Int)

val total = listOf(..ShootInfoのリスト..)
  .groupingBy { it.name }
  .reduce { key, accumulator, element ->
    ShootInfo(key, accumulator.try + element.try, accumulator.hit + element.hit)
  }
println(total["hoge"]) // hogeさんの試行回数と命中数を表示

この場合、各要素と集計後の型は同じなのでreduceが使えるということ。

reduceは要素をグルーピングして1つの要素に集約するイメージ。別の型への変換を伴うならfoldを使うというスタンスで使い分けたらいいのかなと理解した。