4

数値のリストの反転をカウントしようとしています。次のFregeプログラムは、少数の数値セットに対して機能しますが、100000の数値に対してStackOverflowErrorをスローします。

import frege.IO

inversionCount [] _ = (0, [])
inversionCount [x] _ = (0, [x])
inversionCount xs n = (count, sorted) where
  count = lcount + rcount + mergecount
  (lcount, lsorted) = inversionCount left lsize
  (rcount, rsorted) = inversionCount right rsize
  (mergecount, sorted) = inversionMergeCount lsorted lsize rsorted rsize (0, [])
  (left, right) = splitAt mid xs
  mid = n `quot` 2
  lsize = mid
  rsize = n - mid

inversionMergeCount xs _ [] _ (acc,sorted) = (acc, reverse sorted ++ xs)
inversionMergeCount [] _ ys _ (acc,sorted) = (acc, reverse sorted ++ ys)
inversionMergeCount (xs@(x:restx)) m (ys@(y:resty)) n (acc, sorted)
  | x < y = inversionMergeCount restx (m - 1) ys n (acc, x:sorted)
  | x > y = inversionMergeCount xs m resty (n - 1) (acc + m, y:sorted)
  | otherwise = inversionMergeCount restx (m - 1) resty (n - 1) (acc, x:y:sorted)

main (fileName:_) = do
  input <- readFile fileName
  let xs = map atoi (lines input)
  println . fst $ inversionCount xs 100000

--Haskell's readFile using Java's Scanner
type JScanner = JScannerT RealWorld

data JScannerT s = native java.util.Scanner where
  native new :: File -> ST s (Exception JScanner)
  native useDelimiter :: JScanner -> String -> ST s JScanner
  native next :: JScanner -> ST s String

readFile f = do
  file <- File.new f
  exceptionScanner <- JScanner.new file
  let scanner = either throw id exceptionScanner
  scanner.useDelimiter "\\Z"
  scanner.next

Haskellの同じコードは正常に機能します：

import System.Environment

inversionCount [] _ = (0, [])
inversionCount [x] _ = (0, [x])
inversionCount xs n = (count, sorted) where
  count = lcount + rcount + mergecount
  (lcount, lsorted) = inversionCount left lsize
  (rcount, rsorted) = inversionCount right rsize
  (mergecount, sorted) = inversionMergeCount lsorted lsize rsorted rsize (0, [])
  (left, right) = splitAt mid xs
  mid = n `quot` 2
  lsize = mid
  rsize = n - mid

inversionMergeCount xs _ [] _ (acc,sorted) = (acc, reverse sorted ++ xs)
inversionMergeCount [] _ ys _ (acc,sorted) = (acc, reverse sorted ++ ys)
inversionMergeCount (xs@(x:restx)) m (ys@(y:resty)) n (acc, sorted)
  | x < y = inversionMergeCount restx (m - 1) ys n (acc, x:sorted)
  | x > y = inversionMergeCount xs m resty (n - 1) (acc + m, y:sorted)
  | otherwise = inversionMergeCount restx (m - 1) resty (n - 1) (acc, x:y:sorted)


main = do
  (fileName: _) <- getArgs
  contents <- readFile fileName
  let xs :: [Int]
      xs = map read (lines contents)
  print . fst $ inversionCount xs 100000

スタックオーバーフローの原因は何でしょうか？末尾再帰ではない関数はありますか？

4

2 に答える 2

5

Haskellの方が厳密性アナライザーが優れているか、末尾再帰が別の方法で実装されているか、ランタイムで使用可能なスタックが多い可能性があります。

私が最初に試みることは、-Xss8m、さらには16mを設定することです。

それでも問題が解決しない場合は、（-）、（+）などの厳密な関数のアプリケーションで更新されるレイジー引数がサンクを構築し、後で一度に評価する必要があることに注意してください。これは、の場合と同じ問題でfoldlあり、inversionMergeCountとinversionCountの2番目の引数がこれに苦しんでいるように見えます。

Fregeコンパイラは、これを検出した場合、これについて警告する必要がありますが、現時点では警告していません。

もう1つのポイントは、なぜ最後の2つの引数をタプルで渡すのですか？accを厳密にすることもできます。

于 2013-02-19T23:23:42.890 に答える
3

Ingoの提案に従って、私は変更を加え、コードは現在機能しています。また、intオーバーフローを回避するInteger代わりに、としてカウントする必要がありました。Int厳密な注釈とInteger変換を含む更新されたコードは次のとおりです。

inversionCount [] _ = (zero, [])
inversionCount [x] _ = (zero, [x])
inversionCount xs n = (count, sorted) where
  count = lcount + rcount + mergecount
  (lcount, lsorted) = inversionCount left lsize
  (rcount, rsorted) = inversionCount right rsize
  (mergecount, sorted) = inversionMergeCount lsorted lsize rsorted rsize zero []
  (left, right) = splitAt mid xs
  mid = n `quot` 2
  lsize = mid
  rsize = n - mid


inversionMergeCount xs _ [] _ !acc sorted = (acc, reverse sorted ++ xs)
inversionMergeCount [] _ ys _ !acc sorted = (acc, reverse sorted ++ ys)
inversionMergeCount (xs@(x:restx)) !m (ys@(y:resty)) n !acc sorted
  | x < y = inversionMergeCount restx (pred m) ys n acc (x:sorted)
  | x > y = inversionMergeCount xs m resty (pred n) (acc + m.big) (y:sorted)
  | otherwise = inversionMergeCount restx (pred m) resty (pred n) acc (x:y:sorted)
于 2013-02-20T06:51:04.540 に答える