株式会社クリアコード > ククログ

ククログ

日本OSS推進フォーラム アプリケーション部会 第10回勉強会 - Apache Arrow - データ処理ツールの次世代プラットフォーム

日本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を活用したい方はお問い合わせください。

この記事の続き

関連記事

2018-12-05

Apache Arrow東京ミートアップ2018 - Apache Arrow #ArrowTokyo

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のようなものが必要になるときは来るのだろうか、とか。

後半：開発を始める時間

前半で開発を始めるための情報を得られたので後半では実際に開発を始める時間です。

次のグループにわかれてグループの人と相談しながら各人が「まずはなにに取り組むか」を決めていきます。

  • Apache Arrow（Multiple-Dimension-Spread・Ruby関連を含む）
  • Apache Spark
  • Python
  • R

各グループには詳しい人たちがいるのでその人たちと相談しながら「なにに取り組むか」を決めます。私は各人に「まずはなにに取り組むか決まりましたかー？」と聞いてまわったのですが、だいたいみなさん決められたようでした。最初の1歩を踏み出せましたね。

すでにpull requestを出して2歩目・3歩目を踏み出せている人たちもいるのでいくつかリンクを置いておきますね。

まとめ

勉強会ではなく「開発者を増やす」ことを目的にした集まりを開催しました。この集まりをきっかけに開発に参加した人がいたのでよい集まりだったなぁと思っています。「開発者を増やす」ことを目的にした集まりを開催したい人は参考にしてください。

参加した人たちには集まりの最後にアンケートに答えてもらいました。アンケートの結果はGitHubのspeee/code-party/apache-arrow-tokyo-meetup-2018/feedback/から参照できるので、同様の集まりを開催したい人はこちらも参考にしてください。

引き続き開発に参加していきましょう！

なお、クリアコードはApache Arrowを活用してデータ処理ツールの開発をしたいのでデータ処理ツールを開発していてApache Arrowを活用したい方はお問い合わせください。また、一緒にデータ処理ツールの開発をしたい人も募集しているのでわれこそはという方はご応募ください。

この記事の続き

関連記事

2018-12-10

Ruby 2.6.0とより高速なcsv

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実装がなぜ速いか

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

Ruby 2.6.0のcsvがなぜ速いか

「最速」だった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パーサー

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月版）

今後

コードを整理でき、最適化・機能拡張の準備ができました。たとえば、次のような改良をしていきたいです。興味がある人は一緒に開発しましょう。

  • バックスラッシュでダブルクォートをエスケープ #61
  • クォート文字を指定しなかったらline.split(",")を使う高速化 #56
  • ヘッダーがあるときの高速化 #59

まとめ

Ruby 2.6.0にあわせてcsvのコードを整理して高速化しました。より開発しやすいコードベースになったので一緒に開発していきましょう。

リリース直前にいろいろ変更をぶちこんでごめんなさい。

タグ: Ruby

この記事の続き

関連記事

2018-12-25

Ruby 2.6.0とtest-unitとデータ駆動テスト

Rubyのbundled gemのtest-unitをメンテナンスしている須藤です。

歴史

test-unitはxUnitスタイルのテスティングフレームワークです。Rubyのテスティングフレームワークの歴史（2014年版）にまとめてある通り、Ruby本体に標準添付されています。

Rubyに標準添付されているライブラリーには実は次の3種類あります。

  • ただの標準添付ライブラリー（例：URI）
    • requireするだけで使えるライブラリー
  • default gem（例：csv）
    • requireするだけで使えるライブラリー
    • RubyGemsで更新できる
    • Gemfileでgemを指定しなくても使える
  • bundled gem（例：test-unit）
    • requireするだけで使えるライブラリー
    • RubyGemsで更新できる

どれも標準添付ライブラリーなので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日）でどうやって進めていくか相談しましょう。

タグ: Ruby

関連記事

2018-12-26

JavaScriptのArrayでuniqする8つの方法（と、その中で最速の方法）

この記事はQiitaとのクロスポストです。

みなさんは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などを経て強化されてきているのですが、残念ながら上記のようなことを一発でやる機能は仕様化されていません。やりたければ、既存の機能を組み合わせて実現するほかありません。

uniqのやり方色々

やり方を紹介した記事は、配列の重複をはじく、もしくは重複を取り出す - Qiitaなど既にいくつも例がありますが、ここでは改めてなるべく多くのパターンを挙げてみる事にします。

Objectのキーを使う方法

古典的なやり方としては、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の便利メソッドを使う

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);
}
Mapを使う

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());
}
Setを使う

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万回まで処理した結果です。グラフの縦軸は処理に要した時間（ミリ秒）で、グラフの線が上にあるほど処理が遅く、下にあるほど処理が速い事を示しています。

サイズの小さい配列のuniqのベンチマーク

このように要素数の少ない（サイズの小さい）配列を処理する場面では、forループやArrayのメソッドだけを使う方法がおすすめという事がグラフから見て取れます。MapやSetを使う方法は、このくらいの要素数だとオーバーヘッドが非常に大きいようです。

次は、要素数300の配列を2500回から12500回まで処理した結果です。グラフの縦軸は処理に要した時間（ミリ秒）です。

サイズが中くらいの配列のuniqのベンチマーク

今度は結果が逆転しました。最速なのはSetを使う方法で、最も遅いのはArrayのfilterを使う方法という結果になっています。これは、Arrayのfilterを使うアルゴリズムが本質的に二重ループである（いわゆる、計算量がO(n^2)のアルゴリズム）ことが原因です。この結果からは、要素数が増えてくるとオーバーヘッドよりも計算量の方が支配的になってくるという事が分かります。

次は、要素数10000の配列を100回から500回まで処理した結果です。グラフの縦軸は処理に要した時間（ミリ秒）です。

サイズが大きい配列のuniqのベンチマーク

もはやオーバーヘッドは完全に無視できるレベルになり、計算量が少ない物が明白に高速という結果になりました。ArrayのindexOfやincludesを使う方法とfilterを使う方法で、本質的なアルゴリズムそのものは大差ない（どちらも二重ループ）のに、forループとfilterとでパフォーマンスに大きな差が現れているのは何故でしょうか？ その答えは後ほど説明しましょう。

今度は指標を変えて、要素数がどの程度になったあたりから計算量とオーバーヘッドの問題が逆転するかを見てみます。以下は、要素数を100から1000まで増やしながら5000回処理した場合の結果です。グラフの縦軸は処理に要した時間（ミリ秒）です。

配列の要素数を増やしながらのuniqのベンチマーク

実行環境の性能による部分が大きいと考えられますが、今回の実験環境においては要素数が300を超えたあたりで計算量の増大がオーバーヘッドを追い抜くという結果になりました。しかしやはりアルゴリズム的に差が無い筈のuniqByIndexOfやuniqByIncludesとuniqByFilterやuniqByFilterArrowの間で大きな差がある……というか、filterを使うと指数関数的に処理時間が増大するのにforループでは線形の増加に留まっているように見えます。

この謎を解くために、次はNightly 66.0a1での結果を見てみましょう。JavaScriptエンジンの最適化が進んでいるためか、同じパラメータだと数字が小さくなりすぎてしまったため、今度はパラメータを「要素数を100から200刻みで1900まで増やしながら10000回処理」に変えています。

配列の要素数を増やしながらのuniqのベンチマーク2

グラフの傾向を見ると、計算量が大きいアルゴリズムであるindexOfやincludesを使った物はいずれも指数関数的な増大を見せています。1つ前の結果でuniqByIndexOfやuniqByIncludesが線形の増加に見えたのは、

  • Firefox 64時点ではforループは最適化されていたが、filterのループは最適化されていなかった。
  • 最適化の結果、forループを使った物の結果の指数関数的な増大が顕著になり始めるタイミングが右にずれていた（グラフが横に引き延ばされていた）。そのため、グラフの描画範囲では線形の増加に見えていた。
  • Nightly 66ではfilterも最適化されたため、アルゴリズムが本質的に似ている4つの項目のグラフが再び接近するようになった。

という事だったようです。

また、それでもまだfilterを使った方法の方が遅いのは、indexOfやincludesを使った方法では検索対象の配列がuniq後の配列（＝小さい配列）なのに対し、filterを使う方法ではuniq前の配列（＝大きい配列）を対象にしているせいで、その分余計な時間がかかったからだと考えられます。

2019年1月5日追記：new Set()とスプレッド構文の組み合わせを加えて再計測した結果も掲載しておきます。
配列の要素数を増やしながらのuniqのベンチマーク3
検証環境上では、スプレッド構文を使うとArray.fromより若干速いという結果が得られました。

まとめ

以上、JavaScriptでArrayのuniqを実現する様々な手法をご紹介しました。

Webのフロントエンドの開発では計算量が問題になるような事はそう多くないのではないかと思われますが、Nodeで大量のリクエストを捌くような場面や、どれだけの量のデータが渡されるか事前に予想できないライブラリ開発のような場面では、なるべく計算量が小さいアルゴリズムを採用する事が望ましいです。

また、1つの事を実現するのに複数のやり方がある場合には、何を優先するかを事前にきちんと明らかにし、数値で比較可能な場合は特に、この例のようにベンチマークを取ってそれぞれのやり方の優劣を比較する事が大事です。

性能測定の結果を踏まえると、処理速度的には、少なくとも今回の実験環境においては

  • SetとArray.fromまたはスプレッド構文の組み合わせが最もおすすめ。
  • ただし、「要素数が小さい配列を」「頻繁に（多数）処理する」という前提がある場合には、SetやMapを使わない方法の方がおすすめ。

という事が言えそうです。ベンチマークに使用したスクリプトはGistで公開していますので、皆さんもぜひお手元で試してみて下さい。

タグ: JavaScript

関連記事

2018-12-27
«前月 最新記事 翌月»
タグ:
年・日ごとに見る
2008|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|04|05|06|07|08|09|10|11|12|
2012|01|02|03|04|05|06|07|08|09|10|11|12|
2013|01|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|04|05|06|07|08|09|10|11|12|
2020|01|02|03|04|05|06|07|08|09|10|11|12|
Generated by tDiary version 5.0.8
Powered by Ruby version 2.7.0-p0