Python の爆速 "in set" に julia で挑む

@kitadakyou さんの Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由 というブログのコードを julia の Array で挑んだらどうなるかを試してみました。

まず、自分の python3 で、"in set" 実行した時の時間です。 

>>> for _ in range(10):  # 今回は実験のため、10回実行
...     result = 0
...     start_time = time.time()
...     for _ in range(100000):
...         num = randint(1, 10000000)  # 改めて1 ~ 10000000 の間の数値をランダムに 100000 個選び、集合中にあれば result を + 1 する
...         if num in a:  # 要素が集合中に存在するかチェック
...             result += 1
...     # print(result)
...     print("elapsed_time:{time} sec".format(time=time.time() - start_time))
... 

elapsed_time:0.17500686645507812 sec
elapsed_time:0.17588305473327637 sec
elapsed_time:0.17502999305725098 sec
elapsed_time:0.1756739616394043 sec
elapsed_time:0.17586398124694824 sec
elapsed_time:0.17543387413024902 sec
elapsed_time:0.1754751205444336 sec
elapsed_time:0.17451786994934082 sec
elapsed_time:0.1747879981994629 sec

上記がベンチマークです。

では、julia に移植、といっても set() はないので、Array() で書きます。 


julia> A = rand(1:10^5,10^5);

julia> for i in 1:10
         result = 0
         @time for i in 1:10^5
           if rand(1:10^7) in A
             result +=1
           end
         end
         print(result)
       end
  4.826036 seconds (100.00 k allocations: 1.526 MiB)
644  6.101467 seconds (99.99 k allocations: 1.526 MiB)
633  5.478746 seconds (99.99 k allocations: 1.526 MiB)
598  6.400460 seconds (99.99 k allocations: 1.526 MiB)
672  5.073428 seconds (100.00 k allocations: 1.526 MiB)
617  5.145575 seconds (100.00 k allocations: 1.526 MiB)
609  5.333662 seconds (100.00 k allocations: 1.526 MiB)
649  5.370491 seconds (100.00 k allocations: 1.526 MiB)
623  5.060122 seconds (99.99 k allocations: 1.526 MiB)
650  5.429527 seconds (100.00 k allocations: 1.526 MiB)
644

ちょっと悲しいですが、python に10倍以上の差で負けています。

単純に関数化しても期待したよりも遥かに小さな変化です。 


julia> function compair_a()
         result = 0
         for i in 1:10^5
           if rand(1:10^7) in A
             result +=1
           end
         end
         print(result)
       end
compair_a (generic function with 1 method)

julia> for i in 1:10
         @time compair_a()
       end
588  5.119351 seconds (100.00 k allocations: 1.526 MiB)
674  4.885485 seconds (100.00 k allocations: 1.526 MiB)
653  5.554557 seconds (100.00 k allocations: 1.526 MiB)
612  4.990193 seconds (100.00 k allocations: 1.526 MiB)
658  5.416396 seconds (100.00 k allocations: 1.526 MiB)
643  5.082678 seconds (100.00 k allocations: 1.526 MiB)
687  4.965522 seconds (100.00 k allocations: 1.526 MiB)
626  4.842607 seconds (99.99 k allocations: 1.526 MiB)
635  4.879983 seconds (100.00 k allocations: 1.526 MiB)
627  5.068559 seconds (100.00 k allocations: 1.526 MiB)

なら、map() を使ってみよう。 

julia> function conpair_a1()
         A1 = rand(1:10^7, 10^5)
         B1 = map(x -> x in A, A1)
         print(sum(B1))
       end
conpair_a1 (generic function with 1 method)

julia> for i in 1:10
         @time conpair_a1()
       end
616  4.849527 seconds (126.83 k allocations: 3.727 MiB)
629  4.948732 seconds (100.00 k allocations: 2.384 MiB)
602  4.862076 seconds (100.01 k allocations: 2.384 MiB)
640  4.906242 seconds (100.00 k allocations: 2.384 MiB)
645  4.859775 seconds (100.01 k allocations: 2.384 MiB)
673  4.951097 seconds (100.00 k allocations: 2.384 MiB)
639  4.855138 seconds (100.00 k allocations: 2.384 MiB)
641  4.932278 seconds (100.00 k allocations: 2.384 MiB, 0.08% gc time)
649  4.852540 seconds (100.00 k allocations: 2.384 MiB)
637  4.958297 seconds (100.01 k allocations: 2.385 MiB)

メチャクチャ悔しいので、ともかく答えだけ早く出す方法に変更です。 

julia> function intersect_a1()
         A1 = rand(1:10^7, 10^5)
         print(length(intersect(A1, A)))
       end
intersect_a1 (generic function with 1 method)

julia> for i in 1:10
         @time intersect_a1()
       end
648  0.020620 seconds (41 allocations: 5.281 MiB)
636  0.025924 seconds (41 allocations: 5.281 MiB, 17.71% gc time)
645  0.014462 seconds (41 allocations: 5.281 MiB)
631  0.017685 seconds (41 allocations: 5.281 MiB)
637  0.020631 seconds (41 allocations: 5.281 MiB)
683  0.020915 seconds (41 allocations: 5.281 MiB)
622  0.024897 seconds (41 allocations: 5.281 MiB, 29.49% gc time)
656  0.017534 seconds (42 allocations: 5.281 MiB)
643  0.021651 seconds (41 allocations: 5.281 MiB)
695  0.024542 seconds (41 allocations: 5.281 MiB)

これなら楽勝ですが、根本的に行っている演算が異るので、ちょっと微妙な感じです。

普通に書くなら julia は for ループは python に比較して安定した速度が出るといわれています。最適化したコードなら python は苦手とされる for ループでもかなり早いですね。

B! LINE