julia の Array の vcat() を見直して、組み上げ速度を上げよう

はじめに

julia 0.6.3 で、計算しながら Array を組み上げると、ちょっと時間がかかることがあります。 vcat() と、空の Array への代入はどちらが、早いのでしょうか?

下記の実験で判ったのは、

  1. Array の中に文字列があると、Array の結合は、大幅に速度が落ちます
  2. Array を 数回、 vcat() で結合するなら、 vcat() の実用性は高いです
  3. 文字列ありで、100回程度以上、 vcat() するなら、先に入れ物の Array を作り、代入する方法を検討しましょう

ということです。

数字だけの2つの Array を積み重ねてみよう

まず、A と B という 10^4 × 3 の Array を作ります。 

A = hcat(
  randn(10^4),
  randn(10^4),
  randn(10^4)
  );

B = hcat(
  randn(10^4),
  randn(10^4),
  randn(10^4)
  );

まずは、vcat() で、A と B を積み重ねます。5回、時間を測定してみましょう。 

julia> for i in 1:5
         @time C_vcat = vcat(A,B);
       end
  0.125543 seconds (55.42 k allocations: 3.453 MiB)
  0.000096 seconds (9 allocations: 468.984 KiB)
  0.000380 seconds (9 allocations: 468.984 KiB)
  0.000337 seconds (9 allocations: 468.984 KiB)
  0.000291 seconds (9 allocations: 468.984 KiB)

MacBook Pro が、電池駆動中のためか、少し時間にブレが出ています。

次に、先に入れ物 Array を、Any の型で、組んで代入する関数を作ります。 

function Tum_Tum(A::Array,B::Array)
  size_A = size(A)[1];
  C = Array{Any}(size_A+size(B)[1],3);
  C[1:size_A,:] = A
  C[(size_A+1):end,:] = B
  return C
end

では、測定してみましょう。 

julia> for i in 1:5
        @time Tum_Tum(A,B)
        end
  0.011303 seconds (63.55 k allocations: 1.535 MiB)
  0.000452 seconds (60.01 k allocations: 1.373 MiB)
  0.000619 seconds (60.01 k allocations: 1.373 MiB)
  0.001146 seconds (60.01 k allocations: 1.373 MiB)
  0.001165 seconds (60.01 k allocations: 1.373 MiB)

上記だと、さすがに vcat の方が早いです。

念のため、同じものができているか確かめてみましょう。 

julia> C_vcat == Tum_Tum(A,B)
true

大丈夫でした。私は、10001 行目で結合で良いか? なんて、ちょっぴり不安になります。

では、ここで、Any だった型を、Float64 に変更したら、どうなるでしょう? 

function Tum_Tum_Float(A::Array,B::Array)
  size_A = size(A)[1];
  C = Array{Float64}(size_A+size(B)[1],3);
  C[1:size_A,:] = A
  C[(size_A+1):end,:] = B
  return C
end

では、測定です。 

julia> for i in 1:5
         @time Tum_Tum_Float(A,B)
       end
  0.012903 seconds (3.43 k allocations: 627.708 KiB)
  0.000391 seconds (6 allocations: 468.922 KiB)
  0.000387 seconds (6 allocations: 468.922 KiB)
  0.000654 seconds (6 allocations: 468.922 KiB)
  0.000585 seconds (6 allocations: 468.922 KiB)




 これは良い感じですね。Array の型を指定するのはとても大事ですね。



文字列を含む2つの Array を積み重ねてみよう



 ここで、懲りずに、今度は、string 入りの Array で試してみます。


A2 = hcat(
  randn(10^4),
  randn(10^4),
  "string_".* string.(collect(1:10^4))
  );

B2 = hcat(
  randn(10^4),
  randn(10^4),
  "string_B_".* string.(collect(1:10^4))
  );




 まずは、vcat() で、測定しましょう。もちろん、vcat(A2,B2) で動きます。


  julia> for i in 1:5
           @time = vcat(A2,B2);
         end
  0.211822 seconds (30.92 k allocations: 2.121 MiB)
  0.140495 seconds (9 allocations: 468.984 KiB)
  0.145904 seconds (9 allocations: 468.984 KiB)
  0.142249 seconds (9 allocations: 468.984 KiB)
  0.139703 seconds (9 allocations: 468.984 KiB)




 なんと、string が混った Array の結合は、vcat() は、かなりてこずるようです。


 では、先に Array の型を Any で指定した Array に代入してみましょう。

 この場合は、先程の Tum_Tum() が使えますね。


julia> for i in 1:5
         @time Tum_Tum(A2,B2)
       end
   0.144137 seconds (3.55 k allocations: 634.036 KiB)
   0.137178 seconds (6 allocations: 468.922 KiB)
   0.140681 seconds (6 allocations: 468.922 KiB)
   0.144750 seconds (6 allocations: 468.922 KiB)
   0.140838 seconds (6 allocations: 468.922 KiB)




 なんと、自作 Tum_Tum() がんばっています。


 もちろん、


julia> vcat(A2,B2) == Tum_Tum(A2,B2)
true




 答えは一緒ですね。


 では、入れ物の Array の型を正確に指定してみましょう。


 まず、Array{String}(size_A+size(B)[1]) が、Float64 型の隣りに入らずに苦戦します。


julie> C = hcat(
          Array{Float64}(size_A+size(B)[1]),
          Array{Float64}(size_A+size(B)[1]),
          Array{String}(size_A+size(B)[1])
          );
ERROR: UndefRefError: access to undefined reference




 仕方が無いので、 "" を先に代入して組みます。


function Tum_Tum_FFS(A::Array,B::Array)
  size_A = size(A)[1];
  C_3 = Array{String}(size_A+size(B)[1]);
  for i in 1:length(C_3);C_3[i] = "";end;
  C = hcat(
    Array{Float64}(size_A+size(B)[1]),
    Array{Float64}(size_A+size(B)[1]),
    C_3
    );
  C[1:size_A,:] = A
  C[(size_A+1):end,:] = B
  return C
end




 これは組めました。


 では、測定してみましょう。


julia> for i in 1:5
          @time Tum_Tum_FFS(A2,B2)
       end
  0.187246 seconds (68.13 k allocations: 2.961 MiB)
  0.143167 seconds (40.02 k allocations: 1.526 MiB)
  0.140169 seconds (40.02 k allocations: 1.526 MiB)
  0.140350 seconds (40.02 k allocations: 1.526 MiB)
  0.155728 seconds (40.02 k allocations: 1.526 MiB, 8.37% gc time)






 vcat() を越えるかも? と夢を見ましたが、さすがに、vcat() は越えられません。

 やはり、string 型の列を作るあたりで、余計な作業なのでしょう。



どうしても、1行ずつ Array を作らないといけない場合はどうだろう



 ここで、もう少し、特殊な場合を考えます。

 どうしても 1 行ずつ計算をして求めないといけない場合はどうでしょう。

 実数 x を、計算式に入れて f(x) を求めて、note という文字列を付けることにします。

  [x, f(x), note] 

  という行を、次々に積み重ねていくことにします。
  今回は複雑な計算は思いつきませんので、f(x) = sin(x) としてみることにします。


 では、まず、vcat() ばかりの関数の定義をします。


function vcat_test(n::Int64)
  array_ans = []
  array_ans = hcat(1, sin(1), "hoge_1")
  for i in 2:n
    array_ans = vcat(array_ans , hcat(i, sin(i), "hoge_"*string(i)))
  end
  return array_ans
end




 測定してみましょう。


julia> for i in 1:5
         @time vcat_test(100)
       end
  0.040969 seconds (7.19 k allocations: 381.453 KiB)
  0.044292 seconds (7.19 k allocations: 381.453 KiB)
  0.038721 seconds (7.19 k allocations: 381.453 KiB)
  0.037588 seconds (7.19 k allocations: 381.453 KiB)
  0.037962 seconds (7.19 k allocations: 381.453 KiB)




 次に先に、入れものを作っておく、関数の定義です。


function Substitution_test(n::Int64)
  array_ans = Array{Any}(n,3)
  for i in 1:n
    array_ans[i,:] = hcat(i, sin(i), "hoge_"*string(i))
  end
  return array_ans
end




 測定してみましょう。


julia> for i in 1:5
         @time Substitution_test(100)
       end
  0.003589 seconds (6.70 k allocations: 241.563 KiB)
  0.002266 seconds (6.70 k allocations: 241.563 KiB)
  0.001659 seconds (6.70 k allocations: 241.563 KiB)
  0.001627 seconds (6.70 k allocations: 241.563 KiB)
  0.001628 seconds (6.70 k allocations: 241.563 KiB)




 100回くらいくりかえすと、1桁の差が出てきました。


 なるべく入れものを先にした方が、仮に {Any} の型でも良いようですね。

 文字列だけ、別の Array にしたら、もっと速いよ、なんて、声が聞こえてきそうです。





















                            B!
                                





                            LINE