AtCoder ABC 100 C - *3 or /2 でJuliaを試してみる(Julia) - あるエンジニアのAtCoder奮闘記

irisruneです。久々に新しい言語に挑戦してみた回です。前置きをしておくと、今回は問題の難易度はかなり低めで言語周りの話がメインです。

なお、こちらの記事に多大な影響を受けているためこの場を借りて紹介させていただきます。

そもそもJuliaとは

簡単に書くと、Pythonなどのように対話環境があってコードが試しやすく、LLVMを用いてコンパイルを行うため実行が高速で、科学計算向けに基本機能として行列計算などをサポートしている至れり尽くせりのような言語です。

また、PythonやC++などのコードを使うためのパッケージなども存在しているため、既存のモジュールなどを活用することができます。

Juliaと競プロ

~~上記リンク先記事を見れば大体わかります。~~

まず、AtCoderでJuliaを使うことはできますがバージョンが0.5です。（2019年5月15日現在Julia公開バージョンは1.1）影響としては配列（行列）の累積計算を行うaccumulate関数が使えないことなどが挙げられます。 mathモジュールが使えないKotlinに比べれば影響は少ない…かも？

他の問題としては実行時間の計測方式の関係？で必ず数百ms以上はかかってしまったりメモリ使用量が100MB以上かかったりします。前者は意外と問題になりにくいようですが後者は64MB制限の問題で致命的ですね…

そして、標準入力で顕著ですが関数の実行の仕方によって平気で実行時間が1000ms以上変わったりします。色々試しましたがすべてのケースで実行時間の短くなる記法が見つかっていないので悩みどころですね…

また、最初のケースの実行時間が非常に不安定です。 ~~色々な記法で実行時間の比較をしようと思っていましたがこれによるものがほとんどだったので没になりました。~~

問題

atcoder.jp

問題自体はそれほど難しくはありません。アルゴリズムを考えるのも実装するのも簡単だと思います。

アルゴリズム概説

入力された数列の要素それぞれについて、2で割れる回数を数えて合計すれば答えが出ます。

なお、要素をすべて掛け合わせてから2で割れる回数を求めても答えが出るはずです…が、相当大きな値になってしまうので実装は難しく、BigInt型を使っても上手くいかなかったです。

コードと考察

とりあえず最も実行時間の短かったコードだけを挙げます。

parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=map(parseInt,x)

function main()
    n = parseInt(readline())
    a = parseMap(split(readline()))

    ans = 0
    for i in 1:n
        while mod(a[i],2) == 0
            a[i] /= 2
            ans += 1
        end
    end

    println(ans)
end

main()

f:id:amifiable:20190515160737p:plain

入力をオーソドックスに関数化し、それ以外はそのまま記述しました。関数化部分を増やしても全体の実行時間はあまり変わらず、最初のケースで時間がかかりがちだったので良い結果は出せませんでした。

ある程度わかったこととしては、

入力部分はparse関数とmap関数を関数化した方が速い。
入力以外の部分では関数化しないよりする方が早くなるとは限らない。
- 逆に、関数化によりそれほど遅くなることも（最初のケース以外では）ないので関数呼び出しのオーバーヘッドを気にする必要もなさそう。
- 最初のケースは関数を増やすと遅くなりがちだが提出の度に実行時間が変わったりしてよくわからなかった。
全てのケースにおける実行時間の幅が6ms程度のため処理速度自体はそれほど悪くはないように感じる。
- python3のfastest codeと（振れ幅が）同等というのを速いとみるか遅いとみるか。
  - 速いコードは基本的にビット演算を使っている（アルゴリズムレベルで違う）ので比較対象として不適当かもしれない。

雑記

IntelliJのJuliaプラグインを使ってみましたが、エディタ部分がやたら使いにくく感じたのでAtomプラグインも試してみたいと思います。
複数行入力をする手段があればJupyterを使ってもよいのですが…textareaを標準入力にする手段があれば知りたいですね。