パフォーマンスの改善とアルゴリズム

Posted on 2011/03/18 by supermab

前回のPOST～Excel-DNA で XLL をつくる（その６）～では、総当たり法で素数判定を行う処理を VBA と XLL で記述し比較しましたが、どちらも実用になるような処理時間ではありませでしたね(笑)
そこで今回は、ちょっと脱線してアルゴリズムについて書いてみようかと思います。前回作成したプログラムのアルゴリズムを改良して、処理時間を短縮してみます。まず、前回書いたコードを眺めてみましょう。

C#

public static bool IsPrime(int x)
{
for (int i = 2; i <= x / 2; i++)
{
if (x % i == 0)
{
return false;
}
}
return true;
}


VB.NET

Public Shared Function IsPrime(x As Integer) As Boolean
For i As Integer = 2 To x \ 2
If x Mod i = 0 Then
Return False
End If
Next
Return True
End Function

このコードは、与えられた整数 x を 2 から x/2 までの整数で試し割りをして、割り切れれば素数ではないと判定し、処理を中断してFALSE を返します。ですから、例えば x が偶数であれば一度 2 で割るだけですので、非常に短時間で処理が終わりますが、x が素数のときは x/2 までの全ての数で割り算を実行しますので、x が大きな数の場合は途方もなく時間がかかってしまいます。どうやって改善できるでしょうか？・・・まず、 x/2 まで調べれば良いことは自明ですね。では 3 で割り切れなければ、x/3 まで調べればいいのでは？・・・調べる数が減って、その分早く処理が終わるはずです。それに、偶数を調べる必要はありませんね。
（こんな感じ↓）
C#

public static bool IsPrime2(int x)
{
if(x % 2 == 0 && x != 2) return false;
if(x % 3 == 0 && x != 3) return false;
for (int i = 3; i <= x / 3; i+=2)
{
if (x % i == 0)
{
return false;
}
}
return true;
}


VB.NET

Public Shared Function IsPrime2(x As Integer) As Boolean
If x Mod 2 = 0 AndAlso x <> 2 Then
Return False
End If
If x Mod 3 = 0 AndAlso x <> 3 Then
Return False
End If
For i As Integer = 3 To x \ 3 Step 2
If x Mod i = 0 Then
Return False
End If
Next
Return True
End Function


Excel での Long の最大値（2147483647）を私の環境で判定してみると、IsPrime メソッドが約5.5sec かかるのに対して、IsPrime2 メソッドは約1.8sec で処理出来ます。実に３倍の高速化になりました。
もう少し、頑張ってみましょう。もし、3 で割り切れなければ x/3 より大きな数で割っても無意味 ⇒ 5 で割り切れなければ x/5 より大きな数で割っても無意味 ⇒　・・・　と、どこまで調べる範囲を少なく出来るか考えると、 x の平方根までですね。では、IsPrime3 を書いてみましょう。
（こんな感じ↓）
C#

public static bool IsPrime3(int x)
{
if(x % 2 == 0 && x != 2) return false;
if(x % 3 == 0 && x != 3) return false;
for (long i = 3; i * i <= x; i+=2)
{
if (x % i == 0)
{
return false;
}
}
return true;
}


VB.NET

Public Shared Function IsPrime3(x As Integer) As Boolean
If x Mod 2 = 0 AndAlso x <> 2 Then
Return False
End If
If x Mod 3 = 0 AndAlso x <> 3 Then
Return False
End If
Dim i As Long = 3
While i * i <= x
If x Mod i = 0 Then
Return False
End If
i += 2
End While
Return True
End Function

かなり高速化して、Timer関数では計測出来なくなってきました。
Excel で複雑処理を行うシートを作って処理が重くなったときに、処理時間を詳細に計測してボトルネックを探す方法が、（MSDN）パフォーマンスの改善 にのっており、ここにMicroTimer のコードが記載されていますので、これを使って計測します。
（こんな感じ↓）

Private Declare Function getFrequency Lib "kernel32" _
Alias "QueryPerformanceFrequency" (cyFrequency As Currency) As Long
Private Declare Function getTickCount Lib "kernel32" _
Alias "QueryPerformanceCounter" (cyTickCount As Currency) As Long</code>

Function MicroTimer() As Double

' Returns seconds.
Dim cyTicks1 As Currency
Static cyFrequency As Currency
'
MicroTimer = 0

' Get frequency.
If cyFrequency = 0 Then getFrequency cyFrequency

' Get ticks.
getTickCount cyTicks1

' Seconds
If cyFrequency Then MicroTimer = cyTicks1 / cyFrequency
End Function

Function IsPrimeVBA(target As Long) As Boolean
Dim i As Long
IsPrimeVBA = True
For i = 2 To target / 2
If target Mod i = 0 Then
IsPrimeVBA = False
Exit For
End If
Next
End Function

Sub CalculateTime()
Dim start, finish
Dim is_prime As Boolean
With ActiveSheet

start = MicroTimer
is_prime = Application.Run("IsPrime", .Range("A1").Value)
finish = MicroTimer
Debug.Print (is_prime &amp; ":IsPrime time= " &amp; Round(finish - start, 7))

start = MicroTimer
is_prime = Application.Run("IsPrime2", .Range("A1").Value)
finish = MicroTimer
Debug.Print (is_prime &amp; ":IsPrime2 time= " &amp; Round(finish - start, 7))

start = MicroTimer
is_prime = Application.Run("IsPrime3", .Range("A1").Value)
finish = MicroTimer
Debug.Print (is_prime &amp; ":IsPrime3 time= " &amp; Round(finish - start, 7))

End With
End Sub

CalculateTime　で実行時間を計測したところ、私の環境では、IsPrime3 は 0.0012sec で処理できました。IsPrime(5.5sec) と比較すると、じつに 4500倍以上の高速化です。
でも、総当たりですので、幼稚と言えば幼稚・・・突っ込みも入りそうなので、もうひと息ガンバって・・・このアルゴリズムを実装してみます(笑) ⇒ ミラーラビン素数判定法
でも、冪剰余の計算が・・・。こんなとき、Excel-DNA は手軽に.NetFramework を利用できて便利です！
今回は、冪剰余の計算に、System.Numerics.Bigintger クラス構造体の ModPow メソッドを利用しました。
（こんな感じ↓）
C#


using System.Numerics;
using System.Collections.Generic;

public class Prime
{
public static bool MillerRabin(string trg)
{
BigInteger X = BigInteger.Parse(trg);
List<BigInteger> exp_list = new List<BigInteger>();
BigInteger tmp = X - 1;
exp_list.Add(tmp);
while (tmp % 2 != 0)
{
tmp /= 2;
exp_list.Add(tmp);
}

int[] b_arry = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
foreach (int b in b_arry)
{
BigInteger big_b = new BigInteger(b);
foreach (BigInteger exp in exp_list)
{
BigInteger mod = BigInteger.ModPow(b, exp, X);
if (mod != 1 && mod != X - 1)
{
return false;
}
}
}
return true;
}
}

VB.NET


Imports System.Numerics
Imports System.Collections.Generic

Public Class Prime
Public Shared Function MillerRabin(trg As String) As Boolean
Dim X As BigInteger = BigInteger.Parse(trg)
Dim exp_list As New List(Of BigInteger)()
Dim tmp As BigInteger = X - 1
exp_list.Add(tmp)
While tmp Mod 2 <> 0
tmp /= 2
exp_list.Add(tmp)
End While

Dim b_arry As Integer() = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
For Each b As Integer In b_arry
Dim big_b As New BigInteger(b)
For Each exp As BigInteger In exp_list
Dim [mod] As BigInteger = BigInteger.ModPow(b, exp, X)
If [mod] <> 1 AndAlso [mod] <> X - 1 Then
Return False
End If
Next
Next
Return True
End Function
End Class

私の環境では、0.00035sec で処理できました。IsPrime の5.5sec と比較すると実に 14,000倍以上 高速になりました。
これは、アルゴリズムが、プログラミングにおいては非常に重要なことを示しています。

今回作成したコードと実験用のbook はこちら ⇒ IsPrime.zip

では、また(笑)

[googlead]

This entry was posted in Excel, ．NetFramework and tagged , . Bookmark the permalink.

2 Responses to パフォーマンスの改善とアルゴリズム

  1. y sakuda says:
    2011/03/18 at 6:18 PM

    >アルゴリズムが、プログラミングにおいては非常に重要なことを示しています。
    そりゃそうでしょｗ

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *