Elixir Enum.zip VS 再帰関数 速度競争

はじめに

Enum.zipを使ったコードが予想以上に遅かったことがあり、他の実装方法と比較してみます。

次の記事で作った、ABC242Cで比較してみます。

対策前

    def add_list_with_shift(l) do
        #   リストlの要素を以下のようにシフトして加算したリストを返す。
        # ret[i] = l[i-1] + l[i] + l[i+1]
        shift_left1 = Enum.drop(l++[0], 1)
        shift_right1 = Enum.take(l, length(l) - 1)
        shift_right1 = [0 | shift_right1]
        Enum.zip([shift_left1, l, shift_right1]) |> Enum.map(fn {x, y, z} -> rem(x + y + z, @mod) end)
    end

実行時間は、AtCoderのジャッジで1746msでした

再帰関数で実装

Enum.zipを再帰関数で実装してみます

    def add_list_with_shift(l) do
        #   リストlの要素を以下のようにシフトして加算したリストを返す。
        # ret[i] = l[i-1] + l[i] + l[i+1]
        shift_left1 = Enum.drop(l++[0], 1)
        shift_right1 = Enum.take(l, length(l) - 1)
        shift_right1 = [0 | shift_right1]
        zip_sum(shift_left1, l, shift_right1)
    end

    def zip_sum([a],[b],[c]), do: [rem(a+b+c, @mod)]
    def zip_sum([a|a_list],[b|b_list],[c|c_list]), do: [rem(a+b+c, @mod)| zip_sum(a_list,b_list,c_list)]

実行時間は、AtCoderのジャッジで1543msでした

200ms速くなりました。

AtCoderでは、200ms足りなくてTLEになるとかはあまりないと思いますが、Elixirの場合、適切なアルゴリズムでも、あと一歩間に合わない場合があるので、そんな時は役立つかもしれません。