2012年05月06日

VBScript の配列要素を追加する処理の高速化

VBScript で集合(コレクション)を扱いたいときは、配列を使うことが1つの方法です。 要素を1つずつ追加するときは、次のようにコーディングすることになると思います。

ReDim arr(-1)
For i=0 To n
 ReDim Preserve arr( UBound( arr ) + 1 )
 arr( UBound( arr ) ) = i
Next

このソースコード(以後は「コード」)は、集合に要素を追加したいときに、配列の要素を+1してから、要素を代入する処理をしています。

このコードは、要素数が大きくなると、非常に処理が遅くなります。 n=10万(10万要素)の場合、0.766秒 もかかります。 1秒未満ですが、使っていると引っ掛かりを感じる時間であり、何度も実行するとかなりイライラすることでしょう。

時間がかかっているのは、配列の要素を追加している ReDim Preserve の処理です。 つまり、ReDim Preserve を実行する回数を減らせば、高速化できます。

最初に n=10万 の要素を作成して、ReDim Preserve を1回だけ実行するように改良したコードは、次のようになります。

ReDim arr(-1)
ReDim Preserve arr( n )
For i=0 To n
arr( i ) = i
Next

この場合、0.031秒 で済みます。 25倍も高速になりました。

ただ、このコードは制限事項があります。 最初に全ての要素数が分かっているときだけしか使えないことです。 しかも、ほとんどのケースでこの制限に引っかかってしまいます。

この制限事項がなく、ReDim Preserve を実行する回数を減らすには、必要な要素数がいくつになるか、ある程度、予測することです。 とは言っても、正確に要素数を予測することは不可能です。 そこで、ReDim Preserve を実行する回数がなるべく少なくなるような予測をします。 経験則では、多くのケースで、要素数は100個以下です。 しかし、要素数が何万個になる場合もなくはありません。 それを踏まえたコードは、次のようになります。

ReDim arr(-1)
arr_fast_ubound = UBound( arr )
For i=0 To n
 If UBound(arr) <= arr_fast_ubound Then _
  ReDim Preserve arr( ( arr_fast_ubound + 100 ) * 4 )
 arr_fast_ubound = arr_fast_ubound + 1

 arr( arr_fast_ubound ) = i
Next
ReDim Preserve arr( arr_fast_ubound )

予測をしているのは、( ( arr_fast_ubound + 100 ) * 4 ) の部分です。 この計算式が、要素数の予測をしています。 そして、最後の ReDim Preserve で正確な要素数を設定しています。

ポイントは、( ( arr_fast_ubound + 100 ) * 4 ) の「 * 4 」の部分です。 ReDim Preserve を実行する回数を減らすなら、1個ずつ要素を増やすのではなく、100個ずつ要素を増やすこと ( arr_fast_ubound + 100 ) が考えられます。 その場合、ReDim Preserve を実行する回数は、1000回です。 1000個ずつ要素を増やしても、100回です。 それが、 * 4 を入れるだけで、要素数を級数的に増やすことができ、実行する回数は、たったの 6回です。

この場合、0.125秒 になります。 6倍の高速になりました。

25倍ほどのインパクトはありませんが、制限事項のために使えなくなることがありません。 ところで、実行回数が 10万回から 6回に劇的に減ったのに、6倍しか高速にならないのは、If 文と加算が 10万回実行されることが増えたこともありますが、それほど重い処理ではないため、それよりも、ReDim Preserve を実行するときに増える要素数が大きいほど、速度が遅いことを示しています。 それでも、1ずつ増やす処理を 10万回実行する場合よりも 6倍速いのです。

最初に1度だけ要素数をかなり大きくとって、最後に正確な要素数を設定することも考えられます。 つまり、ReDim Preserve を実行する回数が必ず 2回になります。 そのコードは、次のようになります。

ReDim arr(-1)
ReDim Preserve arr( 100000*15 )
For i=0 To n
 arr( i ) = i
Next
ReDim Preserve arr( n )

このコードは、予測した最大要素数が、実際の要素数の 15倍であったケースに相当します。 この場合、0.125秒 になり、( ( arr_fast_ubound + 100 ) * 4 ) と同じ時間になります。 もし、予測した最大要素数が、実際の要素数の 2倍の場合、0.047秒 になり、かなり高速になります。 しかし、15倍以上なら遅くなります。 つまり、このコードは、あらかじめ予想される最大要素数が、実際の要素数の15倍以内という制限事項が付くコードということになります。 しかも、予想される要素数が「最大」であることが結構キツイです。 また、多くのケースでは、要素数が 100以下なので、どんなケースでも 20万要素を確保してしまうと、返って遅くなるでしょう。

sage_p at 22:27│Comments(0)TrackBack(0)プログラミング 

トラックバックURL

この記事にコメントする

名前:
URL:
  情報を記憶: 評価: 顔