やわらかテック

興味のあること。業務を通して得られた発見。個人的に試してみたことをアウトプットしています🍵

【並行コンピューティング技法】第2章のまとめ

Algorithm Elixir Erlang 本読んだぞ computer science

前回までのあらすじ

以前から気になっていた「並行コンピューティング技法」を衝動買い。全体の構造を読み解き、どんな知識がこの本から得られるかを考察した。合わせて、第1章を読み、内容を簡潔にまとめた。第1章は大きく以下のような内容を扱っている

  • 並行と並列の違い
  • 並行までの(現在の逐次処理を並行処理に書き直すため)の4ステップ

www.okb-shelf.work

続いて、第2章を読み進めていこう

第2章

まずは前回同様に、見出しから第2章からどんな情報が得られるのかをざっくりと観察してリスト出ししてみた。

  • 並行処理にするための2つの手法
    • タスクの分解(特徴とサンプル)
    • データの分解(特徴とサンプル)
  • 並行不可能な場合の例(実際にはタイトルは適切ではなく、並行不可能な場合の回避テクニックに近い)

「並行処理にするための2つの手法」は実は第1章で既に登場した話であり、第2章では、この部分をより深掘りにしている。並行までの4つのステップの中の「スレッド化したいところを見つける」と「実行」の中間部分にあたるのではないだろうか。

並行処理にするための2つの手法

どちらかというと「データの分解」の方がしっくりくる。機械学習などで前処理を大量のデータに対して実行していく場合が想定しやすい。その一方でタスクの分解というと、メインの処理として逐次に実行すると処理が停止してしまうため、別スレッドやプロセスにて別処理を行うというイメージが強い(eg: メールの送信処理が完了までresponseを返さないのではなく、メールの送信処理は別スレッドにて実行し、メインの処理ではresponseを返してしまう)。というのが、私の2つの手法に対する事前に持ち合わせていた前知識だが、実際にどうなのかを確認していこう。

ここで基本用語が登場。「連続的整合性」は覚えざるを得ない。従来の逐次処理を並行処理に書き換えた際に、逐次処理として実行していた時の最終の結果が不変ではいけないという用語。つまり、並行処理は「連続的整合性」を必ず持っている必要がある。

タスクの分解

タスクとは何か

ここでいうタスクというのは「関数」であったり、処理を連ねた「パイプライン」であったりする。実装されたコードを熟知していればパーツ化可能なタスクを見つけ出すことは容易に行うことが可能だろう。タスクを別スレッドにて実行し、終了するまでの流れは基本的には変わらない。

  • タスクを別スレッドにて起動
  • タスクを実行していたスレッドが停止、もしくはスリープ(再開可能な状態で待機)
  • メインのスレッドにて処理の終了を検知・管理
2つの原則

タスク分解する際の2つのお約束。以下引用。守ろう。

最小でもスレッド数(またはコア数)と同じ数のタスク数にする。
タスク内の処理量(粒度)はタスクやスレッドの管理に伴うオーバーヘッドよりも多くしなければならない

2つ目のがよく分からない。と思ったら、本書に解説がある。狙いは性能を向上させること。また、タスク内の処理量を「粒度」と呼ぶ。タスクを分解することで、メインスレッドにはスレッドの立ち上げ、他スレッドにて実行しているタスクの制御・管理などの本来、逐次処理を記述している際には発生しなかったオーバーヘッド(負荷となる処理)が発生する。スレッドが多くなればなるほど、オーバーヘッドが増えていくとすると、タスク量に対してスレッド数が適切でないと、オーバーヘッドの量が増え、元々の逐次処理よりも処理量が多くなり、性能が悪くor現状維持になってしまう可能性がある。そのために、タスク量とスレッド数のバランスを取るのが重要になる。 そのため、最低でもスレッド数とタスクの数は揃えるのだそうだ。

タスク間の依存性

例えば、算出値をmapやlistに保持する場合に複数のスレッドから行うと、データの整合性が取れなくなる可能性が高い。これがデータへの依存。もう1つが、実行順序に対する依存。Aの値がなければBの値が算出できないなど。

サンプル: 数値積分

ある関数が描く曲線の指定の定義域の下部の領域の面積を求めるタスクの分解を筆者と考える。が、筆者曰く、「読者に頑張ってほしい」とのことで具体的な回答は載っていない。問題の意味を理解する時間は自分にとって重要ではないので、何をすればいいのかだけ何となく分かった。要は積分を行う、定義域をスレッド毎に分割して、各スレッドにて算出された値を合計すれば良いのではないか

データ分解

共通する処理を分割したデータに対してスレッド毎に行う並行化の手法。データを分割して「チャンク(連続性を持つ部分領域?? -> マイクラのチャンクで考えると分かりやすい)」というものを作成して各チャンクを対象にそれぞれのスレッドにてタスクを実行する。となると、以下の２点が重要になる。

  • どのようにデータをチャンクに分解するのか
  • 各タスクが更新すべきデータにアクセスするには(アクセス可能な保証)

minecraft-ja.gamepedia.com

チャンクの分割方法

正直なところ、どんな分割方法を採用したとしても動作はする。しかしながら、分割の方法によって性能が左右される。どのような場合かというと、他のスレッドにて扱われているチャンクを参照する場合に発生する。
仮に4x4の行列を1x1のチャンク16個に分割した場合に他スレッドの全てのチャンクを参照しようとすれば16-1=15のチャンクに対してやりとりを行う必要がある(その分、1回あたりのデータ量は少なくなるだろうが)。これは先ほど話したオーバーヘッドになり得る。また別の場合、2x2のチャンク4個に分割した場合に全てのチャンクを参照しようとすれば4-1=3回のやりとりだけで済む。しかしながら、一度のやりとりで扱うデータ量は増える。そのためどのような形状にチャンクを分割するのか、データを交換するのかが重要になる。一般的には「処理の粒度(タスクの処理量)とチャンクの境界(4x4の行列を2x2の2つに分割した場合の境界は3ブロック)の比率を最大」にすれば良いらしい。

f:id:takamizawa46:20200209121635j:plain

データへのアクセス

アクセス可能な保証というのがタイトルにあるが、実際にはどのようにデータをスレッド同士で参照するかという話。先ほど記述したように、スレッド同士でmessage passingや共有メモリを参照をすることでデータのやり取りを行うが、ここではゴーストセルと呼ばれる、チャンク分割時に各スレッドのストレージ(TLS -> thread local storage)にデータのコピーを行う方法の話がメイン。便利ではあるが、コピーするデータのサイズやコピー回数など、決して万能ではない旨が記述されている。

サンプル: 有限グリッドのライフゲーム

ライムゲームのグリッドを読者の任意のサイズで区切って(チャンクに分割)、並行化するとどうなるのかを考える。先ほどのサンプルと同様で、答えはなく読者が自発的にデータ分割について考えるためのサンプル。ライフゲームは以前、作成したことがあったので何をやればいいのかが何となく分かったので、思ったようにデータ分割について考えてみた

  • 全体のグリッド(NxN)をMxMのチャンクに分割(※ただしM < N)
  • 分割する際に、生死判定に必要となる隣接の単位グリッドをゴーストセルに確保
  • 生死判定のプログラムを単位グリッドにそれぞれのチャンクを持つスレッドにて実行 <- 並列化はココ
  • 集計値(次のグリッド)をメインのスレッドに集約

こうすることで更新場所が被ることはなく、最小限の隣接するグリッドのみをゴーストセルに配置するだけで、逐次処理を行なっていたコードにほとんど手を加える必要なく実装可能だと思った。

f:id:takamizawa46:20200209121820j:plain

並列化不可能な場合

タイトルには並列化不可能とあるが、実際に読み進めていると並列化不可能な場合に出くわした際にどのように手を加えれば、並列化可能なコードに書き換えることが出来るかというテクニックがまとまっている。なぜ並列化出来ないかという視点だけ覚えて、後から参照出来るようにリストで例をまとめておく

状態を保つアルゴリズム(eg: 乱数値生成のためのseed値など)

注意が必要だが、ほとんどの場合は書き替え可能。各スレッドのTLSに保存するなど。
なお、過去に実は遭遇済み。確かにseed値をTLSではないが、各タスクの実行前に、それぞれのプロセスでseed値をセットするようにした記憶がある

www.okb-shelf.work

漸化式(eg: nを求めるのにn-1の値が必要な式)

データをチャンクに分割した場合に先頭以外の各チャンクの一番目の要素が参照する値が算出前なので存在しないため並行化不可となる。多くの場合は並行化不可能だが、第6章で扱う「プリフィックス サム(prefix sum)」という条件を満たす漸化式であれば並行化可能らしい。

該当する処理

nums = [1, 2, 3, 4, 5]
calced = list()
for n in range(1, 5):
  calced[n] = nums[n-1]
帰納変数(eg: いわゆるインクリメント変数とかカウンタなどと呼ばれるもの)

実行時に帰納変数の状態が期待する数値とは限らないため、注意。帰納変数の値を一般化することで対処可能(関数にしてしまうのが良さそう)

該当する処理

count = 0
for num in range(1, 100):
  if num % 2 == 0:
    count += 1
リダクション(eg: forを回してsumを求めるような列挙可能なデータ構造に対する処理)

sumを求める場合には各スレッドにてチャンクより合計値を算出し、メインスレッドに集約して合計するなどデータのやり取りを工夫すれば対処可能。

該当する処理

sum_ = 0
for n in range(1, 1000, 3):
  sum += n
ループ内依存(eg: 過去の算出値を参照する場合など -> 漸化式にニュアンスは近い)

コードの書き換えによって参照する方法を更新することで対応可能だが、場合によっては処理量が増えることがある模様。

該当する処理

import random

calced = list()
weights = [random.random() for _ in range(500)]
for n in range(5, 505):
  calced[n-5] = weights[n-5] * n

並行化する際の設計時に考慮する4つのスコア

左に本書の単語、括弧内に私が分かりやすく砕いた単語を記述しておく。

  • 1.実行効率(パフォーマンス)
  • 2.簡潔性(シンプルさ)
  • 3.可搬性(使い回しのしやすさ)
  • 4.スケーラビリティ

筆者の観点で上記4つのスコアに優先順位をつけると以下のようになる。
4 > 3 > 1, 2

スケール出来ることが一番重要で、これは時代が変化してプロセッサのコア数が増えたとしても問題なく、コードが動作することを重要視しているからだそうだ。

以上

参考文献

【並行コンピューティング技法】全体の構成と得られる知識 & 第１章のまとめ

物買ったぞ 本読んだぞ Algorithm Erlang Elixir

今回の購入物

前から買おうとは思っていたが、読む時間ないなぁと手を出さずにいた「並行コンピューティング技法」をたまたま立ち寄った本屋にて発見し、思い切って購入。最近、学習に対するモチベーションが下がっているので気持ち新たにスタートするためにも購入

f:id:takamizawa46:20200202140626j:plain:h550

著者について

こちらの初版は2009年で、すでに10年以上経過していることになる(早いなぁ)。著者のClayさんの現職場はIntelで2020年時点で16年の勤務経歴があり、20年以上に渡りマルチコア/マルチスレッドのアルゴリズムなどのコード実装に関わっている大ベテランだ。計算機科学のPhDでもあり、要はめちゃくちゃ強い人。ひえぇ...
LinkedIn: clay-breshears

全体の構成と本書から得られる知識について

本書を詳細に読み始める前に、最初に見出しに目を通して全体の構成がどのようになっているかを考察する。その上で自分が、今から読む本から何の情報を得たいのか、何が分かっていないかをリスト化しておき、頭の中か、紙などにメモしておく。そのためにも、まずは、見出しから考察した本書の全体の構造を考えてみる。本書は第1章から始まり、250程のページを経由して第11章までの構成を持つ。第11章までの構成をざっくりと4つに縮約すると以下のようになった。

  • 1.基礎知識:(並列と並行って何が違うの。スレッドとは、分散メモリとは..etc)
  • 2.並行プログラミングの実装における諸注意・考え方
  • 3.実践(ソートアルゴリズムなどを並行アルゴリズムに書き換え)
  • 4.並行プログラミングでのデバッグ、検証方法について

なるほど。まえがきにある通りに、この一冊を読み通せば、実際に並行処理を設計 -> 実装 -> 検証する上でのポイント、考え方が身に付くようだ。現段階で自分の中に持ち合わせていない知識は1.基礎知識以外のほとんど。よって、この書籍を読み通すことで、今持っている

  • 並行/配列処理
  • プロセス/スレッド/マルチスレッド/マルチコア
  • 分散処理/ノード
  • 分散メモリ/共通メモリ
  • ソートアルゴリズムなど

といった基礎的な単語レベルの知識をどのように設計、実装に転用するかを理解するのが第一目標。その上で検証方法やパフォーマンスチューニングの方法を学ぶことを第二目標とした

第1章

第1章を読む理由

自分の持っている知識が著者の認識と正しいかを確認するため。今更だけど、「並行」と「並列」の違いって確かによく分からない(説明出来ない)ので読んでみる。加えて第1章から得たい知識を頭の中に図化したものを書き出してみた。

f:id:takamizawa46:20200202140650j:plain:h550

この図を完成させるように第1章を読み進めた

第1章のまとめ

並行と並列の違い

まず並行と並列という単語の意味がどのように違うのか。自分は並列処理というのはA,B,C,Dという異なる処理を同時に実行させるもので、並行処理はA,A,A,Aという同じ処理を同時に実行させるものだと思っていたが、実際は大きく違っていた。そもそも並行と並列は同軸にはなくて関係上は

  • 並行
    • 並列

というようになる。並行は並列を内包している。書籍から「並行・並列」の項目を引用する

並行とは複数の動作を実行可能状態に保てる状態を備えていること
並列とは複数の動作を同時に実行できる場合のこと

自分の持っていた知識とは全然違っていた。分かりやすく記憶するためにイメージづけをしておく

影分身をして100人分、一気に修行する
  • 並行 -> 修行を開始して修行中の状態
  • 並列 -> 100人に分身が完了した状態

スレッド化の4ステップ

めちゃシンプル。機械学習の開発フローに似てるかも

  • スレッド化したいところ(独立可能な処理 -> 関数レベル、もしくはパイプライン)を見つける
    • アプリの実装が完了してからの方が望ましい。実装を熟知していればボトルネックを指摘できるが、そうでないときは、処理の計測ツールなどを使ってボトルネックを検出するのもok
  • 実装(本書を読み進めてねとある)
  • 実装したコードの検証と修正
  • パフォーマンスチューニング

共有メモリと分散メモリでの実装

言われてみれば当然のことだが、気になったところだけを簡単にメモっておく

共通部分
  • 分割方法 -> データを分割するのか処理を分割するのか
  • データ量やメモリ使用量によって動的にスケールするかどうか(k8sみたいもん)
異なる部分
  • データの同期の確保 -> 共有メモリへの参照・更新が非同期で行われるとデータの状態が思いもよらない物になるため同期を取る必要がある。
    • 例: 2人が同時にチケットの予約をした場合にチケットはどちらの物にするのか
    • 分散メモリではElixir, Erlangのようにmessage passing(メッセージの送受)によってデータの同期を取る
  • 排他制御 -> データを同期させるために共有メモリを参照・更新できるスレッドを制限する
PRAM(Parallel Random Access Machine)

理解のために簡単に...。複数のCPUが1つ以上のメモリに接続しているRAMモデルを変形した構成。メモリへの参照(読み取り)と更新は「並行 / 排他」のどちらかの条件で実行する(権限のようなイメージ)。

  • 並行 -> 誰(どのスレッド)でもOK
  • 排他 -> 参照もしくは更新できるのは1人(特定のCPUで実行される1スレッド)だけ
Producer-Consumer

共有メモリ上にqueueを配置して、タスクを格納しておき、手が空いたスレッドからqueueを参照してdequeueしてタスクを実行を繰り返すことで効率的に処理を行う

リードライトロック

共有メモリへの参照は値の変化を発生させないため、問題ないが、更新はダメ。更新処理が走った際には参照を一時的にストップ(参照の依頼を待ち状態にする)。更新処理が終了した後に参照が再び可能になる。

第1章については以上です

ElixirのString.contains?で第1引数にbinaryを第2引数に日本語ひらがなを与えるとfalseになる理由についての調査報告

清流elixir computer science Erlang Elixir

事の発端

たまたまElixirでhttp responseのbinary情報に対して、特定の日本語が含まれているかという判定式を記述していたところで、この現象に遭遇した。

iex> body = <<201, 202, 197, ...>>
iex> String.contains?(body, "いちご")
false

間違いなくbinaryの中には第2引数で渡している日本語ひらがな(内部データ的にはこいつもbinary)が含まれているのになぜかfalseになる。この一件をtwitterにて投下したところ、KIKUCHI Yutaka 🌓 菊池 豊さんとこの動作について議論をしたが、なぜそうなるのかの答えにはたどり着けなかった


以降、時間が上手く確保できずで調査をする時間がなかったのだが、空いた時間を作れたのでなぜそうなるのかを調べてみた

問題の判定

iex> ?a
97

iex> ?b
98

iex> ?c
99

iex> ?あ
12354

iex> ?い
12356

iex> ?う
12358

なぜfalseになるのか...

iex> String.contains?(<<97, 98, 99>>, "abc")
true

iex> String.contains?(<<12354, 12356, 12358>>, "あいう")
false

2byteずつ確保されているなら以下の処理はtrueになるのかどうか(ならない)

iex> String.contains?(<<12354, 12355, 12356, 12357, 12358, 12359>>, "あいう")
false

String.contains?の実装を見てみる

まずは公式ドキュメントから。この時点で解決出来るのがベスト

Checks if string contains any of the given contents.
contents can be either a string, a list of strings, or a compiled pattern.

文字列に与えられたコンテンツが含まれているかどうかを確認。 コンテンツは文字列、文字列リスト、もしくはコンパイルされたパターンのどれか。

なるほど、コードサンプルも確認しておこう。第2引数をリストにして複数からor検索で実行出来るのは知らなかった

String.contains?("elixir of life", "of")
true
String.contains?("elixir of life", ["life", "death"])
true

なにやら見慣れない使い方を発見。確かにcompile patternを引数に渡せると説明にあったけど、そもそもcompile patternが何か分からん

iex> pattern = :binary.compile_pattern(["life", "death"])
iex> String.contains?("elixir of life", pattern)
true

:binaryということはErlangのモジュールなので、Erlangのドキュメントを確認しに行く

about binary module

This module contains functions for manipulating byte-oriented binaries.
Although the majority of functions could be provided using bit-syntax,
the functions in this library are highly optimized and are expected to either execute faster or consume less memory,
or both, than a counterpart written in pure Erlang.

このモジュールには、バイト指向のバイナリを操作するための関数が含まれています。
ほとんどの関数はビット構文を使用して提供しており、このライブラリの関数は高度に最適化されており、
純粋なErlangで記述された関数よりも高速に実行される、もしくはメモリの消費量が少なくなります。

思った通り、バイナリ操作をするための関数群らしい。先ほど、登場した:binary.compile_patternについて確認する。 少々長いので、部分的に公式ドキュメントを引用する。

Builds an internal structure representing a compilation of a search pattern
When a list of binaries is specified, it denotes a set of alternative binaries to search for

なるほど。本当に関数名のまんまでErlangではmatch/3, matches/3などの関数で使用するための検索パターンをバイナリから作成するための関数のよう。 リストの場合も同様で、引数で渡すときはflatなデータを代入してくれなど諸注意についても記述されている。何となく意味と使われ方が分かったので次に進もう

ちなみに以下のコードも試したがダメだった

iex> pattern = :binary.compile_pattern(["あ", "い", "う"])
{:ac, #Reference<0.2806410432.2574385153.63561>}

iex> String.contains?(<<12354, 12356, 12358>>, pattern)

内部実装を見に行こう

compile patternというものも試してみたがtrueに判定されなかった。そもそもcompile patternについての知識が乏しいというのもあるが、一旦考えないこととする。実際にString.contains?がどのように判定を行なっているかを確認するために、Stringモジュールを見てみる

https://github.com/elixir-lang/elixir/blob/v1.10.0/lib/elixir/lib/string.ex#L2188

def contains?(string, []) when is_binary(string) do
  false
end

def contains?(string, contents) when is_binary(string) and is_list(contents) do
  "" in contents or :binary.match(string, contents) != :nomatch
end

def contains?(string, contents) when is_binary(string) do
  "" == contents or :binary.match(string, contents) != :nomatch
end

まずcontains?に関してはパターンマッチを使用して3種類の関数が実装されている。 共通の条件としては第1引数がバイナリであること。ドキュメントに記述があるように、第1引数が空文字の場合にAll matching、trueを返すようなのでor条件式。それに加えた以下の条件によって3つの関数を使い分けしているようだ

  • 1.第2引数が空のリストの場合に固定でfalseを返す
  • 2.第2引数がリストであり、要素を持っている。:binary.match(string, contentes) != :nomatchではない
  • 2.第2引数がリストではなく(排反的に):binary.match(string, contentes) != :nomatchではない

ここで、再びErlangのドキュメントの:binary.matchに戻る。おそらく、こちらでもパターンマッチを使用して複数の関数が定義されているだろう
内部で実装されているErlangのbinary.match/2を直接呼び出してもfalseになる

iex> :binary.match(<<12354, 12356, 12358>>, "あいう")
:nomatch

binary.match/2 について

Erlang Official Document: binary.matchから引用

match(Subject, Pattern) -> Found | nomatch OTP R14B
Types
  Subject = binary()
  Pattern = binary() | [binary()] | cp() # 第2引数がbinaryかbinaryを要素に持つリスト、もしくはcompile pattern
  Found = part()
Same as match(Subject, Pattern, []).

https://github.com/elixir-lang/elixir/blob/v1.10.0/lib/elixir/lib/string.ex#L2188

-spec match(Subject, Pattern) -> Found | nomatch when
      Subject :: binary(),
      Pattern :: binary() | [binary()] | cp(),
      Found :: part().

match(_, _) ->
    erlang:nif_error(undef).

え、どういうこと。これで関数として判定が成り立つってこと?? 単純にErlangのsyntaxを理解出来ていないのか。
returnとしてFound :: part()もしくはnomatch(atom)を返すのは分かるけど、判定をどこでしてるのかが全く分からない。判定をどうやっているかが分からないと今回一番見たい部分を見る事が出来ない。

とりあえず正常にmatchした時のresponseを落ち着いて1回、見てみる

iex> :binary.match("あいう", "あいう")
{0, 9}

このreponseが先ほど確認したFound :: part()に当たるものだろう。part()は内部でbinary()を返している:

-spec part(Subject, PosLen) -> binary() when
      Subject :: binary(),
      PosLen :: part().

気を取り直して、binaryのドキュメントをよく見てると判定をどのようにしているかの旨が記述されているではないか。

part() = {Start :: integer() >= 0, Length :: integer()}
A representaion of a part (or range) in a binary. Start is a zero-based offset into a binary() and Length is the length of that part.
As input to functions in this module, a reverse part specification is allowed,
constructed with a negative Length, so that the part of the binary begins at Start + Length and is -Length long.
This is useful for referencing the last N bytes of a binary as {size(Binary), -N}. The functions in this module always return part()s with positive Length.

先ほど確認したresponseは{Start :: integer() >= 0, Length :: integer()}は上記のように構成されており、Start()はbinary()という基準点からの距離?(offset...うーん、いまいち何を言ってるのか分からないが)を持つらしい。
こんな時は頭を空っぽにして、コードの実行結果を見てみよう。Erlangのドキュメントを参考にpart()関数を呼び出してみる

iex> bin = <<1,2,3,4,5,6,7,8,9,10>> 
<<1, 2, 3, 4, 5, 6, 7, 8, 9, 10>>

iex> :binary.part(bin, {byte_size(bin), -5})        
<<6, 7, 8, 9, 10>>

あーなるほど、offsetと言っているのはsliceを行うというような意味合いなのか。とすると内部でやっていることは大したことではないはず。今回はpart()の第2引数を-5で固定で渡したけど、Elixirのcontains?からは何が渡っているのだろうか...(後日談: これあんまり関係なかった)
先ほどの戻り値は0番目の位置から9byte進んだところまで一致したということを表しているのか

iex> :binary.match("あいう", "あいう")
{0, 9}

つまり、「あ、い、う」それぞれが3byteずつ容量を持っているということか? そう思い<<12354, 12356, 12358>>をiexに打ち込んでみたところ、「あいう」に変換されないことに気づく

iex> bin = <<12354, 12356, 12358>>
"BDF"

iex> :binary.part(bin, {byte_size(bin), -2})
"DF"

どういうことだ..?? byteの情報とcodepointsの情報が一致しないものがあるということだとすれば辻褄が合うが...

# やはり以下の番号が返ってくる
iex(33)> String.to_charlist("あいう")
[12354, 12356, 12358]

そもそもErlangにはcodepointsという概念がないのかもしれないと思い、binaryをbinary listに変換するbinary.bin_tolistを試してみたところ、とんでもないことが分かった。やはり先ほどの予測通り、日本語ひらがなは3byteの情報を持っているようだ

# よく見ると配列の一番最後の要素の値が2ずつインクリメントされている
iex> :binary.bin_to_list("あ")
[227, 129, 130]
iex> :binary.bin_to_list("い")
[227, 129, 132]
iex> :binary.bin_to_list("う")
[227, 129, 134]

仮説が正しいのかを確認

iex> bin = <<227, 129, 130, 227, 129, 132, 227, 129, 134>>
"あいう"

素晴らしい。これならtrueの判定を見る事が出来そうだ

iex> String.contains?(<<227, 129, 130, 227, 129, 132, 227, 129, 134>>, "あいう")
true

なるほど、やはりそうだった。内部でcallしているのがErlangのモジュールに実装された関数であるため、byte情報の取り扱い方が異なるのが原因だと考えられる。Erlangでは日本語ひらがな1文字は3byteの情報で扱うのだが、Elixirでは1byteの情報として扱っている。この違いのせいで、思ったようにtrueの判定にならなかったのだろう

残る疑念

Elixirではbinary情報を1byteで扱っている、Erlangでは日本語ひらがなに関しては3byteで扱っていると記述しているが、これは本当にbyteなのか。単位が正確ではない気がする。1codepointが正しい??

参考文献

【擬似実装コード有り】Pythonでswitch構文っぽいものを表現する方法について

computer science Python

かゆい所に手が届くswitch構文

別にswitch構文がなくても、おそらくその処理は工夫次第で記述することが可能だろう。しかし、golangやjavascriptに見られるswitch構文を用いることで少なくとも可読性は上がるし、拡張性もif elseの組み合わせよりは良いはず。それにif elseの組み合わせで複雑な多条件を表現すると階層化されて条件がネストされるため視認性が下がるので、好きではない。switch構文なら見かけ上ではcaseA, caseB, caseC...は対等に見えるので視認性はこちらの方が良い(実際の内部処理は上から辿っている模様)

別にswitchがなくても処理は書ける
golang

func FizzBuzz(num int) string {
  if num % 15 == 0 {
    return "fizzbuzz"
  } else if num % 3 == 0 {
    return "fizz"
  } else if num % 5 == 0 {
    return "buzz"
  }
  return "no match"
}

switch構文を使えば可読性と拡張性が増す
golang

func FizzBuzz(num int) string {
  // switchに渡す条件をtrueにしておけば条件式を記述出来る
  switch true {
    case num % 15 == 0:
      return "fizzbuzz"
    case num % 3 == 0:
      return "fizz"
    case num % 5 == 0:
      return "buzz"
  }
  return "no match"
}

仮に「七の倍数の時はラッキーって出力しておいて〜」という仕様が急に決まったとしても以下のようにするだけで改修は終わる(ただし、評価順は上から順なので注意)

// 7の倍数という条件の方を優位にさせるため、 num % 3 == 0の上に記述(最初に21で被る)
func FizzBuzz(num int) string {
  // switchに渡す条件をtrueにしておけば条件式を記述出来る
  switch true {
    case num % 15 == 0:
      return "fizzbuzz"
    case num % 7 == 0:
      return "ラッキー"
    case num % 3 == 0:
      return "fizz"
    case num % 5 == 0:
      return "buzz"
  }
  return "no match"
}

「お、こんな便利な構文使わん理由ないやん、よっしゃPythonでも書いたろ」と思っても残念。Pythonにはswitch構文は実装されていない。理由は以下の公式ドキュメントのQAにて書かれている通り

docs.python.org

if... elif... elif... else の繰り返しで簡単に同じことができます。switch 文の構文に関する提案がいくつかありましたが、範囲判定をするべきか、あるいはどのようにするべきかについての合意は (まだ) 得られていません。

一言で言えば、他に書く方法あるから、それで何とかしてね。って感じかな。おっしゃる通りだけど、あってもいい気はする。で、このPythonにswitch構文を導入するかどうかは2001年頃から議論されており、拒否されているよう。
www.python.org

それでもそれっぽいswitch構文が使いたい

です。なので、それっぽいのを記述する。すでに多くの先駆者がif else使ったり、dictionaryにkeyをセットして関数をvalueに持たせたりと既出のものが多いので自分が調べた限り、この書き方は確認出来なかったので載せておく。正直な所はO(1)で高速にアクセス可能なdictionaryのkeyとvalueを使った複数条件処理を推したいところではある

if false: でネストさせるやつ

どういうこと。とりあえずコードを見せる

def fizzbuzz(num):
  """
    num -> int
    return -> int
  """
  if False:
    pass
  elif num % 15 == 0:
    print("fizzbuzz")
  elif num % 3 == 0:
    print("fizz")
  elif num % 5 == 0:
    print("buzz")

なぜif False:と一番上の条件式に記述をしているかというと、先程話した通り、条件式が見た目上、ネストするのを回避するためと後の拡張性を確保したいからだ。処理としては一判定無駄になってしまうが、前者の理由を優先した。あとはswitch構文同様にcaseと記述して条件式を書くもの、ifでswitch構文っぽく記述するなら全てelifという様に記述できるように意識した。正直、好みの問題だし下記の記述がdefaultだろう

def fizzbuzz(num):
  """
    num -> int
    return -> None
  """
  if num % 15 == 0:
    print(num, " is fizzbuzz")
  elif num % 3 == 0:
    print(num, " is fizz")
  elif num % 5 == 0:
    print(num, " is buzz")

無名関数のリストを作るやつ

無名関数を使ってこんなことが出来る

lst = [lambda x: x > 5, lambda x: x < 3]

for i, func in enumerate(lst):
  print(i, "->", func(i))

実行結果

0 -> False # 0 > 5
1 -> True # 1 < 3

この様に無名関数をリストに保持させておくことで実行順序を保証できて、条件式を実行時評価状態にしておくことが出来るので、複雑な条件式を表現可能ということでswitch構文っぽいものが記述出来る。dictionaryを使う場合にはkeyをa, b, cのようにsortされても問題ないように順序を意識してkeyを作成する必要があるため、うーんとなり、この方法が思いついた

# 条件式を内包する無名関数を作成(実行時に評価される)
# Falseを返しているのは実行時に評価式がFalse判定されたことを呼び出し元に伝えるため
conditions = [
  lambda x: "fizzbuzz" if x % 15 == 0 else False,
  lambda x: "fizz" if x % 3 == 0 else False,
  lambda x: "buzz" if x % 5 == 0 else False
]

# 擬似switch構文(値と条件式を含む無名関数のリストを受け取る)
def switch(val, judge_lst, default_res=None):
  """
    # val -> any
    # judge_lst -> list[func]
    # default_res(None) -> any
    # return -> any
  """
  # リストに含まれている関数を順に実行(リストなので)
  for func in judge_lst:
    res = func(val)
    # Flaseが返ってきていない(評価式がtrueとなった)ならbreak
    # この処理を削除すればフォールスルーになる(breakをしないと次の評価式に移るやつ)
    if res:
      return res
  return default_res

実行結果

for i in range(1, 31):
  print(i, " -> ", switch(i, conditions, "no match"))

# 1  ->  no match
# 2  ->  no match
# 3  ->  fizz
# 4  ->  no match
# 5  ->  buzz
# 6  ->  fizz
# 7  ->  no match
# 8  ->  no match
# 9  ->  fizz
# 10  ->  buzz
# 11  ->  no match
# 12  ->  fizz
# 13  ->  no match
# 14  ->  no match
# 15  ->  fizzbuzz
# 16  ->  no match
#  :
# 30  ->  fizzbuzz

今回はサンプルのために、ただ文字列を返すという無名関数を作成したが、無名関数内から定義済み関数をcallしたり、クラスのinstanceを返したりと割とやれることは多いはず。ただ、if else...の実装に比べると明らかに重いので、上手く共通化出来る時ぐらいしか出番はないだろう

conditions = [
  lambda x: str_slicer("fizzbuzz") if x % 15 == 0 else False,
  lambda x: str_slicer("fizz") if x % 3 == 0 else False,
  lambda x: str_slicer("buzz") if x % 5 == 0 else False
]

def str_slicer(str_):
  """
    str_ -> string
    return -> list[string]
  """
  res = list()
  append = res.append
  for s in str_:
    append(s)
  return res

実行結果

for i in range(1, 31):
  print(i, " -> ", switch(i, conditions, "no match"))

# 1  ->  no match
# 2  ->  no match
# 3  ->  ['f', 'i', 'z', 'z']
# 4  ->  no match
# 5  ->  ['b', 'u', 'z', 'z']
# 6  ->  ['f', 'i', 'z', 'z']
# 7  ->  no match
# :
# 29  ->  no match
# 30  ->  ['f', 'i', 'z', 'z', 'b', 'u', 'z', 'z']

総評

すでにPythonでswitch構文の代役に関する記事はそこそこあるが、個人的な興味と久しぶりにPythonを記述機会があったので遊んでみた。if else...を淡々と書き続けていると頭がおかしくなりそうなので、最近は無名関数に条件式埋め込んでってことをよくやる。記事の主題とは関係ないが、Pythonにswitch構文がない理由を調べる中で、「デザインと歴史」というページにたどり着いて、少し読んでみたが面白かった。興味のある項目があったら読んでみるのも良いかもしれない

参考文献

【golang/Elixirのサンプル有り】何度も同じようなテストを書くのがつらいので無名関数を使って楽しくしよう

Elixir golang

反応が良かったツイート

テストを無名関数で書くと楽しいよという旨のツイートの反応が良かった。ただ言葉だけだと正確に情報が伝わらないので実際にどうやっているのかをコードに落としてみた

せっかくなのでgolangとElixirで書いてみた

実際に無名関数を使ってテストを書いてみる

リストに含まれている値を集計し、登場回数をカウントしてmapにして返す

  • go version: go1.12.4 darwin/amd64
  • Elixir version: Erlang/OTP 22 & Interactive Elixir (1.9.4)

golang編

動作の確認

func CountAggregeter(lst []string) map[string]int {
  // 集計用のmap
  aggregater := make(map[string]int, 0)
  for _, val := range lst {
    if _, ok := aggregater[val]; ok {
      aggregater[val] += 1
    } else {
      aggregater[val] = 1
    }
  }
  return aggregater
}

// 実行結果
package main
import "fmt"
func main(){
    // Your code here!
    
    lst := []string{"AAA", "BBB", "AAA", "CCC", "DDD", "BBB", "EEE"}
    res := CountAggregeter(lst)
    fmt.Println(res)
}

// map[AAA:2 BBB:2 CCC:1 DDD:1 EEE:1]

こちらからも確認可能です
play.golang.org

プロジェクト化

$GOPATH以下にディレクトリを作成してファイルを用意する(今回はテストだけを試すのでmain.goはなし)。テストのパッケージはgolangに標準組み込みのtestingを使用する。業務で3ヶ月使っているがシンプルなテストをする上でパフォーマンスは十分で覚えることもほとんどない。

ちなみに$GOPATHは簡単に確認することが出来る

$ echo $GOPATH
/Users/okb/go

/nameless_func_test  
|── /utils  
    |── list.go  
    |── list_test.go

下記に先ほど作成したリストの値をカウントする関数を記述する
./nameless_func_test/utils/list.go

package utils

// リストを受け取り、値の登場回数をカウント
func CountAggregeter(lst []string) map[string]int {
    // 集計用のmap
    aggregater := make(map[string]int, 0)
    for _, val := range lst {
        // 既出であれば+1
        if _, ok := aggregater[val]; ok {
            aggregater[val] += 1
        } else {
            // 初登場であれば1を格納
            aggregater[val] = 1
        }
    }
    return aggregater
}

testingの仕様に従って、_test.goをテストを行いたいファイルの語尾に付ける。今回はlist.goに対してテストを行うのでlist_test.goを作成。そしてお待たせ。ここで無名関数が登場する
./nameless_func_test/utils/list_test.go

// Testという名前をテストを行いたい関数の頭に付けて関数を作成
func TestCountAggregeter(t *testing.T) {
        // 何度も同じ処理を行うため無名関数化
    debuger := func(lst []string, expectMap map[string]int) error {
        // 集計処理を実行
        res := CountAggregeter(lst)

        // 期待する値を用いてloop処理
        for key, val := range expectMap {
            // 値が集計結果に含まれているかどうか
            if cnt, ok := res[key]; ok {
                // カウント数が一致しないのであればerror
                if val != cnt {
                    return errors.New("[Error] カウント数が一致しません")
                }
            } else {
                // そもそも結果に含まれていなければerror
                return errors.New("[Error] 想定値か集計値が間違っています")
            }
        }
        return nil
    }
}

これがテストに使用する無名関数。引数にCountAggregeterに渡すリストと、期待する結果(assertテストとほとんど同じ)を与えて、一致するかをrangeを使って確認するというシンプルな仕上がり。退屈なテストの記述作業が少しは面白くなるはず。
あとはこの無名関数を使ってテストをゴリゴリ書くだけ(ちなみにtestingではエラー終了をさせる時にt.Error()とする)

./nameless_func_test/utils/list_test.go

func TestCountAggregeter(t *testing.T) {
    // シンプルなケース
    if err := debuger([]string{"A", "B", "C", "D"}, map[string]int{"A": 1, "B": 1, "C": 1, "D": 1}); err != nil {
        t.Error(err)
    }

    // 重複した値がうまくカウントされているか
    if err := debuger([]string{"A", "B", "A", "C"}, map[string]int{"A": 2, "B": 1, "C": 1}); err != nil {
        t.Error(err)
    }

    // リストが空の場合
    if err := debuger([]string{}, map[string]int{}); err != nil {
        t.Error(err)
    }

    // 複数の値が重複する場合
    if err := debuger(
        []string{"A", "B", "A", "C", "D", "C", "E", "F", "D", "F", "G"},
        map[string]int{"A": 2, "B": 1, "C": 2, "D": 2, "E": 1, "F": 2, "G": 1},
    ); err != nil {
        t.Error(err)
    }

    // 重複の発生が3回以上
    if err := debuger([]string{"A", "A", "A"}, map[string]int{"A": 3}); err != nil {
        t.Error(err)
    }
}

テストの実行と結果の確認。いいね

$ pwd
/Users/okb/go/src/nameless_func_test

$ go test -v nameless_func_test/utils
=== RUN TestCountAggregeter
--- PASS: TestCountAggregeter (0.00s)
PASS
ok nameless_func_test/utils 0.007s

Elixir編

実はElixirでテストを扱うのは初めて。今まではやってもdoctestでしか記述をしたことが無かった。まずはCountAggregeterと同様の機能を持つ関数の実装を行なった

defmodule Aggregater do
  def counter(lst) do
    Enum.reduce(lst, %{}, fn val, acc ->
      if Map.has_key?(acc, val) do
        Map.put(acc, val, Map.get(acc, val)+1)
      else
        Map.put(acc, val, 1)
      end
    end)
  end
end

Aggregater.counter(["AAA", "BBB", "AAA", "CCC", "DDD", "BBB", "EEE"]) |> IO.inspect

実行結果

> $ iex list.ex  
Erlang/OTP 22 [erts-10.6.1] [source] [64-bit] [smp:4:4] [ds:4:4:10] [async-threads:1] [hipe] [dtrace]

%{"AAA" => 2, "BBB" => 2, "CCC" => 1, "DDD" => 1, "EEE" => 1}
Interactive Elixir (1.9.4) - press Ctrl+C to exit (type h() ENTER for help)

プロジェクト化 & テスト書く

Elixirでのテストの記述に関してはmoduleレベルで扱うのは初めてなので以下の記事を参考にテストを書いてみる

elixirschool.com

ExUnitを扱いたいのでmixの新規プロジェクトを立ち上げる

$ mix new aggregater

実行後色々と生成される。今回、扱うのはlib/aggregater.exとtest/aggregater_test.exの2ファイルのみ。テストとして実行するファイルには.exs形式を用いる必要がある模様。

まずはlib/aggregater.exに先ほど実装した関数を記述
./lib/aggregater.ex

defmodule Aggregater do
  def counter(lst) do
    Enum.reduce(lst, %{}, fn val, acc ->
      if Map.has_key?(acc, val) do
        Map.put(acc, val, Map.get(acc, val)+1)
      else
        Map.put(acc, val, 1)
      end
    end)
  end
end

続いてテストのための無名関数を記述していく
./test/aggregater.ex

defmodule AggregaterTest do
  use ExUnit.Case
  doctest Aggregater

  # テストの命名
  test "test for Aggregater.counter" do
    # lst -> []string
    # expects -> map[string]int
    # 無名関数の作成
    debuger = fn lst, expects ->
      res = Aggregater.counter(lst)
      Enum.each(expects, fn {key, val} ->
        if Map.has_key?(res, key) do
          if val != Map.get(res, key) do
            IO.puts("#{val} == #{Map.get(res, key)}")
            # 想定外の状態が発生した場合に即return
            raise :error
          else
            :ok
          end
        else
          raise :error
        end
      end)
    end
  end
end

無名関数を使って複数のテストを書いてみる

defmodule AggregaterTest do
  use ExUnit.Case
  doctest Aggregater

  test "test for Aggregater.counter" do
    # シンプルなケース
    assert debuger.(["A", "B", "C", "D"], %{"A" => 1, "B" => 1, "C" => 1, "D" => 1}) == :ok

    # 重複した値がうまくカウントされているか
    assert debuger.(["A", "B", "A", "C"], %{"A" => 2, "B" => 1, "C" => 1}) == :ok

    # リストが空の場合
    assert debuger.([], %{}) == :ok

    # 複数の値が重複する場合
    assert debuger.(["A", "B", "A", "C", "D", "C", "E", "F", "D", "F", "G"], %{"A" => 2, "B" => 1, "C" => 2, "D" => 2, "E" => 1, "F" => 2, "G" => 1}) == :ok

    # 重複の発生が3回以上
    assert debuger.(["A", "A", "A"], %{"A" => 3}) == :ok
  end
end

実行してみる

$ mix test Finished in 0.06 seconds
1 test, 0 failures

Elixirで無事に無名関数を使ってテストを実行することが出来た。mixで作成したプロジェクトであればゴリゴリとテストが書いていけそうだ。人によるが自分にとっては退屈なテストケースの記述処理が無名関数を使うことで楽しく効率化することが出来る。ご参考に。全体のコードはこちらから
github.com

追記

いつもお世話になっているfukuoka.exさんの古賀さんより、一筆頂きました

サンプルコードまで書いて頂きました。確かにElixirでテストを書くのであればブロックを分けてシンプルなassertを一文記述する方式の方がどこでErrorになるのかも一目瞭然でクリーンになる。さらにPowerAssertというライブラリがかなりいい感じですね gist.github.com

PowerAssert

t.co

こういう反応がもらえるのが何よりありがたいし、自分のレベルアップが出来る。ありがとうございます🙇‍♂️

参考文献