11

Haskell でフィルターを実装しています。つまり、次のようにコマンドラインから呼び出すことができるプログラムです。

$ cat inputfile.txt | myFilter > outputfile.txt

約 80 MB のファイルに対してプログラムを実行すると、スタック オーバーフローが発生します (スタック スペース オーバーフロー: 現在のサイズ 8388608 バイト)。cygwin で GHC バージョン 6.12.3 を使用しています。

プログラムで使用している関数に問題があると思いますがsort、3日間探しても解決方法がわからないので、どなたかヒントをいただければと思います。

これが私のプログラムに関する重要な詳細です。

私のフィルタ プログラムは、標準入力を文字列に読み取り、それを複数の行に分割し、各行を何らかのタイプのレコードに解析しますEvent

data Event = ...

これはのインスタンスですOrd

instance Ord Event where
    x < y = ...

組み込みsort関数を使用してイベントをソートできるようにします。

行への分割とイベントの解析 (行ごとに 1 つのイベント) は、関数によって実行されます。

p :: String -> [Event]

これは内部的に標準関数を使用しますlines。

イベントをグループ化する関数 g もあります。

g :: [Event] -> [[Event]]

g は、ここでは関係のない基準をいくつか使用しています。各グループには最大 4 つのイベントを含めることができます。

を使用して (リストとして表される) イベントの各グループを並べ替えsort(つまり、各グループ内のすべてのイベントが並べ替えられます)、最後に関数を使用してすべてのイベント グループを文字列としてフォーマットします。

f :: [[Event]] -> String

メイン関数は次のようになります。

main = interact (f . (map sort) . g . p)

前述のように、約 80 MB のファイルに対してこのプログラムを実行すると、スタック オーバーフローが発生します。

並べ替え関数を次の関数に置き換えると（単純なクイック並べ替えの実装）：

mySort :: [Event] -> [Event]
mySort [] = []
mySort (e:es) = let h = [j | j <- es, j < e]
                    t = [j | j <- es, e < j]
                in
                  (mySort h) ++ [e] ++ (mySort t)


main = interact (f . (map mySort) . g . p)

スタックオーバーフローはありません！

関数の場合、の定義を次のようmySortに置き換えます。t

                    t = [j | j <- es, e <= j]

<つまり、に置き換え<=ます。スタック オーバーフローが再び発生します。

だから私はここで何が起こっているのか分かりません。無限再帰を導入したことがわかりません。私のもう 1 つの仮説は、遅延評価がここで役割を果たすことができるというものです ( ?<=よりも大きなサンクを生成し<ますか?)。

私は Haskell の経験はありますが、本当の専門家ではないので、過去 3 日間、これを理解するのに苦労していたので、役立つヒントを得ることができてうれしく思います。

4

2 に答える 2

23

犯人は

instance Ord Event where
    x < y = ...

Ordこれはインスタンスを定義する間違った方法です。Ordインスタンスの最小限の完全な定義は、compareまたは のいずれかを定義します(<=)。compareに関して(<=)、および に関してすべてのOrdメンバー関数の既定の定義がありますcompare。したがって、 を定義する(<)と、それが使用できる唯一のOrdメンバーであり、他のすべてのメンバーは呼び出されると無限にループcompareし(<=)ますcompare。

このData.List.sort関数はcompare順序を決定するために を使用するため、最初の比較でループします。カスタムクイックソートは のみを使用する(<)ため、機能します。

于 2012-08-30T19:22:12.097 に答える
1

コードのプロファイルを作成してすぐに結果を得る前に、スタックサイズを増やしてみてください。

RTSを有効にしてプログラムをコンパイルし、必要なスタックサイズを指定します。

http://book.realworldhaskell.org/read/profiling-and-optimization.html

于 2012-08-30T18:45:15.543 に答える