読者です 読者をやめる 読者になる 読者になる

真面目なノート

こまめにその日の進捗などをメモしておく。

おウチはいいところ

Haskell 競技プログラミング Python 型システム アルゴリズム

ここ数日のまとめ

プログラミング

AOJで競技プログラミングの練習

Longest Increasing Subsequence | Aizu Online Judge

こいつを解いた。

最長増加部分列という問題である。 [5, 1, 3, 2, 4]というような数列の中から、[1, 2, 4]のような、元の数列から前後関係を崩さずに取り出せる単調増加な数列を探しだす。

解法としては、簡単に言うと、[5] の最長増加部分列、[5, 1]の最長部分増加列、[5, 1, 3]の最長増加部分列、というように、要素を一つずつ増やしていき、最長増加部分列を更新していく。更新方法は以下のとおり。

  • 追加した要素 a の値が、最長増加部分列の最大値(すなわち最後の要素)より大きい場合
    • 最長増加部分列を伸長。最長増加部分列の右端に要素 a を追加する
  • それ以外
    • 最長増加部分列の中で、要素 a よりも大きい要素の内、最小である要素 b を a と入れ替える。

数列の要素がNとし、最長部分増加列の更新に要する計算量をO(M)とすると、全体の計算量はO(NM)になる。更新の際に最長増加部分列の全探索を行うと計算量がO(N2)になってしまうため、ここが多少工夫を要する部分である。最長増加部分列はソート済みの数列であるため、ここは二分探索を用いることで、計算量をO(N logN)にする。

Pythonによるコードは以下のとおり。二分探索については標準ライブラリにbisectモジュールがあるので、それを用いた。

import bisect

N = int(input())
numbers = []
for i in range(N):
    numbers.append(int(input()))

lis = [numbers[0]]
for last in numbers[1:]:
    if lis[-1] < last:
        lis.append(last)
    else:
        pos = bisect.bisect_left(lis, last)
        lis[pos] = last

print(len(lis))

この問題は、(僕の感じでは)今までの動的計画法ほどmutableな感じがしない。どうも末尾再帰にしてもなんにしても、Haskellで書けるんじゃないかな、という気がしたので、ちょっと他の人の解答を見てみた。

AIZU ONLINE JUDGE: Code Review

{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
module Main (main) where
import Control.Applicative
import Control.Monad
import qualified Data.ByteString as BS
import Data.ByteString.Char8 (readInt)
import qualified Data.IntSet as IS
import Data.Maybe (fromJust)
import qualified Data.Vector.Unboxed as VU
 
main :: IO ()
main = do
  n <- readLn
  as <- VU.replicateM n $ fst . fromJust . readInt <$> BS.getLine
  print $ solve as
 
solve :: VU.Vector Int -> Int
solve as = IS.size $ VU.foldl' f IS.empty as
  where
    f s e = case IS.lookupGE e s of
      Just ix | e < ix     -> IS.insert e $ IS.delete ix s
              | otherwise -> s
      Nothing -> IS.insert e s

よくわからないモジュールが幾つか出てきた。というか、正直言うとだいたい全部わからないので、一個ずつ見ていく。

ByteString

文字列に関する正格評価、高速処理などを提供してくれるモジュール。詳しくは下記のサイト。全体の速度向上のために用いていると思う。

www.geocities.jp

使用している関数で気になったreadIntについてはこんな感じ。

readInt :: ByteString -> Maybe (Int, ByteString)

返り値のタプルのsndは未評価のByteStringである。

Data.IntSet

Data.IntSet

Hackage見たほうが良い気がする。

An efficient implementation of integer sets.

とのこと。

size :: IntSet -> Int
-- O(n). Cardinality of the set.
empty :: IntSet
-- O(1). The empty set.
lookupGE :: Key -> IntSet -> Maybe Key
-- O(log n). Find smallest element greater or equal to the given one.
insert :: Key -> IntSet -> IntSet
-- O(min(n,W)). Add a value to the set. There is no left- or right bias for IntSets.
delete :: Key -> IntSet -> IntSet
-- O(min(n,W)). Delete a value in the set. Returns the original set when the value was not present.

このモジュール、要するに整数の集合(つまりリストではない)を利用するためのモジュールらしい。計算量もかなり小さい。そして、恐ろしいことに非常に充実したモジュールであり、様々な問題に応用できそう。この問題においてはlookupGEがO(log n)であるから、必要十分な速度が出せているということらしい。

ちなみに、そもそもこのモジュールがどういう風に実装されてるのかという話については、以下の様なことが書いてあった。今度暇な時にもう少し調べてみよう。

The implementation is based on big-endian patricia trees. This data structure performs especially well on binary operations like union and intersection. However, my benchmarks show that it is also (much) faster on insertions and deletions when compared to a generic size-balanced set implementation (see Data.Set).

Data.Vector.Unboxed

unboxされたVector。これも、メモリ使用量を抑えるためにunboxを使っているのだろう。

foldl' :: Unbox b => (a -> b -> a) -> a -> Vector b -> a
-- O(n) Left fold with strict accumulator
replicateM :: (Monad m, Unbox a) => Int -> m a -> m (Vector a)
-- O(n) Execute the monadic action the given number of times and store the results in a vector.

foldl' が正格(strict)なので、スタックオーバーフローなどの問題もおこらない。ナルホド。
競技プログラミングHaskellによる解答を見ていくのが結構勉強になりそうなので、しばらく続けると良さそうだ。

48時間でSchemeを書こう

評価:第二部

48時間でSchemeを書こう/評価: 第二部 - Wikibooks

条件分岐等の機能を追加していく。異型リストなるものを導入するために、存在型の拡張機能を用いた。存在型に関してはこのチュートリアルでは詳しくは触れていないので、今後も出てくるかも、程度に覚えておくと良さそう。

REPLの作成

48時間でSchemeを書こう/REPLの作成 - Wikibooks

一行だけ命令を受け取ってそれに対して評価を返す。とりあえず評価関数を簡単なIOに変更するだけ。この次あたりから非常にしんどくなってくる。

変数と代入

48時間でSchemeを書こう/変数と代入 - Wikibooks

かなり厳しい。Haskellにおいてミュータブルな値をどのように使っていくのか、という部分に関わる。基本的には、以下の様な方法がとられる。

  • Stateモナド
    • インタプリタという複雑なデータ型を保持する環境では、スタックがオーバーフローしrunStateが破壊されうるので、ダメ。
  • Stateスレッド
    • 集合状態をHaskellに管理させる。
    • STモナド
    • IORef

今回はIORefを使う。結果として、今まで書いてきた主要な部分を、再びIORefモナドに合わせて書き換える必要が生じる。つらい。

Scheme関数の定義

48時間でSchemeを書こう/Scheme関数の定義 - Wikibooks

最早何をしているのかわからなくなってきた。前章でDefineなどを定義したのと同様にしてPrimitiveFuncとFuncを定義する。

Funcのapplyに関しては、引数、パラメータ、クロージャなどをバインドバインドし、評価していく……かなり理解が追いついていないが、とにかく最後までやりきっていきたい。

プログラミング言語と型の理論

第3章 型なし算術式

数とブール値からなる単純で小さな言語の構文を見ていくことで、以下の様な基本概念についての理解をする。

  • 抽象構文
  • 帰納的定義・証明
  • 評価
  • 実行時エラーのモデル化

まず構文を定式化していく。以下の様な方法で行う。

  • 帰納的な項定義
  • 推論規則による項定義

基本的にはこの二つは同一である。これらを以降Τと呼ぶ。ここに、このような論理的規則ではなく、もう少し具体的な項の定義Sを与える。これらのΤとSについて、以下の様な点に留意する。

  • Τ : 構文を定義する項の最小集合
  • S : より具体的に定義された項の集合(であるが、最小かどうかは自明でない)

よって、T=Sであることを証明する。これにより、TがSによって、より具体的な形で定義されたことになる。この定義は以下のことに活用される。

  • 関数の帰納的定義
    • consts(t) : tに現れる定数の集合
    • size(t) : tのサイズ。すなわち抽象構文木のノード数
    • depth(t) : 構文木の深さ
  • 項の性質の帰納的証明
    • 上のような帰納的定義から、他の性質を新たに証明する

更に、これまでで構文の定式化を行ったので、ここから項の評価法を定義していく。この評価法のことを、意味論という。

  • 操作的意味論
    • 抽象機械を定義する
      • 状態 : 項
      • 振る舞い : 遷移関数
    • この時、項tはtを初期状態として動き始めた抽象機械の最終状態を指す
  • 表示的意味論
    • 項の意味は数学的対象とされる
    • 意味領域に対して項を写す解釈関数を定義する
      • 領域理論に基づく
  • 公理的意味論
    • 言語の定義を言語の法則そのものから構築する
      • 不変条件の発見などにつながった

以降、評価関係や推論規則に関する定理・定義等を証明していく。

  • 項が正規形であるとは、t→t' となるtが存在しないことをいう
  • 全ての値は正規形である
  • 正規形だが値でないとき、これは行き詰まり状態であり、実行時エラーとなる。

実行時エラーをwrong項として持つ言語は、元の言語と同等のものであることの証明が個人的に面白い気がした。

研究

論文

スマートフォンによる動作センシング関係の論文をいくつか読んだ。どうも流れとしては、回数カウントやスキルアセスメント系は結構あるようだ……そこら辺、何が既にされていて、何がされていないのかというところを先生と話し合って色々決めないといけない。

データを取った

なんにせよ、とりあえずスマホでどういうデータがとれるかわかっていないとしょうがないので、市営ジムでデータを取ってきた。慣性センサによる回数のカウントと種目の識別は割とイケそうな気がした。後は、金属が当たる時の高周波音は取れたが、これは、まあ、どうだろうか、という感じだ。