Elixir入門~友愛数を題材にGolangとの性能比較

はじめに

関数型のパラダイムに触れてみたく、Elixirに入門してみた。
実装対象は友愛数を求めることとした。
性能比較のためにGolangでの実行結果と比較した。

Elixirの書き方の参考、性能の目安にしていただければ幸いです。

What's 友愛数

友愛数（ゆうあいすう、英: amicable numbers）とは、異なる 2 つの自然数の組で、自分自身を除いた約数の和が、互いに他方と等しくなるような数をいう。 双子数、親和数（しんわすう）とも呼ばれる。 最小の友愛数の組は (220, 284) である。

220 の自分自身を除いた約数は、1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 で、和は 284 となる。一方、284 の自分自身を除いた約数は、1, 2, 4, 71, 142 で、和は 220 である。
by Wikipedia

友愛数を求めるための実装方針

• 1からMAX値まで
  • 約数を求める
  • 約数の和を求める
  • 約数の和の約数を求める
  • 約数の和の約数の和を求める
  • 「元の数」と「約数の和の約数の和」が一致したら友愛数として出力する

なお、約数のメモ化や、確定済み友愛数のスキップなどは行わない。

Elixirでの実装

インプット

言語仕様を知る上でインプットにしたのは、以下2サイト。

• 公式ドキュメント(https://elixir-lang.org/getting-started/introduction.html)
  • わかりにくいがページ右側のタブで 2. Basic typesなどを順に選ぶと次に進める
  • 一部日本語に訳されたページもある(https://elixir-lang.jp/getting-started/introduction.html)
• Elixirの入門の独り言(https://qiita.com/kuwa0224/items/875a8f7438a9229b086f)
  • 多言語、他パラダイムから入門した時に感じるであろう諸々の疑問を、FizzBuzzをブラッシュアップしながら丁寧に記述してある
  • 入門者は本記事を読む前にこちらの記事を読んでおくと良い
  • もっと評価されるべき

アウトプット

実装の全量は以下の通り。順に解説する。

amicable.ex

defmodule AmicableNumber do
  import ExPrintf

  def run(start, limit) do
    # 分散処理のための記述
    parent = self()
    # for文
    pids = Enum.map(1..limit, fn(n) ->
      spawn fn ->
        # 子プロセスに、amicable(n)を計算した結果を親プロセスに返すよう命令
        send parent, amicable(n)
      end
    end)
  end

  # 友愛数が見つかったら出力する
  defp amicable(n1) do
    # 元の数字の約数を求める
    fact1 = factorize(n1)
    # 元数字の約数の和を求める
    n2 = Enum.reduce(fact1, fn(n, acc) -> n + acc end)
    # 元数字の約数の和の約数を求める
    fact2 = factorize(n2)

    # 元数字の約数の和の約数の和と、元数字が一致したら出力    
    if n1 == Enum.reduce(fact2, fn(n, acc) -> n + acc end) && n1 != n2 do
      printf "%10d, %10d\n", [n1, n2]
    end
  end

  # 約数を求めてmapを返却する
  defp factorize(n) do
    # 割り切れる数字が約数になるので約数一覧のmapが得られる
    fact = Enum.filter(1..trunc(n*0.5+1), fn(i) -> rem(n, i) == 0 end)
    fact
  end
end

# ここが最初に実行される
# 標準入力で受けた値の最初の値を取り出して数字に変換
limit = System.argv |> List.first |> String.to_integer;

# 引数を2つ渡してAmicableNumberモジュールのrunメソッドを呼んでいる
IO.puts AmicableNumber.run(1, limit);

はじめに実行されるのは以下。
値をパイプ(|>)で渡して行く様子が独特。

amicable.ex

# ここが最初に実行される
# 標準入力で受けた値の最初の値を取り出して数字に変換
limit = System.argv |> List.first |> String.to_integer;

# 引数を2つ渡してAmicableNumberモジュールのrunメソッドを呼んでいる
IO.puts AmicableNumber.run(1, limit);

上記から呼び出されたrunメソッドの実装。
子プロセスを生成して処理をさせている。

amicable.ex

  def run(start, limit) do
    # 分散処理のための記述
    parent = self()
    # for文
    pids = Enum.map(1..limit, fn(n) ->
      spawn fn ->
        # 子プロセスに、amicable(n)を計算した結果を親プロセスに返すよう命令
        send parent, amicable(n)
      end
    end)
  end

以下のamicable()で、与えられた値と対になる友愛数があるか確認し、あれば出力する。
Enum.reduceとあるのは第一引数のmapの中身それぞれに処理をした結果の唯一の値を出力できる。
ここでは和を求めている。
ElixirではEnumとmapをよく使う。
なお、n1==n2の場合は友愛数ではなく完全数になるので出力していない。

amicable.ex

  # 友愛数が見つかったら出力する
  defp amicable(n1) do
    # 元の数字の約数を求める
    fact1 = factorize(n1)
    # 元数字の約数の和を求める
    n2 = Enum.reduce(fact1, fn(n, acc) -> n + acc end)
    # 元数字の約数の和の約数を求める
    fact2 = factorize(n2)

    # 元数字の約数の和の約数の和と、元数字が一致したら出力    
    if n1 == Enum.reduce(fact2, fn(n, acc) -> n + acc end) && n1 != n2 do
      printf "%10d, %10d\n", [n1, n2]
    end
  end

以下メソッドで愚直に約数を求める。
Enum.filterで条件に合う要素を抽出したmapを出力している。
remは多言語での%に対応し、割った余りを求めている。
rubyなどと同様、メソッドの最後の行がメソッドの戻り値になる。

amicable.ex

  # 約数を求めてmapを返却する
  defp factorize(n) do
    # 割り切れる数字が約数になるので約数一覧のmapが得られる
    fact = Enum.filter(1..trunc(n*0.5+1), fn(i) -> rem(n, i) == 0 end)
    fact
  end

Golangでの実装

性能比較のため、Golangでも実装してみた。
愚直に記載したため不備があれば指摘いただきたい。
なお、Elixirの記事なので詳細は解説しない。

なぜかこちらはMAXがハードコードされているのと、並列上限を設定したがElixir側では実装が面倒そうだったので直列になるよう並列度をMAXとあわせている。直すのが面倒... 本当にごめんなさいでした。

amicable.go

package main

import (
	"fmt"
	"sync"
)

type Fact struct {
	Num  int
	Fact []int
}

var MAX = 100000
var START = 2

var PARALLEL_NUM = 100000

func main() {
	var wg sync.WaitGroup
	semaphore := make(chan int, PARALLEL_NUM)
	for i := START; i <= MAX; i++ {
		wg.Add(1)
		go func(i int) {
			semaphore <- 1
			defer wg.Done()
			isAmicable(i)
			<-semaphore
		}(i)
		wg.Wait()
	}
}

// nが友愛数の片方を担うかどうかを判定
func isAmicable(n int) bool {
	s := factorize(n)
	sum1 := 0
	for _, v := range s {
		sum1 += v
	}

	s = factorize(sum1)
	sum2 := 0
	for _, v := range s {
		sum2 += v
	}
	if n == sum2 && n != sum1 {
		fmt.Println(n, sum1)
	}

	return n == sum2
}

// 因数分解結果を返却
func factorize(n int) []int {
	var fact []int
	for i := 1; i < int(float64(n)*0.5+1); i++ {
		if n%i == 0 {
			fact = append(fact, i)
		}
	}
	return fact
}

性能比較 Elixir vs Golang

実行環境

Macのローカルで様々なアプリが動いてる状況で実行。
それぞれの言語バージョンは、2018年12月現在、大体最新。

ハード: MacBook Pro (Retina, 13-inch, Early 2015)

$ elixir --version
Erlang/OTP 21 [erts-10.1.2] [source] [64-bit] [smp:4:4] [ds:4:4:10] [async-threads:1] [hipe] [dtrace]

Elixir 1.7.4 (compiled with Erlang/OTP 21)

$ mix --version
Erlang/OTP 21 [erts-10.1.2] [source] [64-bit] [smp:4:4] [ds:4:4:10] [async-threads:1] [hipe] [dtrace]

Mix 1.7.4 (compiled with Erlang/OTP 21)

$ go version
go version go1.11.2 darwin/amd64

詳細条件

• timeコマンドはMacのデフォルトはLinuxと違うらしいので/usr/bin/timeを明示的に指定する
• 友愛数を求める上限は10万とする。

結果(raw)

Elixirの結果

$ /usr/bin/time mix run ./lib/amicable_number.ex 100000
Compiling 1 file (.ex)
warning: variable "pids" is unused
  lib/amicable_number.ex:9

warning: variable "start" is unused
  lib/amicable_number.ex:5

       220,        284
       284,        220
      1184,       1210
      1210,       1184
      2924,       2620
      2620,       2924
      5020,       5564
      5564,       5020
      6232,       6368
      6368,       6232
     10744,      10856
     10856,      10744
     12285,      14595
     14595,      12285
     17296,      18416
     18416,      17296
     63020,      76084
     66928,      66992
     66992,      66928
     67095,      71145
     71145,      67095
     69615,      87633
     76084,      63020
     79750,      88730
     87633,      69615
     88730,      79750

== Compilation error in file lib/amicable_number.ex ==
** (ArgumentError) argument error
    (stdlib) :io.put_chars(:standard_io, :unicode, [[#PID<0.164.0>, #PID<0.165.0>, #PID<0.166.0>, #PID<0.167.0>, #PID<0.168.0>, #PID<0.169.0>, #PID<0.170.0>, #PID<0.171.0>, #PID<0.172.0>, #PID<0.173.0>, #PID<0.174.0>, #PID<0.175.0>, #PID<0.176.0>, #PID<0.177.0>, #PID<0.178.0>, #PID<0.179.0>, #PID<0.180.0>, #PID<0.181.0>, #PID<0.182.0>, #PID<0.183.0>, #PID<0.184.0>, #PID<0.185.0>, #PID<0.186.0>, #PID<0.187.0>, #PID<0.188.0>, #PID<0.189.0>, #PID<0.190.0>, #PID<0.191.0>, #PID<0.192.0>, #PID<0.193.0>, #PID<0.194.0>, #PID<0.195.0>, #PID<0.196.0>, #PID<0.197.0>, #PID<0.198.0>, #PID<0.199.0>, #PID<0.200.0>, #PID<0.201.0>, #PID<0.202.0>, #PID<0.203.0>, #PID<0.204.0>, #PID<0.205.0>, #PID<0.206.0>, #PID<0.207.0>, #PID<0.208.0>, #PID<0.209.0>, #PID<0.210.0>, #PID<0.211.0>, #PID<0.212.0>, ...], 10])
    (elixir) lib/kernel/parallel_compiler.ex:206: anonymous fn/4 in Kernel.ParallelCompiler.spawn_workers/6
      146.00 real       508.54 user         2.17 sys

最後にエラーが出てしまうので、改善したいけどよくわからない。
サンプル拾ってきても並列実行すると起きるので環境問題っぽい。
最後まで計算は進んでるようなので一旦OKとする。

Golangの結果

$ /usr/bin/time go run amicable_number.go
220 284
284 220
1184 1210
1210 1184
2620 2924
2924 2620
5020 5564
5564 5020
6232 6368
6368 6232
10744 10856
10856 10744
12285 14595
14595 12285
17296 18416
18416 17296
63020 76084
66928 66992
66992 66928
67095 71145
69615 87633
71145 67095
76084 63020
79750 88730
87633 69615
88730 79750
       44.44 real        43.22 user         1.09 sys

比較

real	user	sys
146	508	2.17
44.44	43.22	1.09

CPU時間(user)の比較で、Golangの方が11倍高速...で良いのかな。
実装方法によってもだいぶ変わりそうなので、何か気づかれた方はコメントいただけると嬉しいです。

Tips

• 友愛数については、5年ほど前に「博士の愛した数式」という映画で初めて目にして以来、様々な言語で実装してきました
• 友愛数の値一覧の公開情報としては、兵庫県立明石北高等学校の天文研究部が5年前の時点で1000万までの値を掲載していました
  • 天文部と友愛数のつながりが気になります