Edited at

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サイト。


アウトプット

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


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万までの値を掲載していました


    • 天文部と友愛数のつながりが気になります