naoki86star

インターネットの片隅でなにかしら書いてみる

今までのプログラミングとClojureプログラミングとを比べてみる(アルゴリズム視点)

最近のCodilityのtaskをネタにして直接的にプログラミングできる形の説明で一題考えてみます。

前置きとそれにかかる説明

 ネタにするtask内容作るアルゴリズムはこんな感じ。
 整数の配列Hが与えられている。X-Y軸平面では以下のように表現できる。

f:id:naoki86star:20200225115103p:plain
例1
python風に書くなら、上の絵の例で以下の配列Hが与えられる感じ。

H=[6, 4, 7, 10, 10, 7, 3, 3, 5, 5]

 お題は、0<k<NとなるxにてX軸に平行な直線で領域を分割し、2領域それぞれで、底辺の長さはx, N-x 高さはそれぞれの領域内でのH(x)の最大値として、その値で求められる面積の和が最小になるその値を求めてくれ、ってもの。*1面積の和の出し方具体例を以下だしてみますが、求めたい答えは80

f:id:naoki86star:20200225115130p:plain
比較例
 オリジナルtaskだとNの最大値は10000に設定されていて、実際にN=10000条件下でHの形がピラミッド状とかで検算を回されている模様で、単純都度総当たり計算だと合格できない仕掛けになっています。*2

 このお題の場合には、単純に書くと計算オーダーがO(N*N*N)になってしまいそうなのを、先にkの範囲の値すべてに対する右側/左側それぞれでの最大値をあらかじめ求めておけば、O(N)に収まることできます。もっと美しいもっと優れている書き方あると思うのですが、自分が書くとこんな感じ。

    # 左側領域の最大値を求めておく
    a_maxes = [ None ] * len(H)
    a_maxes[0] = H[0]
    a_max = H[0]
    for i in range(1, len(H)):
        a_max = max(a_max, H[i])
        a_maxes[i] = a_max

    # 右側領域の最大値を求めておく
    b_maxes = [ None ] * len(H)
    b_maxes[len(H)-1] = H[-1]
    b_max = H[-1]
    for i in range(len(H)-2, -1, -1):
        b_max = max(b_max, H[i])
        b_maxes[i] = b_max

    # 全サイズの値を比較して最小値を残す
    ans = min([a_maxes[i] * (i+1) + b_maxes[i+1] * (len(H)-1-i) for i in (len(H)-1)])

 Codilityで使える言語にはC/C++/C#/Go/Java/python3/....そのほかいくらか、でもclojureは選択肢にないですね。でもclojureの話はこの時点では出さないとして、他の言語で書く場合も基本的なアウトラインというか、仮想言語的に書いた場合に同じように書けると思うのです。
 ...ちなみに、やっぱりPythonが一番書きやすい、といつも思ってしまうのです。よく使う基本アルゴリズムが簡潔によびだせて、本筋の課題を解くアルゴリズムを組み立てるのに集中できる。

本題

で、最近clojureを覚えてきたときに、まずは、clojureでどう計算するのを書く?基本的な文法・関数のところから置き換えてみてたりします。

もっと手短に書ける可能性大大だけれども、それでもいったん書いてみます。(loop, recurで何とかしてしまったのが怪しいかも)

(defn solution [H]
  (let [left-side-max ;; 右側最大値早見表
           (loop [ from (drop 1 H) to [(first H)] max-val (first H)]
             (if (first from)
                 (recur (next from)(conj to (max (first from) max-val))(max (first from) max-val))
                 to))
        right-side-max ;; 左側最大値早見表
           (loop [ from (reverse (drop-last 1 H)) to [(last H)] max-val (last H)]
             (if (first from)
                 (recur (next from)(conj to (max (first from) max-val))(max (first from) max-val))
                 (reverse to)))]

     ;; 右側面積+左側面積の和の最小になる値を残す
     (loop [ left-height (drop-last 1 left-side-max)
             right-height (drop 1 right-side-max)
             left-width 1
             right-width (dec (count right-side-max))
             ans (* (count H) (first right-side-max))]
         (if (first left-height)
             (recur (next left-height)(next right-height)(inc left-width)(dec right-width)
                    (min ans (+ (* left-width (first left-height))(* right-width (first right-height)))))
              ans)) ;; <<== return
))

いいところ

  • 変数名にハイフンが使えるのはいい

どうしたものかと思うところ

  • やっぱりぱっと見なにをしているか、他言語に比べるとみていてわからない
  • ざっとlen(H)=10000を流しただけでpythonよりはやや遅かった*3
まとまらないまとめ

 clojureでパフォーマンスを狙うのは現実的にはマルチスレッドを多用して、粒度(処理の大きさ)が一様でないような場合に、スレッドを余らせないような走らせ方がうまくいくようだと、なにかいいことが起きそうな気はしてます。
 clojureを使っていくにおいて、pythonでかどうかは別にいったん他の言語でパフォーマンスを考慮したアルゴリズム設計をして(机上設計?)それからclojureに落としていくステップでないとなかなか最後のよいゴールにはたどり着きにくい、そんな感想です。

 自分がclojureをイメージしてみるに、clojureはjavaが支えてくれている生態系上にあるものとして特徴づけられている、と表現してみます。JVMで動いているということに加えて、(積み重なった資産である)javaのライブラリが極めて容易に呼び出せる点はclojure派の人達はどのくらいの意義をもっているのか知りたいところです。clojureは、その生態系上で少なくとも言語記述形態上はjavaとまるで異なる書き方のプログラミングになります。暗に陽にobject志向言語と関数型言語のいいとこどりを意識して目的・自分の解きたい問題を解こうとするのが自然な姿になるのかどうか。例えば、簡単なhttpサーバーは確かに書きやすさを感じていて、javaのライブラリを呼び出せるスクリプト言語的な(interpriterではないと怒られるのだけど)錯覚を感じたりもします。また別の表現試みるならフットワークの軽さフットワークを何倍にも軽くすることができる秘めたる力の存在は予感します。
 あと、少なくともこんな課題ーきっちりclassを設計してプログラムを組むのが最もやりやすいような課題ーはclojureを使うまでもないとは明らかに言えると思います。一方で、関数型の小さな課題ー限りなく数学的関数に似た課題は、計算機の黎明期から作成されてきていて(例えばlapackとかをイメージしてます)、今から解きたい課題システム化したいもの置き換えたいものは今まで実現されてきたものよりももう少し大きなものであるはずです。

 個人的にたどり着いた考えとして、clojure単独で、すなわち狭い意味でlips部分だけみている限りは、そんなに他言語を凌駕するような潜在力はないのではないのかなぁ、ということです。*4だけれども、暗にclojure単独でなにかを書こうとするかにしてもjavaの土台に乗っていることを意識するし、明に他のjavaライブラリを一緒に利用しようとしてそのカバレッジの恩恵にあずかろうとする場合にスクリプト言語的な軽快感がなにか今後も使ってみてみたいと自分に思わせるのでした。
 java生態系の上で、java言語にとらわれない軽快な書き方ができる世界をclojureで初めて知ったということ、というようにまとめておきます。その気になるとこの構図ですなわちjavaの上で拡張された言語が実はいくつかあるということが意識の上のほうに上がってきて興味を持ちつつもあります。*5

*1:実際の説明で仮想ストーリーから導入されて条件も若干違うのですけど

*2:やったことないけどthreadも環境条件として使えなくしてあるんでないだろうか、純粋にアルゴリズムのプログラミングのお題だと思う

*3:当初*-side-maxの構築loopで(last H)を使ったら圧倒的に遅くなっていた、(reduce into ...)に書き直してみようとおもったのだけど(last ...)が回避できず、現状のスキルではあきらめ...

*4:他言語で書いたアルゴリズムを書き直してみるのは楽しいけど

*5:jythonとか、、以前触ろうとしてみたけども、利用するときの意識が、javaプログラムの中から便利にpythonスクリプトを呼び出そう・それだけにいっていてjava生態系を活用しようという意識がなかった。jythonの場合のjava生態系活用方法?