日本OSS推進フォーラム一般会員の1企業クリアコードの須藤です。
日本OSS推進フォーラム アプリケーション部会 第10回勉強会でApache Arrowを紹介しました。
関連リンク:
どういう人たちが来そうか予想できなかったので、あまりデータ処理まわりを知らない人にも雰囲気が伝わるといいなぁくらいのレベル感の内容にしました。技術的に突っ込んだ内容は少なめにしてこんなことができるよというのを網羅的に紹介したつもりです。
数年後、Apache Arrowがもっと普及したときに、この勉強会に参加した人たちが「あぁ、それ数年前から知っていたよー」と言えるようになるといいなぁというのを狙いました。
が、「アプリケーションのユーザーから見てApache Arrowで具体的にどううれしいの?」という問の答えとしては微妙だったなぁという感触でした。データ処理ツールを開発している人には「ここが速くなるのはこのケースでうれしい」とか「この機能はここでうれしい」とか伝わるのですが、データ処理ツールを使っている人にはイメージしづらいということがわかりました。ユーザーにとっても「速くなる」はうれしいはずですが、挙動は変わらないし、まだ動くものが少ないので体感できないしでピンとこないようです。
1,2年もすればApache Arrowを活用したプロダクトがいろいろでてくるはずなので、このプロダクトではこううれしくなった、あのプロダクトでは…と紹介できるようになるだろうなぁと思います。そうすればアプリケーションのユーザーからもイメージしやすくなりそうです。早くそんな状況になるためにも開発を進めたりデータ処理ツールを開発している人たちに紹介できるといいんじゃないかと思いました。
なお、もっと突っ込んだ話はApache Arrow東京ミートアップ2018で紹介します。この集まりにはデータ処理ツールを開発するような人たちが来る集まりです。
日本OSS推進フォーラム アプリケーション部会 第10回勉強会でApache Arrowを紹介しました。
アプリケーションのユーザーにApache Arrowのよさを説明することが難しいという知見を得ました。
クリアコードはApache Arrowを活用してデータ処理ツールの開発をしたいのでデータ処理ツールを開発していてApache Arrowを活用したい方はお問い合わせください。
Apache Arrow東京ミートアップ2018を主催したした須藤です。会場提供・飲食物提供などSpeeeさんにいろいろ協力してもらいました。ありがとうございます。
私はApache Arrow本体のことを網羅的に紹介しました。データの配置のことなど日本OSS推進フォーラム アプリケーション部会 第10回勉強会では触れなかった技術的な詳細についても紹介しています。
関連リンク:
この集まりは勉強会ではありません。勉強をする集まりではなく開発者を増やす集まりです。開発対象のプロダクトはApache Arrowだけでなく、Apache Arrow以外でもデータ処理に関わるプロダクトであればなんでもOKです。
そのため参加枠は次の2つにしました。
開発に参加する気がある人だけが参加する集まりということです。
「開発者を増やす」という目的を実現するために時間の使い方を次の2つにわけました。
後半では「開発の1歩目を踏み出せる」ことを目指しました。ポイントは「1歩目」です。この集まりの時間内で「バリバリ開発する」を目指していないということです。この集まりの時間で「なにに取り組もうか」が決まれば十分です。取り組むと決めたことに実際に取り組み始められればなおよしです。
「何に取り組もうか」を決めるために必要そうな情報を前半に提供しました。
前半では、まず私がApache Arrowの関する全体的な情報を提供しました。今回はApache Arrowを軸にいろいろなプロダクトの開発者を増やしたかったので、どのプロジェクトでも参考になりそうな予備知識としてApache Arrowの情報を最初に提供しました。
その後は次のテーマごとに詳しい人から情報を提供しました。適切な人に情報提供してもらえて本当によかったなぁと思っています。
みなさんには次の2点を話してくださいとお願いしていました。
「今後こうなるとよさそう」は「開発の1歩目」のヒントになることを期待していました。
私も新しく知ったことが多くあったのでみなさんにお願いして本当によかったなぁと思っています。Rubyまわりを開発している人視点で言うと、特にRとPythonの情報は興味深かったです。RubyでもRのALTREP・pandasのExtensionArrayのようなものが必要になるときは来るのだろうか、とか。
前半で開発を始めるための情報を得られたので後半では実際に開発を始める時間です。
次のグループにわかれてグループの人と相談しながら各人が「まずはなにに取り組むか」を決めていきます。
各グループには詳しい人たちがいるのでその人たちと相談しながら「なにに取り組むか」を決めます。私は各人に「まずはなにに取り組むか決まりましたかー?」と聞いてまわったのですが、だいたいみなさん決められたようでした。最初の1歩を踏み出せましたね。
すでにpull requestを出して2歩目・3歩目を踏み出せている人たちもいるのでいくつかリンクを置いておきますね。
勉強会ではなく「開発者を増やす」ことを目的にした集まりを開催しました。この集まりをきっかけに開発に参加した人がいたのでよい集まりだったなぁと思っています。「開発者を増やす」ことを目的にした集まりを開催したい人は参考にしてください。
参加した人たちには集まりの最後にアンケートに答えてもらいました。アンケートの結果はGitHubのspeee/code-party/apache-arrow-tokyo-meetup-2018/feedback/から参照できるので、同様の集まりを開催したい人はこちらも参考にしてください。
引き続き開発に参加していきましょう!
なお、クリアコードはApache Arrowを活用してデータ処理ツールの開発をしたいのでデータ処理ツールを開発していてApache Arrowを活用したい方はお問い合わせください。また、一緒にデータ処理ツールの開発をしたい人も募集しているのでわれこそはという方はご応募ください。
Rubyの標準添付ライブラリーのcsvをメンテナンスしている須藤です。
csvは名前の通りCSVを読み書きするための便利ライブラリーです。
もともとRuby本体とは別に開発されていたのですが、Ruby 1.8.0のときにRuby本体にバンドルするようになりました。dRubyやREXMLがRuby本体にバンドルされたのも同じタイミングです。Ruby 1.8.0のときにバンドルするライブラリーをすごく増やしたのです。(その頃の様子がわかるURLをここに置いておきたかったけど見つけられなかった。。。)
Rubyではcsvのようにrequire
するだけで使えるライブラリーを「標準添付ライブラリー」と呼んでいます。String
のようにrequire
しなくても使えるライブラリーは。。。なんだろう。組み込みクラスかしら。
その後、Ruby 1.9.0のタイミングで実装をFasterCSVに置き換えました。FasterCSVは名前の通りもともとのcsvよりも速いライブラリーです。もともとのcsvもFasterCSVもRubyだけで実装してあり、Cを使っていません。Rubyで実装したCSVライブラリーでは最速です。今のcsv(FasterCSVベースのcsv)よりも速いといっているCSVライブラリーはCを使っているはずです。
そんなcsvをさらに速くしたものがRuby 2.6.0に入っています。
FasterCSVがなぜ速いかというと各行をline.split(",")
でパースしているからです。String#split
はCで実装されているので速いのです。
ただ、世の中にはline.split(",")
でパースできないCSVがたくさんあります。たとえば、次のようなCSVです。
a,"b,c",d
このCSVではダブルクォートで囲んでいる中にコンマがあるのでline.split(",")
では次のようにパースしてしまいます。
[
"a",
"\"b",
"c\"",
"d",
]
このようなケースにも対応するために、FasterCSVはline.split(",")
した後の各要素のダブルクォートの数を数えます。ダブルクォートの数が偶数ならダブルクォートの対応が取れていて、奇数なら取れていないというわけです。ダブルクォートの対応が取れていない場合は後続する要素と連結します。
このようにして速さを維持したまま複雑なCSVもパースできるようになっています。ただ、複雑なCSVをパースするときは速度が落ちてしまいます。次の表はcsvが使っているベンチマークを使ったパース性能の計測結果です。複雑になるほど性能が落ちている(単位時間あたりでのパース回数が減っている)ことがわかります。
100msでのパース回数 | |
---|---|
ダブルクォートなし | 373 |
ダブルクォートあり | 207 |
ダブルクォート中にコンマあり | 140 |
ダブルクォート中に改行あり | 82 |
Ruby 2.6.0に入っているcsvでは次のようになります。「ダブルクォートあり」の場合は少し性能が落ちています(207から194に減っている)が、ダブルクォート内が複雑になっても「ダブルクォートあり」と性能が変わりません。(「コンマあり」と「改行あり」が193と192で194とほとんど変わらない。)「ダブルクォートなし」の場合は少し性能があがっています。(373から401に増えている)
100msでのパース回数 | |
---|---|
ダブルクォートなし | 401 |
ダブルクォートあり | 194 |
ダブルクォート中にコンマあり | 193 |
ダブルクォート中に改行あり | 192 |
「最速」だったcsvがどうやってさらに速くなったかというとStringScanner
を使うようになったからです。StringScanner
は標準添付ライブラリーの1つで、正規表現を使って高速に文字列をスキャンできます。
ただ、単にStringScanner
を使っても「最速」だったcsvよりも速くはなりません。line.split(",")
は強敵です。@284kmが取り組んだ、まずline.split(",")
をStringScanner
に置き換えるpull requestでも全体的に遅くなっています。ただ、これでも高速にするための工夫をした後の結果です。Red Data Toolsの開発の集まりなどで@284kmと一緒に高速にするための書き方を模索していました。その結果、次の知見を得ました。
StringScanner
を使ったコードは次のようなコードになります。ポイントは「次はこういう値が来るはず、来なかったらエラー」というのをつなげていくところです。
row = []
scanner = StringScanner.new(line)
column_value = scanner.scan(/[^",\r\n]+/) # カラムの値
raise "no column value" unless column_value
row << column_value
raise "no comma" unless scanner.scan(/,/) # カラムの区切り文字(コンマ)
column_value = scanner.scan(/[^",\r\n]+/) # 次のカラムの値
raise "no column value" unless column_value
row << column_value
raise "no comma" unless scanner.scan(/,/) # カラムの区切り文字(コンマ)
raise "extra data" unless scanner.eos? # すべてのデータを使ったか
p row
CSVのように複雑なものだと、「次はこういう値が来るはず、来なかったら別のこの値なはず」というようにフォールバックしていきます。たとえば、「ダブルクォートで囲まれていない値があるはず、なかったらダブルクォートで囲まれた値のはず」といった具合です。
line.split(",")
を超える性能を出すためにはフォールバックをいかに減らすかが大事になります。フォールバックのオーバーヘッドがあるとline.split(",")
に負けてしまうのです。
フォールバックを減らすには「次はこういう値が来るはず」ができるだけ当たるような順番にします。カラムの値の次はコンマがきやすいので、次の2つでは後者の方がフォールバックの回数が減ります。
カラムの値もコンマも並列に扱う(フォールバックが多い):
row = []
column_value = nil
until scanner.eos?
if scanner.scan(/[^",\r\n]+/) # カラムの値
column_value = scanner.matched
elsif scanner.scan(/,/) # コンマ
row << column_value
column_value = nil
else
raise "invalid"
end
end
row << column_value if column_value
p row
カラムの値の後はコンマがくるはず(フォールバックが少ない):
row = []
until scanner.eos?
if (column_value = scanner.scan(/[^",\r\n]+/)) # カラムの値
if scanner.scan(/,/) or scanner.eos?
row << column_value
else
raise "no comma"
end
else
raise "invalid"
end
end
p row
line.split(",")
に勝つには正規表現のマッチ回数をいかに減らすかを頑張る必要があります。これが基本的なコンセプトです。それではさらに具体的な方法を説明していきます。
line.split(",")
ベースのアプローチでは次のようにダブルクォート中が複雑になる処理で性能劣化が大きかったです。
100msでのパース回数 | |
---|---|
ダブルクォートあり | 207 |
ダブルクォート中にコンマあり | 140 |
ダブルクォート中に改行あり | 82 |
これを解決するために行に分割してから処理することをやめました。
行に分割せずに、ダブルクォート中がどうなっていても(たとえば改行文字を含んでいても)統一的に処理することで性能劣化を防ぎました。
100msでのパース回数 | |
---|---|
ダブルクォートあり | 194 |
ダブルクォート中にコンマあり | 193 |
ダブルクォート中に改行あり | 192 |
これが一番大変でした。というのは、パースするロジックをすべてStringScanner
らしく書き換える必要があるからです。
書き換えた後は次のようなコードになりました。すっきりですね。
row = []
while true
value = scanner.scan(/[^",\r\n]+/)
if scanner.scan(/,/)
row << value
elsif scanner.scan(/\r\n/)
row << value
p row
row = []
elsif scanner.eos?
row << value
p row
return
else
raise "invalid"
end
end
これでダブルクォートを使っていても性能劣化しなくまりました。(ダブルクォート中に改行がある方が速くなっているのはなぜだ。。。)
100msでのパース回数 | |
---|---|
ダブルクォートあり | 165 |
ダブルクォート中にコンマあり | 160 |
ダブルクォート中に改行あり | 187 |
これを実現することによりコードをメンテナンスしやすくなり、最適化や機能追加をしやすくなりました。line.split(",")
ベースのコードも200行未満の実装なのでそんなに長すぎるわけではないのですが、状態が多くて適切な場所に適切な処理を入れるのが難しかったのです。
以前と同じくらいの性能にできればStringScanner
ベースのパーサーで開発を進められます。
loop
をwhile true
にする性能改善の大きなポイントは正規表現のマッチ回数を減らすことですが、それ以外の部分でも少しずつ性能改善できます。その1つでやりやすいものがloop do ... end
ではなくwhile true ... end
でループするようにすることです。
Rubyを使っている場合はdo ... end
を使いたいので私は普段は次のようにループを書きます。
loop do
# ...
end
しかし、今回のように性能改善したいケースでは次のようにwhile true ... end
を使った方が高速です。これはloop
だとdo ... end
の中でスコープが変わるのでその準備をしないといけないのに対し、while
はスコープが変わらないのでその準備が必要ないからです。
while true
# ...
end
csvのケースではwhile true
の方が15%ほど高速です。
100msでのパース回数:
ダブルクォートなし | ダブルクォートあり | |
---|---|---|
loop |
377 | 166 |
while |
401 | 192 |
string[start...end]
をstring[start, end - start]
にするString
には文字列データの一部を共有する機能があるため、既存のString
の一部で必要なString
を作れる場合は共有機能を使うことで高速になります。
文字列データを共有するにはString#[]
を使います。String#[]
は便利なメソッドでいろんな引数を受けつけます。たとえば、次の2つは同じ結果を返します。
string[1...6]
string[1, 5]
ただし、string[1, 5]
の方が速いです。これは、引数が2つの場合は特別扱いされているためです。
csvの場合、string[1, 5]
のスタイルを使った場合の性能改善の度合いは軽微です。
100msでのパース回数 | |
---|---|
string[1...6] |
405 |
string[1, 5] |
409 |
みなさんはCSV#line
というメソッドがあるのを知っていますか?私は知りませんでした。このメソッドは最後に処理した行そのもの(パース前の行)を返します。普通はパース結果だけを使うので、この処理のために通常のパース処理が遅くなるのは微妙です。そのため、このための情報を必要になったときにはじめて取得するように変更しました。
100msでのパース回数 | |
---|---|
#line 用のデータを逐次処理 |
409 |
#line 用のデータを遅延処理 |
416 |
微妙に速くなっています。
通常は必要ない処理を必要になるまで処理しないことによる高速化はCSVの書き込み処理で顕著です。
CSV
はCSVを読み書きできるのでインスタンスを作るときに読み書き両方用の初期化をしていました。そのため、CSVを読むだけ、書くだけのときに余計な処理をしていました。
この読む用の初期化・書く用の初期化を必要になるまで遅延するようにしました。これにより、読むだけのときは書く用の初期化を一切しなくなり、高速になります。
以下は書き込み処理のベンチマーク結果です。
100msでの処理回数:
CSV.generate_line |
CSV#<< |
|
---|---|---|
読む用の初期化を毎回実行 | 350 | 2177 |
読む用の初期化を遅延実行 | 850 | 3506 |
2倍ほど速くなっています。CSV.generate_line
はCSV
オブジェクトを作らずに1行生成する便利機能ですが、たくさんの行を生成する時はCSV
オブジェクトを作った方が高速です。これは、CSV.generate_line
の場合は1行生成する度に書く用の初期化を毎回しなければいけないためです。
つまり、次のように書くのは遅いということです。
rows.each |row|
puts CSV.generate_line(row)
end
それよりは次のように書いた方が速いです。
output = ""
csv = CSV.new(output)
rows.each |row|
csv << row
end
puts output
String#each_char
ではなくString#index
を使う読む用の初期化時に改行文字を自動検出しているのですが、そこも高速化できた処理でした。
従来はString#each_char
で一文字ずつ確認していたのですが、そこをString#index
を使って書き換えました。次のような感じです。
cr_index = sample.index("\r")
lf_index = sample.index("\n")
if cr_index and lf_index
if cr_index + 1 == lf_index
"\r\n"
elsif cr_index < lf_index
"\r"
else
"\n"
end
elsif cr_index
"\r"
elsif lf_index
"\n"
else
:auto
end
String#index
を使うとCレベルで文字チェックをできるので速くなりました。(後でどのくらい速くなったか追記できるといいな。)
なんか野暮ったいコードなのでもう少しシュッとできるといいですね。
これで速くなるんじゃないかと試したものの逆に遅くなったアイディアもありました。
extend
csvにはまじめにパースするモードとゆるくパースするモードがあります。従来はメソッド内でif
で分岐していました。インスタンス作成時にモードにあわせたモジュールをextend
してパース時はメソッド内のif
を減らすと速くなるのではないか、という案です。こんな感じです。
module StrictMode
def parse
# ...
end
end
module LiberalMode
def parse
# ...
end
end
class CSV::Parser
def initialize(options)
if @options[:liberal_mode]
extend LiberalMode
else
extend StrictMode
end
end
end
CSV::Parser.new(:liberal_mode).parse # LiberalMode#parse
実際にやってみてところむしろ遅くなりました。メソッド内でif
で分岐する方が速かったです。
csvはRubyレベルで実装してあるCSVパーサーでは最速です。さらに速くするにはCで実装する必要があります。たとえば、Cを使っているfastest-csvはcsvよりも数倍高速です。
100msでのパース回数 | |
---|---|
csv | 16 |
fastest-csv | 76 |
なお、私のオススメはApache Arrowです。Apache ArrowはCSV用のライブラリーではありませんが、CSVパーサーもついています。Apache ArrowのCSVパーサーを使うとfastest-csvよりもさらに数倍高速です。
100msでのパース回数 | |
---|---|
csv | 16 |
fastest-csv | 76 |
Apache Arrow | 223 |
使い方も簡単です。次のコードでCSVをロードできます。
require "arrow"
Arrow::Table.load("/tmp/a.csv")
参考:Apache Arrowの最新情報(2018年9月版)
コードを整理でき、最適化・機能拡張の準備ができました。たとえば、次のような改良をしていきたいです。興味がある人は一緒に開発しましょう。
Ruby 2.6.0にあわせてcsvのコードを整理して高速化しました。より開発しやすいコードベースになったので一緒に開発していきましょう。
リリース直前にいろいろ変更をぶちこんでごめんなさい。
Rubyのbundled gemのtest-unitをメンテナンスしている須藤です。
test-unitはxUnitスタイルのテスティングフレームワークです。Rubyのテスティングフレームワークの歴史(2014年版)にまとめてある通り、Ruby本体に標準添付されています。
Rubyに標準添付されているライブラリーには実は次の3種類あります。
URI
)
require
するだけで使えるライブラリーrequire
するだけで使えるライブラリーGemfile
でgemを指定しなくても使えるrequire
するだけで使えるライブラリーどれも標準添付ライブラリーなのでrequire
するだけで使えます。違いはRubyGems・Bundlerとの関係です。
ただの標準添付ライブラリーはRubyGemsでアップグレードすることはできませんし、Bundlerで特定のバージョンを指定することもできません。使っているRubyに含まれているものを使うだけです。
default gemはRubyGemsでアップグレードすることもできますし、Bundlerで特定のバージョンを指定することもできます。Bundlerを使っていてgem名を指定しなかった場合は使っているRubyに含まれているものを使います。
bundled gemはRubyGemsでアップグレードすることもできますし、Bundlerで特定のバージョンを指定することもできます。Bundlerを使っていてgem名を指定しなかった場合は使えません。Bundlerを使っていなければrequire
するだけで使えます。
Ruby 2.6.0でより高速になったcsvはRuby 2.6.0からdefault gemになっています。
test-unitはRuby 2.2.0で再度標準添付されるようになってからbundled gemになっています。
そんなtest-unitのデータ駆動テスト機能をさらに便利にしたものがRuby 2.6.0に入っています。
データ駆動テストとは同じテスト内容をいろいろなデータで実行するテスト方法です。パラメーター化テストと呼ばれることもあります。いろいろな入力に対するテストを簡潔に書きたいときに便利です。
test-unitでは結構前からデータ駆動テストをサポートしています。
たとえば、正の数同士の足し算と負の数同士の足し算をテストすることを考えます。データ駆動テスト機能を使わない場合は次のようにそれぞれのケースについてテストを作ります。
require "test-unit"
class TestAdd < Test::Unit::TestCase
def test_positive_positive
assert_equal(3, my_add(1, 2))
end
def test_negative_negative
assert_equal(-3, my_add(-1, -2))
end
end
データ駆動テスト機能を使う場合はテストは1つで、テストに使うデータを複数書きます。
require "test-unit"
class TestAdd < Test::Unit::TestCase
data("positive + positive", [3, 1, 2])
data("negative + negative", [-3, -1, -2])
def test_add(data)
expected, augend, addend = data
assert_equal(expected, my_add(augend, addend))
end
end
データが増えてくるほど、データ駆動テスト機能を使った方がテストを書きやすくなります。データを追加するだけで済むからです。ただ、読みやすさは従来のテストの方が上です。テストに使うデータがベタ書きされているからです。
test-unitのデータ駆動テスト機能をもっと知りたくなった人はRuby用単体テストフレームワークtest-unitでのデータ駆動テストの紹介を参照してください。
Ruby 2.6.0に入っているtest-unitではデータ駆動テストがさらに便利になっています。
まだなんと呼ぶのがよいか決めかねているのですが、今のところデータ表(data matrix)と呼んでいるものを生成する機能が入っています。
データ表というのは各テストで使うデータをまとめたものです。前述のテストの場合は次のようになります。data
を使う毎に1行増えます。
ラベル | expected |
augend |
addend |
---|---|---|---|
"positive + positive" |
3 |
1 |
2 |
"negative + negative" |
-3 |
-1 |
-2 |
このデータ表をいい感じに生成する機能が入っています。
前述のテストで正の数と負の数を足す場合もテストしたくなったとします。その場合、従来のデータ駆動テスト機能の書き方では次のように書きます。data
を2つ増やしています。
require "test-unit"
class TestAdd < Test::Unit::TestCase
data("positive + positive", [3, 1, 2])
data("negative + negative", [-3, -1, -2])
data("positive + negative", [-1, 1, -2]) # 追加
data("negative + positive", [1, -1, 2]) # 追加
def test_add(data)
expected, augend, addend = data
assert_equal(expected, my_add(augend, addend))
end
end
データ表は次のようになります。
ラベル | expected |
augend |
addend |
---|---|---|---|
"positive + positive" |
3 |
1 |
2 |
"negative + negative" |
-3 |
-1 |
-2 |
"positive + negative" |
-1 |
1 |
-2 |
"negative + positive" |
1 |
-1 |
2 |
データ表生成機能を使うと次のように書けます。data
の第一引数にSymbol
を指定しているところがポイントです。テストに渡されるデータはHash
になっていてキーがシンボルで値が対象データです。
require "test-unit"
class TestAddDataMatrix < Test::Unit::TestCase
data(:augend, [1, -1])
data(:addend, [2, -2])
def test_add(data)
augend = data[:augend]
addend = data[:addend]
assert_equal(augend + addend,
my_add(augend, addend))
end
end
これで次のデータ表を生成できます。
ラベル | augend |
addend |
備考 |
---|---|---|---|
"addend: 2, augend: 1" |
2 |
1 |
正+正 |
"addend: 2, augend: -1" |
2 |
-1 |
正+負 |
"addend: -2, augend: 1" |
-2 |
1 |
負+正 |
"addend: -2, augend: -1" |
-2 |
-1 |
負+負 |
期待する結果(expected
)は生成できないのでRuby組み込みのInteger#+
の結果を使っています。これは実は大事なポイントです。データ表生成機能を使えるのは次の場合だけです。
今回の場合は期待する結果を計算できるので使えました。
なお、期待する結果は必ずしも正しい結果を返すはずの既存の実装(今回の場合はInteger#+
)を使わなくても大丈夫です。次のように「エンコードしてデコードしたら元に戻る」ようなときでもデータ表生成機能を使えます。これは性質をテストしているケースです。(性質をテストすることについてはここを参照してください、とか書いておきたいけど、どこがいいかしら。)
assert_equal(raw_data,
decode(encode(raw_data)))
この例ではパラメーターはaugend
とaddend
の2つでそれぞれに正と負があるので、4パターンでしたが、パラメーター数が増えたりバリエーションが増えると一気にパターンが増えます。そのときはこのデータ表生成機能が便利です。
なお、この機能はRed Chainer(Rubyだけで実装しているディープラーニングフレームワーク)で使うために作りました。もともとRed Chainerのテスト内でデータ表を生成していたのですがこの機能を使うことでだいぶスッキリしました。
実はRed Chainerのテストをスッキリさせるためにはデータ表を生成するだけでは機能が足りませんでした。同じデータ表を複数のテストで共有する機能が必要でした。
前述の例で言うと、同じデータ表を足し算のテストでも引き算のテストでも使いたいという感じです。コードで言うと、以下をもっといい感じに書きたいということです。
require "test-unit"
class TestCalc < Test::Unit::TestCase
data(:number1, [1, -1])
data(:number2, [2, -2])
def test_add(data)
number1 = data[:number1]
number2 = data[:number2]
assert_equal(number1 + number2,
my_add(number1, number2))
end
data(:number1, [1, -1])
data(:number2, [2, -2])
def test_subtract(data)
number1 = data[:number1]
number2 = data[:number2]
assert_equal(number1 - number2,
my_subtract(number1, number2))
end
end
そこで、data
メソッドにkeep: true
オプションを追加しました。これで一度data
を書けば後続するテストでも同じデータを使うようになります。
require "test-unit"
class TestCalc < Test::Unit::TestCase
data(:number1, [1, -1], keep: true) # keep: trueを追加
data(:number2, [2, -2], keep: true) # keep: trueを追加
def test_add(data)
number1 = data[:number1]
number2 = data[:number2]
assert_equal(number1 + number2,
my_add(number1, number2))
end
# ここにdataはいらない
def test_subtract(data)
number1 = data[:number1]
number2 = data[:number2]
assert_equal(number1 - number2,
my_subtract(number1, number2))
end
end
実はRed Chainerのテストをスッキリさせるためにはデータを使い回せても機能が足りませんでした。1つのテストに対して複数のデータ表を生成する機能が必要でした。
前述の例で言うと、小さい数同士と大きい数同士で別のデータ表を作りたい、ただし、小さい数と大きい数の組み合わせはいらないという感じです。(わかりにくい。)
データ表で言うと次の2つのデータ表を使う感じです。
小さい数用のデータ表:
内容 | augend |
addend |
---|---|---|
小さい正 + 小さい正 | 2 |
1 |
小さい正 + 小さい負 | 2 |
-1 |
小さい負 + 小さい正 | -2 |
1 |
小さい負 + 小さい負 | -2 |
-1 |
大きい数用のデータ表:
内容 | augend |
addend |
---|---|---|
大きい正 + 大きい正 | 20000 |
10000 |
大きい正 + 大きい負 | 20000 |
-10000 |
大きい負 + 大きい正 | -20000 |
10000 |
大きい負 + 大きい負 | -20000 |
-10000 |
コードで言うと、以下をもっといい感じに書きたいということです。
require "test-unit"
class TestAdd < Test::Unit::TestCase
data(:augend, [1, -1])
data(:addend, [2, -2])
def test_add_small(data)
augend = data[:augend]
addend = data[:addend]
assert_equal(augend + addend,
my_add(augend, addend))
end
data(:augend, [10000, -10000])
data(:addend, [20000, -20000])
def test_add_large(data)
augend = data[:augend]
addend = data[:addend]
assert_equal(augend + addend,
my_add(augend, addend))
end
end
そこで、data
メソッドにgroup:
オプションを追加しました。同じグループ毎にデータ表を生成します。
require "test-unit"
class TestAdd < Test::Unit::TestCase
data(:augend, [1, -1], group: :small) # 小さい数用
data(:addend, [2, -2], group: :small) # 小さい数用
data(:augend, [10000, -10000], group: :large) # 大きい数用
data(:addend, [20000, -20000], group: :large) # 大きい数用
def test_add(data)
augend = data[:augend]
addend = data[:addend]
assert_equal(augend + addend,
my_add(augend, addend))
end
end
setup
でもデータを参照可能にする実はRed Chainerのテストをスッキリさせるためにはデータ表を複数作れても機能が足りませんでした。テスト実行中にデータを参照しやすくする機能が必要でした。
従来のデータ駆動テスト機能ではテストメソッドの引数でデータを渡していました。そのため、setup
中でデータを参照できませんでした。
require "test-unit"
class TestAdd < Test::Unit::TestCase
def setup
# ここでデータを参照できない
end
data(:augend, [1, -1])
data(:addend, [2, -2])
def test_add(data)
augend = data[:augend]
addend = data[:addend]
assert_equal(augend + addend,
my_add(augend, addend))
end
end
Red Chainerのテストではデータを前処理したかったので次のように明示的に前処理メソッドを呼んでいました。
require "test-unit"
class TestAdd < Test::Unit::TestCase
def my_setup(data)
# 前処理
end
data(:augend, [1, -1])
data(:addend, [2, -2])
def test_add(data)
my_setup(data)
augend = data[:augend]
addend = data[:addend]
assert_equal(augend + addend,
my_add(augend, addend))
end
end
これは微妙なのでdata
でデータを参照できるようにしました。
require "test-unit"
class TestAdd < Test::Unit::TestCase
def setup
p data # データを参照できる!
end
data(:augend, [1, -1])
data(:addend, [2, -2])
def test_add(data)
augend = data[:augend]
addend = data[:addend]
assert_equal(augend + addend,
my_add(augend, addend))
end
end
また、テストでも引数でデータを受け取らなくてもよくなりました。(従来どおり受け取ってもよいです。)
require "test-unit"
class TestAdd < Test::Unit::TestCase
def setup
p data # データを参照できる!
end
data(:augend, [1, -1])
data(:addend, [2, -2])
def test_add # test_add(data)としなくてもよい!
augend = data[:augend]
addend = data[:addend]
assert_equal(augend + addend,
my_add(augend, addend))
end
end
Red Chainerのためにtest-unitにデータ表生成機能を追加しました。Ruby 2.6.0にもこの機能を使えるtest-unitが入っています。ぜひ活用してください。
なお、Ruby 2.6.0でなくてもRubyGemsで新しいtest-unit(3.2.9以降)にアップグレードすれば使えます。Red Chainerでもそうやって使っています。
Red Chainerの開発に参加したい人はRed Data Toolsに参加してください。オンラインのチャットか東京で毎月開催している開発の集まり(次回は2018年1月22日)でどうやって進めていくか相談しましょう。
みなさんはuniq
というコマンドやメソッドをご存じでしょうか?
LinuxやmacOSのシェルのコマンドとして使えるuniq
は、与えられた入力の中で(連続する)同じ値を重複と見なして除外するというコマンドです。例えばこんな風に使います。
$ cat /var/log/apache2/access.log | cut -d ' ' -f 1
192.168.0.12
192.168.0.10
192.168.0.12
192.168.0.12
192.168.0.11
192.168.0.10
192.168.0.11
192.168.0.11
$ cat /var/log/apache2/access.log | cut -d ' ' -f 1 | sort | uniq
192.168.0.10
192.168.0.11
192.168.0.12
プログラミング言語でも似たような機能を持っている物があります。例えばRubyでは、Arrayクラスのuniqメソッドを使うと配列の要素から重複を簡単に取り除くことができます。
[0,3,2,1,4,2,3,1,1,2,3,5,2,3,1,2,3,1,1,3,3,1,2].uniq
# => [0, 3, 2, 1, 4, 5]
ここで標題のJavaScriptの話をすると、JavaScript自体の言語仕様はES6やES2015、ES2017などを経て強化されてきているのですが、残念ながら上記のようなことを一発でやる機能は仕様化されていません。やりたければ、既存の機能を組み合わせて実現するほかありません。
やり方を紹介した記事は、配列の重複をはじく、もしくは重複を取り出す - Qiitaなど既にいくつも例がありますが、ここでは改めてなるべく多くのパターンを挙げてみる事にします。
古典的なやり方としては、Object
のプロパティ名を使う方法があります。JavaScriptではObject
のインスタンスは一種のハッシュ(連想配列)として機能し、プロパティ名(=ハッシュのキー)に重複はあり得ないため、配列の要素が登場済みかどうかの判定をするのに使うことができます。
function uniq(array) {
const knownElements = {};
const uniquedArray = [];
for (let i = 0, maxi = array.length; i < maxi; i++) {
if (array[i] in knownElements)
continue;
uniquedArray.push(array[i]);
knownElements[array[i]] = true;
}
return uniquedArray;
};
const array = [0,3,2,1,4,2,3,1,1,2,3,5,2,3,1,2,3,1,1,3,3,1,2];
console.log(uniq(array));
// => [0, 3, 2, 1, 4, 5]
for
文の箇所を今風の書き方に改めると、以下のようになるでしょうか。
function uniq(array) {
const knownElements = {};
const uniquedArray = [];
for (const elem of array) {
if (elem in knownElements)
continue;
uniquedArray.push(elem);
knownElements[elem] = true;
}
return uniquedArray;
}
ただ、この方法には一つ致命的な欠陥があります。それは、Object
のプロパティ名は必ず文字列として扱われるため、文字列化できない要素や、文字列化した時に区別がつかない要素を含む配列に対しては使えないという点です。JavaScriptではDOMのノードや何らかのクラスのインスタンスなどのオブジェクトを格納した配列を使うことが多いので、これでは使える場面が非常に限定されてしまいます。
Array
のインスタンスのindexOf
メソッドを使うと、任意の形式のオブジェクトについて、配列に含まれているかどうかを容易に識別することができます。これを使うと、先の例は以下のように書き直せます。
function uniq(array) {
const uniquedArray = [];
for (const elem of array) {
if (uniquedArray.indexOf(elem) < 0)
uniquedArray.push(elem);
}
return uniquedArray;
}
ES2016で追加されたArray
のincludes
メソッドは、渡されたオブジェクトが配列に含まれているかどうかを真偽値で返すという物です。これを使うと、indexOf
の戻り値の特性(配列に含まれていなければ-1
を返す)を知らない人でも読みやすいコードになります。
function uniq(array) {
const uniquedArray = [];
for (const elem of array) {
if (uniquedArray.includes(elem))
uniquedArray.push(elem);
}
return uniquedArray;
}
ES5.1で追加されたArray
のfilter
メソッドは、条件に当てはまる要素だけを含んだ配列を生成するという物です。これを組み合わせると、for
ループを書かずに同様のことができます。
function uniq(array) {
return array.filter(function(elem, index, self) {
return self.indexOf(elem) === index;
});
}
元の配列の中で2回目以降に登場した(同じ要素が既に登場済みの)要素は、indexOf
の結果=先頭からその要素を探した時の位置が、index
=要素自身の位置と一致しません。そういった要素を除外すれば、各要素が1回ずつしか出現しない配列を取り出せる、という訳です。一時的な配列を作らないで済ませるために、2つ前の例とは異なるindexOf
の使い方をしています(先の例では一時的な配列に対するindexOf
なのに対し、こちらは元の配列に対するindexOf
です)。
アロー関数を使うと、もう少しすっきり書けます。
function uniq(array) {
return array.filter((elem, index, self) => self.indexOf(elem) === index);
}
ES2015で追加されたMap
は、それまでのObject
を使った擬似的な連想配列(ハッシュ)とは異なり、任意のオブジェクトをキーとして使うことができる本物の連想配列です。これを使うと、先のObject
を使った例をより完全な物にすることができます。
function uniq(array) {
const knownElements = new Map();
const uniquedArray = [];
for (const elem of array) {
if (knownElements.has(elem))
continue;
uniquedArray.push(elem);
knownElements.set(elem, true);
}
return uniquedArray;
}
この例では配列を先に用意していますが、実はその必要はありません。というのも、Map
はkeys
メソッドを使うとキーだけの集合を得ることができるからです。keys
メソッドの戻り値はイテレータなので、ES2015で追加されたArray.from
を使って配列に変換することができます。
function uniq(array) {
const knownElements = new Map();
for (const elem of array) {
knownElements.set(elem, true); // 同じキーに何度も値を設定しても問題ない
}
return Array.from(knownElements.keys());
}
Map
に比べるとややマイナーですが、ES2015で追加されたSet
という機能もあります。Map
がキーと値のペアを取り扱うのに対して、Set
はMap
でいう所のキーだけ、つまり、一意な値を格納する集合です。要素の重複があり得ないArray
のような物、とも言えます。これを使うと、先の例はこう書き直せます。
function uniq(array) {
const knownElements = new Set();
for (const elem of array) {
knownElements.add(elem); // 同じ値を何度追加しても問題ない
}
return Array.from(knownElements);
}
しかし、これはもっと簡潔に書き直すことができます。Set
はコンストラクタの引数としてイテレータや配列を受け付けるため、new Set(array)
とすれば、渡した配列の要素の中から一意な値だけの集合を得ることができます。それをArray.from
で配列に戻せば、即ち「配列から重複を取り除く」のと同じ事になります。
function uniq(array) {
return Array.from(new Set(array));
}
2019年1月5日追記:Array.from
ではなくES2015のスプレッド構文を使うと、以下のようにも書けます。
function uniq(array) {
return [...new Set(array)];
}
ということで、JavaScriptで配列をuniqする方法を色々と列挙してみましたが、どの方法が一番おすすめと言えるでしょうか。
その答えを考える前に、何を以て「良い」と判断するかをまずは明らかにする必要があります。具体的には、以下の各観点に優先順位を付けなくてはなりません。
というのも、上記の例のそれぞれには一長一短あり、すべての条件を同時に満たす事は困難だからです。
コードの量については、見ての通りです。コードゴルフなどの文脈や、1バイトでもソースの量を減らさなくてはならないようなシビアな状況であれば、多少動作速度が遅くても文字数の短いコードにする必要があるでしょう。そうでない限りは、記述量が多くなっても速度の速いコードを採用する方が良いでしょう。
実行環境(ブラウザやNodeのバージョン)については、想定する環境でサポートされていない機能を使用している方法は、当然ながら採用できません。Map
やSet
を使う方法は、トランスパイラを使う事で古い環境でも動作させる事はできますが、その場合、変換後のコードがどのパターンになるかによって動作速度が変わってきます。
動作速度については、処理対象の配列の要素数と実行回数によって最適な方法が変わってきます。
まず重要な観点として、計算量の問題があります。アルゴリズムごとに計算量には差があり、配列の要素数や実行回数が多い場面では、なるべく計算量の小さいアルゴリズムの方が望ましいです。
また別の観点として、オーバーヘッドの問題があります。JavaScriptでは関数の呼び出しやオブジェクトの作成、値の型の変換など、純粋な計算量とは別の部分で処理に時間がかかる部分があります。実行回数が少なければオーバーヘッドはほとんど無視できますが、多いとほとんどの処理時間がオーバーヘッドによる物という事になる場合もあります。
それぞれのアルゴリズムで同じ配列を条件を変えながら処理するベンチマークをFirefox 64上で実行した場合の結果で、それぞれの優劣を見ていきましょう。まずは、要素数10の配列を10万回から50万回まで処理した結果です。グラフの縦軸は処理に要した時間(ミリ秒)で、グラフの線が上にあるほど処理が遅く、下にあるほど処理が速い事を示しています。
このように要素数の少ない(サイズの小さい)配列を処理する場面では、for
ループやArray
のメソッドだけを使う方法がおすすめという事がグラフから見て取れます。Map
やSet
を使う方法は、このくらいの要素数だとオーバーヘッドが非常に大きいようです。
次は、要素数300の配列を2500回から12500回まで処理した結果です。グラフの縦軸は処理に要した時間(ミリ秒)です。
今度は結果が逆転しました。最速なのはSet
を使う方法で、最も遅いのはArray
のfilter
を使う方法という結果になっています。これは、Array
のfilter
を使うアルゴリズムが本質的に二重ループである(いわゆる、計算量がO(n^2)のアルゴリズム)ことが原因です。この結果からは、要素数が増えてくるとオーバーヘッドよりも計算量の方が支配的になってくるという事が分かります。
次は、要素数10000の配列を100回から500回まで処理した結果です。グラフの縦軸は処理に要した時間(ミリ秒)です。
もはやオーバーヘッドは完全に無視できるレベルになり、計算量が少ない物が明白に高速という結果になりました。Array
のindexOf
やincludes
を使う方法とfilter
を使う方法で、本質的なアルゴリズムそのものは大差ない(どちらも二重ループ)のに、for
ループとfilter
とでパフォーマンスに大きな差が現れているのは何故でしょうか? その答えは後ほど説明しましょう。
今度は指標を変えて、要素数がどの程度になったあたりから計算量とオーバーヘッドの問題が逆転するかを見てみます。以下は、要素数を100から1000まで増やしながら5000回処理した場合の結果です。グラフの縦軸は処理に要した時間(ミリ秒)です。
実行環境の性能による部分が大きいと考えられますが、今回の実験環境においては要素数が300を超えたあたりで計算量の増大がオーバーヘッドを追い抜くという結果になりました。しかしやはりアルゴリズム的に差が無い筈のuniqByIndexOf
やuniqByIncludes
とuniqByFilter
やuniqByFilterArrow
の間で大きな差がある……というか、filter
を使うと指数関数的に処理時間が増大するのにfor
ループでは線形の増加に留まっているように見えます。
この謎を解くために、次はNightly 66.0a1での結果を見てみましょう。JavaScriptエンジンの最適化が進んでいるためか、同じパラメータだと数字が小さくなりすぎてしまったため、今度はパラメータを「要素数を100から200刻みで1900まで増やしながら10000回処理」に変えています。
グラフの傾向を見ると、計算量が大きいアルゴリズムであるindexOf
やincludes
を使った物はいずれも指数関数的な増大を見せています。1つ前の結果でuniqByIndexOf
やuniqByIncludes
が線形の増加に見えたのは、
for
ループは最適化されていたが、filter
のループは最適化されていなかった。for
ループを使った物の結果の指数関数的な増大が顕著になり始めるタイミングが右にずれていた(グラフが横に引き延ばされていた)。そのため、グラフの描画範囲では線形の増加に見えていた。filter
も最適化されたため、アルゴリズムが本質的に似ている4つの項目のグラフが再び接近するようになった。という事だったようです。
また、それでもまだfilter
を使った方法の方が遅いのは、indexOf
やincludes
を使った方法では検索対象の配列がuniq後の配列(=小さい配列)なのに対し、filter
を使う方法ではuniq前の配列(=大きい配列)を対象にしているせいで、その分余計な時間がかかったからだと考えられます。
2019年1月5日追記:new Set()
とスプレッド構文の組み合わせを加えて再計測した結果も掲載しておきます。
検証環境上では、スプレッド構文を使うとArray.from
より若干速いという結果が得られました。
以上、JavaScriptでArray
のuniq
を実現する様々な手法をご紹介しました。
Webのフロントエンドの開発では計算量が問題になるような事はそう多くないのではないかと思われますが、Nodeで大量のリクエストを捌くような場面や、どれだけの量のデータが渡されるか事前に予想できないライブラリ開発のような場面では、なるべく計算量が小さいアルゴリズムを採用する事が望ましいです。
また、1つの事を実現するのに複数のやり方がある場合には、何を優先するかを事前にきちんと明らかにし、数値で比較可能な場合は特に、この例のようにベンチマークを取ってそれぞれのやり方の優劣を比較する事が大事です。
性能測定の結果を踏まえると、処理速度的には、少なくとも今回の実験環境においては
Set
とArray.from
またはスプレッド構文の組み合わせが最もおすすめ。Set
やMap
を使わない方法の方がおすすめ。という事が言えそうです。ベンチマークに使用したスクリプトはGistで公開していますので、皆さんもぜひお手元で試してみて下さい。