コンサルでデータサイエンティスト

仕事でPythonを書いてます。機械学習、Webマーケティングに興味があります。趣味は旅です。

Sparkで使える機械学習(ML)パッケージについてまとめる

機械学習を扱うSparkアプリケーションの開発を行うにあたり、Spark上で使用することのできる機械学習パッケージ(ライブラリ)について調べてみたのでまとめます。

はじめに

機械学習を扱うような分析タスクや、機械学習を活用したソリューションの開発タスクなどがますます増えています。そのような中で、ビッグデータと呼ばれるような大規模データを扱わなければいけない場面が増えています。数十GB~数TBのデータに対して機械学習を適用しようとした場合、通常の単一マシンで動作するようなPythonプログラムではそのデータを扱いきれないことがほとんどです。このような場合、分散コンピューティングを実現することのできるHadoopSparkの活用を検討していくことになります。今回はSpark上で使うことのできる機械学習(ML)パッケージについてまとめます。

f:id:hktech:20190823024013p:plain


大規模データに適用する機械学習タスク

扱うデータが大規模であるからといって、必ずしもSpark上で機械学習を実施する必要があるわけではありません。例えば、件数でみれば数十億のレコードを持つログデータがあったとしても、SparkやHiveなどで何かしらの集約処理をすることで単一マシンで扱えるようなデータサイズに圧縮できる場合があります。このような場合には、豊富な機械学習ライブラリが用意されているPythonプログラムで処理をするという選択をとることが多いでしょう。

主に大規模データをSpark上で扱うような機械学習タスクには分類・クラスタリング・異常検知、時系列予測、レコメンデーションなどがあります。

f:id:hktech:20190823015930p:plain

Sparkで使える機械学習パッケージはこのようなタスクを実現する機械学習手法が実装されています。それぞれの機械学習パッケージの特徴に触れつつ、実装されている手法の違いについて比較していきます。

Sparkで使える機械学習パッケージ

Spark上で扱うことのできる機械学習パッケージは年々増えてきていますが、まだまだ数は限られています。近年では、AWSやDatabricksなどのクラウドプラットフォーマーが提供しているSageMaker SparkやDatabricksRunTimeMLなどの機械学習基盤が増えていますが、特定のクラウド上でしか使うことができないという不便さがあります。任意の環境で使用することのできる機械学習パッケージの選択肢は少なく、Sparkが公式で提供しているSparkMLパッケージが有名です。また、Deep LearningをSpark上で扱うことのできるパッケージとしてはYahoo社が開発しているTensorflow on Sparkや、Databricks社が開発しているspark-deep-learningなどがある。

f:id:hktech:20190823021236p:plain

本記事では、このような機械学習パッケージの中からいくつかについて詳しく取り上げ、それらの違いについて比較していきます。

Mahout

Apache Mahout*1は分散コンピューティングの歴史の中で最初期の機械学習パッケージです。MahoutはIBM*2が2011年に発表し、その後Hadoopの発展と共にOSS化が進んだパッケージです。Mahoutの読み方はマハウトであり、アイコンがHadoopの象に乗っていることからもわかるように「象使い」という意味です。現在はほとんど開発が進んでいないようです。

Mahoutは、従来Hadoop上で動く機械学習パッケージでしたが、現在はSpark上で動作します。
用意されている主な機械学習手法は以下の通りです。


このように実装されている手法は極めて限定的であるため、現在では使いどころはないと考えてよいと思います。

SparkMLlib/SparkML

SparkMLlib及びSparkMLはSpark公式*3が提供している機械学習パッケージです。2013年から開発が始まっており、最も広く使われているSparkの機械学習パッケージです。いずれもSpark本体と同様に、Scala, Python, Java, Rなどの言語からアクセスすることができます。SparkMLlibはSpark初期の機械学習パッケージとして一定の支持を得ていましたが、現在ではメンテナンスモードとなっておりこれ以上の追加開発はされない予定となっています。一方で、SparkMLはSpark2.0に向けて開発された比較的新しいパッケージであり、こちらは現在でも広く使われています。

SparkMLlibとSparkMLの違いとしては、SparkMLlibはRDDで扱うことを想定して実装されており、SparkMLはDataFrameおよびDatasetで扱うことを想定して開発されています。このように、大きな違いがある両者ですが、Github上では同一のリポジトリにて管理されています。また、両者に実装されている機械学習手法も共通のものが多いです。以下にその一部を列挙します。

  • 分類器: ナイーブベイズ、ロジスティック回帰、SVM、決定木、ランダムフォレスト、GBT
  • クラスタリング: Kmeans, LDA, 混合ガウスモデル
  • レコメンデーション: Alternating Least Square(ALS), Matrix Factorization
  • 回帰モデル: 一般化線形モデル、Ridge回帰、Lasso回帰

このように用意されている手法は限られているものの、一般的によく使われるアルゴリズムはおさえてあるようです。

MMLSpark

MMLSpark*4(Microsoft Machine Learning for Apache Spark)は2017年にMicrosoft社がAzure向けに開発・リリースした機械学習パッケージです。SparkMLと同様に、Scala, Python, Java, Rなどの言語によりアクセスすることができます。本パッケージはAzureクラウド向けに作られているものの、任意の環境で使用することが可能であるという特長があります。

MML Sparkに実装されている主な機械学習手法は以下の通りです。

  • 分類器: LightGBM
  • レコメンデーション: Smart Adaptive Recommendations (SAR)
  • その他: 自然言語処理、画像認識、DeepLearning系モデル

注目すべき点として、データサイエンティストに人気なLightGBMが実装されているということがあります。SparkMLそのものにはxgboostも実装されていないため、この点では優れたパッケージであるといえます。また、レコメンデーション手法である Smart Adaptive Recommendations (SAR)が実装されていることは、ALSによる協調フィルタリングしか存在しないSparkMLと比較するべき点でもあると思います。この手法では、単純な協調フィルタリングではなく、コンテンツ間の情報も活用することでコールドスタート問題を解決するものであるとのことなので、実用面で活用できるのではないかと考えています。

まとめ

Sparkで使える機械学習パッケージについてまとめました。一般的によく使われているSparkMLやSparkMLlib以外にも、いくつかのパッケージがあることがわかりました。今回は特定のクラウド上で使えるSageMaker SparkやDatabricksRunTimeMLについて紹介できなかったので、それらに触れる機会があれば今回紹介したいくつかのパッケージと比較をしたいと思います。

Scalaの配列(リスト)の各要素の出現個数をカウントする

Scalaの配列(リスト)の各要素の出現個数をカウントする方法について調べたのでまとめます。Pythonであればcollections.Counterやcountメソッドで実現できることを、Scalaでは関数型言語の思想に近い形で記述することができます。記事の後半ではおまけとして、配列内のカテゴリ変数の分かれ方を表す指標であるジニ係数(Gini Score)の算出方法についても書いています。

Scalaの配列(リスト)の各要素の出現個数をカウント

次のような長さ10の文字列配列があるとします。

val s = Seq("A", "A", "A", "B", "A", "C", "A", "A", "A", "B") 


この配列中の各要素の出現回数は次のように求めることができます。なお、ここでの出力はMap型になります。

val cntMap = s.groupBy(identity).mapValues(_.size)
cntMap: Map(A -> 7, C -> 1, B -> 2)


各要素の個数についてアクセスしたい場合は次のように書きます。要素“A”の個数は7個であることがわかります。

cntMap("A")
res: 7

配列内のカテゴリ変数のばらつき度合い(分散)をジニ係数で求める

ジニ係数とは配列内の各要素がどの程度ばらついているかを求める指標であり、0から1の範囲をとります。すべての要素が”A”であればジニ係数は0になり、すべての要素が互いに異なる場合は1に近い値をとります。
ジニ係数の詳細については次の記事に記載しています。
http://hktech.hatenablog.com/entry/2018/10/05/004235

ジニ係数は次の式で求めることができます。
 1-\sum_{i=1}^{K}P^2(C_i|t)

ここでは配列全体の要素数が必要となるので、次のように求めます。

val seqLen = s.size


算出式中の P^2(C_i|t)部分については、次のように求められます。

Math.pow(v.toDouble/seqLen, 2)


最終的なジニ係数の算出はfoldLeft関数を使って以下のように書くことができます。

val giniScore = 1.0 - cntMap.values.foldLeft(0.0)((sum, v) => 
  sum + Math.pow(v.toDouble/seqLen, 2))

まとめ

Scalaの配列の各要素の出現個数をカウントする方法についてご紹介しました。また、配列内のばらつき度合いを表すジニ係数の求め方についてもまとめました。メソッドをチェーンすることで複雑な処理も関数風に1行で書くことでScalaの特徴を活かすことができるので、本記事での記述方法を参考にしてみてください。

実践Scala入門

実践Scala入門

ニューラルネットワークに基づく時系列予測手法まとめ: LSTNet, RNN, LSTM, GRU

LSTNetの論文*1を読む機会があったので、関連手法であるニューラルネットワークをベースとした時系列予測の手法についてまとめました。本記事では、RNNをはじめとして、その派生であるLSTM、GRU、LSTNetについて紹介していきます。

RNN (Recurrent Neural Network)

RNN(Recurrent Neural Network) とは、ある層の出力を別の層の入力として利用するような再帰的構造を持ったニューラルネットワークです。

f:id:hktech:20190803021558p:plain

RNNの各時刻における中間出力は隠れ状態と呼ばれ、これは当該時刻tの時系列情報 x_{t}と前時刻t-1の隠れ状態 h_{t-1}を組み合わせて活性化したものです。

tanh(ハイパボリックタンジェント)を使った活性化は下式のように表すことができます。
 h_t=tanh(W_h\cdot [h_{t-1}, x_t] + b_h)


RNNのメリットは、独立した各時点での情報だけでなく前後の時系列情報を活用することができることです。一方で、RNNにはデメリットもあります。

RNNのデメリットは、直前の中間出力のみを使うため長期の時系列情報をうまく学習することができない点にあります。

LSTM (Long Short-Term Memory)

LSTMとは、RNNのデメリットであった長期の時系列情報を考慮することで長期的な依存関係の学習を可能にしたRNNの派生モデルです。
LSTMのメリットは長期間記憶を保持することで長期的な依存関係を考慮して回帰を実現できる点にあります。

f:id:hktech:20190804010234p:plain

LSTMの中間出力はRNNでも中間情報として出力されていた隠れ状態とLSTM特有のセル状態の2種類があります。

また、LSTMの特徴として忘却ゲート入力ゲート出力ゲートの3種類のゲートを持つという点があります。ゲートとは、情報をどの程度つぎの時刻に伝達するかを制御するコンポーネントであり、0から1の値をとります。

① 忘却ゲート
 f_t=\sigma(W_f\cdot [h_{t-1}, x_t] + b_f)

② 入力ゲート
 i_t=\sigma(W_i\cdot [h_{t-1}, x_t] + b_i)
 \tilde{C}_t=tanh(W_C\cdot [h_{t-1}, x_t] + b_C)

③ 出力ゲート
 o_t=\sigma(W_o\cdot [h_{t-1}, x_t] + b_o)

④ セル状態出力
 C_t=f_t \ast C_{t-1} + i_t \ast \tilde{C}_t

⑤ 隠れ状態出力
 h_t=o_t \ast tanh(C_t)


GRU (Gated Recurrent Unit)

GRUとは、LSTMの忘却ゲートと入力ゲートを単一の更新ゲートにマージし隠れ状態のみを伝達していくニューラルネットワークのモデルです。

f:id:hktech:20190805003508p:plain

GRUのメリットは、LSTMと比べて学習パラメータが少ないためより短い時間で学習することができるという点にあります。

① リセットゲート
 r_t=\sigma(W_r\cdot [h_{t-1}, x_t])

② 更新ゲート
 z_t=\sigma(W_z\cdot [h_{t-1}, x_t])

③ 活性化層
 \tilde{h}_t=tanh(W\cdot [r_t \ast h_{t-1}, x_t])

④ 隠れ層出力
 h_t=(1-z_t) \ast h_{t-1} + z_t \ast \tilde{h}_t


LSTNet

LSTNetは、ニューラルネットワークベースの多変量時系列予測モデルです。

LSTNetは大きく以下の3つのコンポーネントで構成されています。

① 特徴抽出を行うConvolution層
② 過去の短期・長期の時系列情報を伝達しながら伝達するRecurrent層
③ Recurrent層出力を結合しARモデルの出力と統合する層

f:id:hktech:20190805004224p:plain


Convolution層

Convolution層では入力された多次元時系列データに対し、畳み込みフィルタを複数適用させることで短期間の特徴および変数間の関係について抽出するように学習します。

f:id:hktech:20190805004926p:plain

Convolution層の出力 h_kは各フィルタを W_kとすると下式で表すことができます。
 h_k=RELU(W_k \ast X + b_k)


Recurrent層

Recurrent層は一般的なRecurrent Layer(GRU)と他Layerの2-Layer構造になっています。Layerの組み合わせは以下の通りです。
① Recurrent Layer(GRU) + Recurrent-Skip Layer
② Recurrent Layer(GRU) + Temporal Attention Layer


Recurrent-LayerはGRUモデルとなっており、 Convolution層の出力を入力としています。活性化関数は一般的なGRUモデルとは異なり、tanhではなくRELUを採用しています。

Recurrent-Layerの出力は以下の式で表すことができます。
 h_t=(1-z_t) \ast h_t + z_t \ast \tilde{h}_t

f:id:hktech:20190805005841p:plain


Recurrent-Skip LayerはRecurrent-Layerと同様に、 Convolution層の出力を入力としたGRUモデルが採用されています。 あらかじめ周期がわかっているデータについては、p個周期ごとの隠れ状態のみを使った予測を行うことができます。pを明示的に定め、p個分スキップすることで重要な情報を失うことなく伝達することができます。電力消費のデータであれば、24時間周期になるようにpを設定するといった使い方をします。

Recurrent Skip-Layerの出力は以下の式で表すことができます。
 h_t=(1-z_t) \ast h_{t-p} + z_t \ast \tilde{h}_t

f:id:hktech:20190805010105p:plain


Recurrent Layer(GRU) + Recurrent-Skip Layerの全結合後の出力は次のように表すことができます。
 h_t^D=W^Rh_t^R+\Sigma_{i=0}^{p-1}W_i^S h_{t-1}^S+b

これは時刻tのRecurrent-Layerの出力と、p-1時刻前までのRecurrent Skip-Layerの出力の和を表しています。


Temporal Attention LayerではRecurrent Skip-Layerとは異なりpを明示的に決めることはせず、Attention Layerを用いて過去系列の隠れ表現の注目度を算出し、予測に使用する過去系列の重みを決定して予測を行います。データに既知の周期性がない場合や、周期が動的変化する場合に有効です。

Recurrent Layerで出力した隠れ表現系列を  𝐻_𝑡^𝑅 = [h_{t-q}^R, \cdots, h_{t-1}^R] とすると、Attentionベクトル \alpha_tは各時点の隠れ表現とt-1時刻の隠れ表現との間の類似度を求めたものであり以下のように表すことができます。

 \alpha_t = AttnScore(H_t^R, h_{t-1}^R)


重み付きの隠れ表現ベクトルを c_t=H_t\alpha_tとすると、Recurrent Layer(GRU) + Temporal Attention Layerの出力は以下のように表現することができます。
 h_t^D=W[c_t;h_{t-1}^R] + b


全結合+ARモデル層

LSTNetの最終出力は  ℎ_𝑡^𝐷 (Recurrent Layerの全結合) と  ℎ_𝑡^𝐿 (ARモデルの出力)の和となります。ARモデルの出力結果と合わせることで、スケール変化の大きいデータに対してよりロバストな予測を実現することができるとされており、これは論文内の評価セクションにて説明されています。

f:id:hktech:20190805012121p:plain


まとめ

ニューラルネットワークベースの時系列予測手法であるRNN, LSTM, GRU、LSTNetの4手法についてご紹介しました。特に次元が大きい多次元時系列データに対しては一般的な回帰モデルよりも高い精度が期待できるため、このあたりの手法はおさえておきたいですね。


ゼロから作るDeep Learning ―Pythonで学ぶディープラーニングの理論と実装

*1:Modeling Long- and Short-Term Temporal Patterns with Deep Neural Network, https://arxiv.org/pdf/1703.07015.pdf

データサイエンティストが競技プログラミングをやるべき理由

前回の記事からだいぶ時間があいてしまいましたが、平成最後ということでひとつ書かせてください。


はじめに
先日登壇した勉強会で「データサイエンティストはエンジニアリングスキルを高めるべき」という趣旨の主張を展開した上で、「エンジニアリングスキルを高めるために競技プログラミングをやっている」と言ったところ、参加者から以下の質問を頂きました。


競技プログラミングと実務のエンジニアリングはどのように関係があるのですか?」


本記事では上記の疑問に対する自分なりの考えをまとめていこうと思います。
アルゴリズム重視や可読性の低いコードばかりで実務に役立たないと思われがちな競技プログラミングですが、実はいろんな側面で業務に役立つことを学ぶことができます。
今回の記事はエンジニア全般を対象とした話をするので、データサイエンティストでない方にも読んでいただきたい内容になっています。


以下に当てはまる読者には特に刺さるかもしれません

  • 周りと比べて仕事が遅い気がする人
  • なんとなく勢いで進めた結果、手戻りしがちな人
  • 問題・仕様の理解に時間がかかる人


目次

競技プログラミングとは

競技プログラミングとは、プログラミングを使って速く・正確に・多くの問題を解き、その結果を競う競技です。現在、世界中でオンラインコンテストが実施されています。
有名なところだと Topcoder, Codeforces, Google Code Jam などがあります。


とりわけ日本で競技プログラミングの話がされる場合は、Atcoderというオンラインコンテストサイトが連想されることが多いです。Atcoderは日本語で問題が出題されることが特徴で、毎週末開催されるコンテストには約5000人がエントリーしているほど有名になってきました (2019/04時点)。


f:id:hktech:20190429120236p:plain
Atcoder Beginner Contest 124 より


ほとんどの競技プログラミングサイトではオンラインジャッジという仕組みが採用されています。これは出題された問題に対するソースコードを提出すると、問いの条件を満たすようなテストケースを自動でチェックしてくれるというものです。提出コードがすべてのテストケースを満たしていて、実行時間も制限時間内だったとき初めてその問題をクリアしたことになります。

オンラインコンテストでは100~120分という制限時間の中で、複数の問題を世界中の人と同時に解き、その結果を競います。

競技プログラミングで身につくスキル

競技プログラミングで身につくスキルは、開発の各フェーズで必要とされるスキルにかなり近いです。まずは開発業務にどのようなフェーズがあるのか確認していきます。

開発を行う時のフェーズはおおよそ以下のようになります。

f:id:hktech:20190429014202p:plain

これをベースに、競プロでどのようなスキルが身につくのかをみていきましょう。

仕様の理解

問題や仕様の理解はコンテストにおいては最も重要なポイントです。問題の理解を誤ったまま先に進んでしまうと、すべて最初からやり直しとなってしまいます。これでは素早くたくさんの問題を解くことができません。仕事で炎上するときもだいたい認識の齟齬が原因ですよね。

問題読解能力は国語力でもあり、業務を行う上でもとても大切なスキルです。競技プログラミングを始めると、問題文から瞬時にイメージを正確にとらえるスキルを身につけることができます。

例えば次のような問題があります。

f:id:hktech:20190429133831p:plain

f:id:hktech:20190429133918p:plain
Atcoder Beginner Contest 125 より


上級者であれば瞬時に理解して実装に落とし込めるようですが、私は凡人なのでまず紙でイメージを書き出します。

この問題では隣り合ってる数字のペアの正負を何回でも操作して入れ替えられるよということなので、それを書き出すとこんな感じになります。

f:id:hktech:20190429135815j:plain


全ての数字を正にすることができました。入出力例と合っているのでこの解釈で間違いなさそうです。

もうひとつ例を書くと

f:id:hktech:20190429140022j:plain


今度は全ての数字を正にすることはできず、1つだけ負の数字が残っています。

このように問題を理解し、イメージをアウトプットすることが大切です。チーム開発などでは認識齟齬が致命傷になることが多いですが、実際の業務でも仕様を理解してイメージをチームメンバーと共有することが大事だと思います。競技プログラミングを始めてから、このような作業が速く・正確に行えるようになった気がします。


実装設計

問題の理解ができたら、次は実装方針の設計を行います。特にデータサイエンティストの人はこの設計をせずにコードを書き出してしまう場合が多い*1ですが、開発では設計を必ず行いましょう。もっとも競技プログラミングで上位を目指すのであれば設計をしている暇なんてありませんが…慣れるまでは急がば回れで堅実にやっていきましょう。


「仕様の理解」パートで、この問題設定では以下のパターンがあることがなんとなくわかりました。

  1. すべての数字を正にできるパターン
  2. 1つだけ負の数字が残ってしまうパターン

ここで、いくつか入力例を書き出してみます。

-10 5 -4
→ 10 5 4
→ 19

10 -4 -8 -11 3
→ 10 4 8 11 -3
→ 30

10 -5 2 8
→ 10 5 -2 8
→ 21

9 -4 3 -1 5
→ 9 4 3 1 5
→ 22

ここまで書くと、以下のことがわかります。

  1. 負の数字が奇数個のとき ⇒ 1つだけ負の数字が残ってしまう
  2. 負の数字が偶数個のとき ⇒ すべての数字を正にできる

つまり、以下のような設計方針を立てることができます。

  • 負の数字をカウントする
  • 負の数字カウントが偶数なら、入力数列の絶対値の和をとる
  • 負の数字カウントが奇数なら、入力数列の絶対値の和から最小数の絶対値 * 2 を引く(既に足した分も引くため)

また、コンテストでは実行時間制限が設けられているため、おおまかな計算量を試算しておく必要があります。頑張ってコードを書いて回した結果、計算時間オーバーではもったいないです。

今回の方針は、入力列(長さN)に対して1回のループを回すためO(n)で解けそうだということがわかります。

テスト設計

前段でテストパターンを洗い出したものの、これで全パターンを満たせているでしょうか?

競技プログラミングでは全てのテストケースを通過しなければ、正解とはなりません。さらに、Atcoderではミスをおかす度にペナルティが付与されてしまうため、テストケースに漏れがないかよく確認したいところです。

実装する前にテスト設計を行う理由としては、テストパターンに漏れがあった場合に実装方針に影響が出てしまうからです。手戻りは未然に防ぎたいですよね。

先の例で、入力パターンをいくつか用意して設計を行い、これを実際のテストパターンとして使う開発手法はテスト駆動開発と呼ばれていたりします。テスト設計と実装設計を同時にやってしまうようなものなのですが、テストパターンが完璧に押さえられている場合は、これを満たすようにロジックを実装するだけなのでとても楽で確実です。


前章で列挙した入力パターンを確認すると、どうやら0が入るパターンを考慮できていなかったようです。このパターンでは、負の数字カウントが奇数なのにもかかわらず全ての数字を正にすることができています。

f:id:hktech:20190429145013j:plain

テストケース漏れ??と思いましたが、そもそも0が入る場合は最後に引くものがないため問題なさそうです。

負の数字カウントが奇数なら、入力数列の絶対値の和から最小数の絶対値 * 2 を引く(既に足した分も引くため)

符号が変わるポイントは忘れがちなので、与えられる数字の範囲に注意してテストケースを設計したいです。念のため新たな入力例もテストパターンに加えて準備万端です。あとは、これらのテストケースが全て通るようなコードを書くだけです。

テスト駆動開発がいかに有用であるかということを、競技プログラミングを通して肌で理解することができます。

実装・テスト

多くのオンラインコンテストでは、好きなプログラミング言語を選んで実装することができます。高速で実行ができるという点で、C++を使っている方が多いですが、実務で使っている好きな言語で書けば良いと思います。

実装方針はすでに立っているので、実装をしていきましょう。
以下が私がPythonで書いたコードです。

# read input
n = int(input())
x_list = [int(i) for i in input().split()] 
 
minus_count = 0
abs_list = []
for x in x_list:
  if x < 0: # x is minus
    minus_count += 1
  abs_list.append(abs(x)) # take abs
    
if minus_count % 2 == 0: # minus_count is even
  print(sum(abs_list))
else: # minus_count is odd
  print(sum(abs_list) - 2 * min(abs_list))


競技プログラミングはプログラムを書くことがメインだと思われがちですが、実は実装に入るまでにほとんどのことは終わっています。上記のコードはプログラミング初心者でもぐぐったら書けるレベルですし、初心者向けの問題であれば実装の高度なテクニックは求められません。

他にも、Atcoderではいろいろな人のコードをみることができます。例えば以下の例は、同じ方針を短いコードでまとめあげています。

n=int(input());a=list(map(int,input().split()));c=0
for i in range(n):
    if a[i]<1:c+=1
    a[i]=abs(a[i])
a.sort()
print(sum(a) if c%2==0 else sum(a)-2*a[0])

最後に、用意した全てのテストパターンを通過することを確認しコードを提出します!

まとめ

競技プログラミングで得たスキルと実務の開発がどのように関係しているかということについて紹介しました。

仕様理解、設計、実装、テストという流れは一般的な開発フローと似ていますし、アルゴリズムや実装テクニックといった部分以外にも実務に役立つことをたくさん学ぶことができます。実装に入るまでにほとんどのことが終わっていると書きましたが、実務でもこのように仕様理解と設計をしっかりと行うことが早く仕事をこなす近道だと思います。急がば回れです。

今回はアルゴリズム以外の部分に着目しましたが、今後はアルゴリズムや計算量を意識した実装に関する記事を書ければいいなと思います。

*1:Jupyter notebook の副作用でしょうか…

Scalaで配列/リストを操作するSeqコレクションについてまとめた

Scalaで配列またはリストを使う際はSeqがおすすめです。本記事では、他のプログラミング言語における配列やリストとは少し異なる挙動を示すSeqコレクションの文法および操作についてまとめました。

Seqの宣言

ScalaのSeqは以下のように作ることができます。

scala> Seq("One", "Two", "Three")
res0: Seq[String] = List(One, Two, Three)


変数seqにリストを持たせる場合は以下のように宣言することができます

scala> val seq: Seq[String] = Seq("One", "Two", "Three")
seq: Seq[String] = List(One, Two, Three)


Seqの要素についてString型をあらかじめ宣言する必要がある点が、Pythonなどのスクリプト言語との大きな違いです。

Seqの要素にアクセスする

ScalaでSeqの要素にアクセスする方法について紹介します。

次のように添字1を指定して要素を取り出すことができます。

scala> seq(1)
res1: String = Two


Scalaの添字は他の多くのプログラミング言語と同じく0で始まるため、2番目の要素が抽出されていることがわかります。

また、Seqの先頭要素や末尾要素へのアクセスはheadやlastを使って次のように行うことができます。

scala> seq.head
res2: String = One

scala> seq.last
res3: String = Three


Seqのinitやtailを使うと、次のように末尾以外・先頭以外の要素を取り出すことができます。

scala> seq.init
res4: Seq[String] = List(Two, Three)

scala> seq.tail
res5: Seq[String] = List(One, Two)

Seqの要素を追加または削除する

ScalaでSeqに要素を追加または削除する方法について紹介します。

先頭に要素を追加するには+: 、末尾に追加するには :+ と記述します。

scala> "Zero" +: seq
res6: Seq[String] = List(Zero, One, Two, Three)

scala> seq +: "Four"
res7: Seq[String] = List(One, Two, Three, Four)


このとき、元のseqは変化していないことに気づかれた方もいると思います。Scalaのコレクションは基本的に非破壊的であるため、新しいオブジェクトが返されるということを覚えておきましょう。

複数のSeqを連結する

Scalaで複数のSeqを結合する方法は次の通りです。

scala> val seqToAdd = Seq("Hello", "World")
seqToAdd: Seq[String] = List(Hello, World)

scala> seq ++ seqToAdd
res8: Seq[String] = List(One, Two, Three, Hello, World)


Seq同士が連結されていることが確認できます。

Seqの要素をソートする

ScalaでSeqをソートするにはsortedを使います。また、逆順に表示するにはreverseを使います。この辺りはpythonと同じメソッド名ですね。

scala> Seq(8, 3, 4, 1).sorted
res9: Seq[Int] = List(1, 3, 4, 8)

scala> Seq(8, 3, 4, 1).reverse
res10: Seq[Int] = List(1, 4, 3, 8)

まとめ

ScalaのSeqコレクションの文法および操作についてまとめました。本記事で取り上げた内容はかなり基本的なメソッドばかりですが、Scalaのリスト操作にはmap, filter, foldLeft, foldRight などの特徴的なメソッドがまだまだあります。これらについては別記事で紹介できればと思います。

Scalaでパッケージをインポートする

Scalaでパッケージおよびライブラリをインポート(import) する方法についてご紹介します。
Scalaに入門したばかりの私が、次の入門書を参考にしながらまとめました。

実践Scala入門

実践Scala入門



パッケージのインポート

Scalaでは、Javaと同様にクラス、オブジェクト、トレイトなどは必ず何らかのパッケージに所属します。パッケージのインポートは他のプログラミング言語と同じく、プログラムの冒頭で行われます。
ドメイン名を逆順にしたものをパッケージ名とするのが一般的な慣習です。

例えば、SparkのWindow関数を使うためのクラスをインポートする方法は以下の通りです。

import org.apache.spark.sql.expressions.Window

この例では、Windowという名前で org.apache.spark.sql.expressions.Window を参照することができるようになります。


ここで、Windowという同じ名前のクラスがインポートされていて衝突してしまった場合にはどのようにすればいいでしょうか?
Scalaではインポート時の名前衝突を以下のように防ぐことができます。

import org.apache.spark.sql.expressions.{Window => SparkWindow}


また、特定のクラスだけでなく、あるパッケージ配下に所属するすべてのクラスやオブジェクトをインポートしたいときには以下のようなインポート文を書くことができます。

import org.apache.spark.sql.expressions._

このようなインポートはワイルドカードインポートなどと呼ばれます。

まとめ

Scalaでパッケージをインポートする方法についてまとめました。Javaに馴染みがある方にとっては特に違和感のない内容となっていますが、他の言語から始められた方はこの機会にインポートの仕方を確認してみてください。

【Scala入門】 ScalaでFizzBuzz問題を解く

Apache Sparkの学習の一環としてScalaに触れてみることにしました。
本記事では、Scalaの基本的な構文を確認した後にFizzBuzz問題を解いていきます。

SparkとScalaの関係性について詳しく知りたい方はこちら
hktech.hatenablog.com


FizzBuzz問題とは

FizzBuzz問題とは1から100までの数字について、3で割り切れる場合に”Fizz”、5で割り切れる場合に”Buzz”、両者で割り切れる場合に”FizzBuzz”、それ以外の場合はその数字を出力させるプログラミング問題です。

調べてみたらもともとは英語圏で遊ばれている言葉遊びらしいです。

プレイヤーは円状に座る。最初のプレイヤーは「1」と数字を発言する。次のプレイヤーは直前のプレイヤーの次の数字を発言していく。ただし、3で割り切れる場合は「Fizz」(Bizz Buzzの場合は「Bizz」)、5で割り切れる場合は「Buzz」、両者で割り切れる場合(すなわち15で割り切れる場合)は「Fizz Buzz」(Bizz Buzzの場合は「Bizz Buzz」)を数の代わりに発言しなければならない。発言を間違えた者や、ためらった者は脱落となる。

ja.wikipedia.org


いや、ただの宴会ゲーム。難しそう。


Scalaのプログラミング構文

いきなりScalaの実装に入る前に、基本的なプログラミング構文を確認しておきます。

FizzBuzz問題で必要となるのは大きく3つです。

  • 1から100までの数字のリスト(配列)
  • リストをまわすためのfor文
  • 条件分岐するためのif-else文

リスト

まずはリストの構文について確認していきます。

1から3までのリストを作ります。

$ List(1, 2, 3)
 res: List[Int] = List(3, 1, 4)


直感的ですね。てかScalaって型推論あるのか、、、確かに型宣言はしてないですよね。

次に1から100のリストを作ります。さすがに1から100まですべて書き出すわけにはいかないですよね。
そこで、Rangeというものを使います。これはPythonと同じですね。

$ Range(1, 101)
 res: scala.collection.immutable.Range = Range 1 until 101


できてそうですね。これをリスト型にします。

$ Range(1, 101).toList
 res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100)


こんな書き方もできます。

$ (1 to 100).toList
 res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100)

for文

Scalaにおけるfor文の書き方についてみていきます。

こんな感じです。簡単です。

$ for (s <- Array("a", "b", "c")) println(s)
 a
 b
 c



それでは前のセクションで学んだリストを使い、1から100を出力してみましょう。

$ for (s <- (1 to 100)) println(s)
 1
 2
 3
 4
 ..........
 
 99
 100


できました。
あとは条件分岐にしたがって、”Fizz” や “Buzz” を出力するようにしていきましょう。

if-else文 / match文

Scalaにおけるif-else条件分岐の書き方について確認していきます。

if-else文は次のように書きます。

$ val i = 3
$ if (i % 2 == 0) print("even") else print("odd")
 odd

また、他の言語のswitch文にあたる構文として、Scalaにはmatch文があります。

var num = 1
num match{
    case 1 => println("one")
    case 2 => println("two)
    case _ => println("other")
}


ScalaFizzBuzz問題を解く

FizzBuzz問題に必要なScalaプログラミング構文を完全に理解したところで、早速実装をしてみました。

for (s <- (1 to 100))
    if (s % 15 == 0)
        println("FizzBuzz")
    else if (s % 3 == 0)
        println("Fizz")
    else if (s % 5 == 0)
        println("Buzz")
    else
        println(s)

無事にFizzBuzz問題が解けました!
コーディング面接でFizzBuzzを書く機会があれば間違いなくScalaで書くでしょう。

もっといい実装方法があるか
こちらの記事では、関数をつくって次のように実装しています。

def fizzBuzz(i: Int): String = {
    val fizz = i % 3 == 0
    val buzz = i % 5 == 0
 
    if (fizz && buzz) "FizzBuzz"
    else if (fizz) "Fizz"
    else if (buzz) "Buzz"
    else i.toString()
    }
   
for (i <- 1 to 99) println(fizzBuzz(i))


さらにScalaっぽく書くパターンとして、次のように処理をチェーンするような書き方があります。

def fizzBuzz(i: Int) = {
  1 to i
} map {
  case i if i % 15 == 0 => "FizzBuzz"
  case i if i % 3 == 0 => "Fizz"
  case i if i % 5 == 0 => "Buzz"
  case _ => i
} foreach {
  s => println(s)
}

fizzBuzz(100)

まずリストを作った上で、その要素をmapで加工し、最後に出力の処理を行います。


最後はmatch文を用いた実装です。こちらが最もシンプルでわかりやすいですね。

def fizzBuzz(i: Int) = i match {
  case i if i % 15 == 0 => "FizzBuzz"
  case i if i % 3 == 0 => "Fizz"
  case i if i % 5 == 0 => "Buzz"
  case _ => i.toString()
}



まとめ

ScalaFizzBuzz問題にチャレンジしてみました。Scalaの基本的なプログラミング構文を活用し、さまざまな実装パターンについて確認しました。Scalaは複雑なプログラミング言語であるというイメージがありましたが、意外にシンプルに書くことができました。引き続きScalaに関する記事を書いていきたいと思います。