tech.guitarrapc.cóm

Technical updates

PowerShell で1から100までの偶数の和を求めるワンライナー

PowerShell でどういうやり方がいいかを少し考えてみます。

「1から100の偶数の和を求めるワンライナー」まとめ - Qiita

というのがあり、Twitter でつぶやいたのですが、一応まとめておきます。

目次

TL;DR

リスト作ってもいいなら、メソッド方式で。作りたくないなら パイプラインで。 bitwise やシフト演算が最速と思いきや、普通に% (剰余) がいいです。

PowerShell でSIMD 活用ってどうやるといいのかが気になります。

算出方法

どれでもどうぞ。

gist.github.com

いずれも求められますが、大きな違いは2つです。(8つあるのは、2 x 4通りです)

  • フィルター方法がパイプライン or メソッド
  • 偶数の算出が 剰余(modulo) or 除算(division) or ビット演算(bitwise) or シフト演算(shift)

シーケンスの生成

フィルター方法の選択でメモリと実行速度に違いがでます。

  • パイプライン | を使うことで、1~100のメモリ域を確保しないので使用メモリが減る一方で、実行速度は落ちます
  • メソッド(シーケンス).Where{}を使うことで、1~100のメモリ域を確保するため使用メモリが増える一方で、実行速度は上がります

リスト作る必要ないならパイプラインがいいですね。

算出方法とベンチマーク

偶数の算出は、どれを選ぶかで実行速度が違いが出ます。

  • modulo

PowerShellでも算術演算子 % を使えます。奇数は剰余が1、偶数は0です。 よく書きます。

  • bitwise

8ビットで考えます。奇数は20 が常に1なので 1とand(論理積)を演算すれば常に1になります。偶数なら0です。 こっちのほうが早い時には使います。

00000001    
00000001   (00000001 is 1)
       &
--------
00000001

C系の(x & 1) == 0 をPowerShellに翻訳すると ($_ -band 1) -eq 0 になります。

  • division

残術演算子 / を使って2で割って、intで小数点を破棄してかけなおすと元に戻るかです。 明らかに無駄なので普段書きません。

  • shift

偶数の1ビット目が0であるため、右シフトして桁を落として左シフトで0を入れた時に元の値になれば偶数、そうでなく1少なくなれば奇数です。

00000011 (3)
00000001 (>> 1)
00000010 (<< 1)
--------
00000010 (2)

C系の ((3 >> 1) << 1) == 3 をPowerShellに翻訳すると (3 -shr 1) -shl 1 -eq 3 となります。

速度を見てみましょう。計算回数が少なければ早いので、オペレータのコストとJITでの最適化がかかるかがポイントです。

PowerShell は1回一回のベンチマークのずれが激しいので、10000回実行した算術平均をとって一回当たりの実行速度を見てみます。*1

BenchMark(Method) Times Avg(ms)
bitwise 1000 0.542
division 1000 0.521
modulo 1000 0.489
shift 1000 0.520
Benchmark(Pipeline) Times Avg(ms)
bitwise 1000 1.353
division 1000 1.486
modulo 1000 1.330
shift 1000 1.359

gist.github.com

余談 : クラス構文

PowerShellでは、同じ処理でもクラス構文にすると、dllからの呼び出しになるため高速化する傾向にあります。

といっても、偶数判定だけクラス構文にすると遅くなります。

Benchmark(Method) Times Avg(ms)
shift 1000 1.287
class 1000 1.088

gist.github.com

全体をクラス構文にして、インスタンスメソッド、スタティックメソッドでどうなるか見てみると早くなっていないことがわかります。

Benchmark(Class) Times Avg(ms)
bitwise 1000 0.536
division 1000 0.562
modulo 1000 0.533
shift 1000 0.559
Benchmark(Static) Times Avg(ms)
bitwise 1000 0.538
division 1000 0.553
modulo 1000 0.521
shift 1000 0.544

gist.github.com

この程度だと速度差つかないですね。(PowerShell 5.1 / 6.2)

*1:これでも差が出るのでウォームアアップがあるとよりいいですね