UArray

同僚が Perl でのファイル処理で悩んでいました。あるデータの情報が、2 つのファイルに分かれて、順番を守って行ごとに格納されています。やりたいのは、2 つのファイルを同時に開き、どちらも最初の行から最後の行まで読みながら、データをつきあわせることです。ちなみにファイルの大きさは、それぞれ 750M と 500M です。

Perl から離れて久しい僕は、はじめの何が難しいのか分かりませんでした。しかし、よく考えてみると、2 つのファイルを同時に読み込む while の構文は存在しないことに気付きました。(嘘かもしれないので、Perl ハッカーのフォローを期待します。)

同僚には、こう言いました。「そんなの Haskell でやれば簡単だよ。ファイルは無限のリストに見える。無限リストは複数あってもいいし、map とか fold のために 1 つの無限リストにしたいなら zip すればいい。全部、遅延評価でやってくれるから楽チン。」

という訳で、本当に Haskell でやると楽なのか、コードを書いてみました。fold に指定する関数では、Array を使ってデータを処理するのがよさそうでした。

ただ、リストの走査は遅延評価したいけれど、仕事は正格評価にしないと、メモリーがいくらあっても足りなさそうです。そこで、定石通り foldl' を使い、仕事の関数はバンパターンを使って正格にしました。こんな感じです。

{-# LANGUAGE BangPatterns#-}
import Data.List
import Data.Array

work :: Array Int Integer -> [[(Int,Integer)]] -> Array Int Integer
work ai xs = foldl' acc ai xs
    where
      acc !ar !x = accum (+) ar x

完璧だと思ったのですが、走らせてみるとプロセスがどんどん太っていき、ついには死んでしまいました。

結局 Haskell の Array はダメダメなのかと諦めかけていましたが、GHC にマニュアルを読むと Unboxed Array を使えと書いてありました。そこで、以下のようにコードを書き換えました。

{-# LANGUAGE BangPatterns#-}
import Data.Int
import Data.List
import Data.Array.Unboxed

work :: UArray Int Int64 -> [[(Int,Int64)]] -> UArray Int Int64
work ai xs = foldl' acc ai xs
    where
      acc !ar !x = accum (+) ar x

Unboxed Array は、値として Integer を格納できないので、Int64 を使います。あとは、Array を UArray に変えるだけです。

これを走らせたところ、まったくプロセスは太らず、十分な早さで結果がでました。GHC のマニュアルの Unboxed のところを重点的に読んで、内部での処理がなんとなく分かりました。。。