空间分离整数输入向量的Haskell快速构造

toe95027  于 2022-12-27  发布在  其他
关注(0)|答案(1)|浏览(122)

如果我期望从用户输入中得到一个用空格分隔的int字符串(已知期望的int的个数),我可以在haskell Data.Vector中传输它,如下所示:

main = do
        n <- readLn -- this is number of ints        
        l' <- getLine
        let a = (read :: String -> Int) <$> words l' 
        return $ V.fromList a

但是我想尽可能快地完成,不使用中间列表,在这种情况下构造Vector的最快方法是什么?
ps.我正在考虑循环getChar + replicateM,但不是shure它会不会更快。

hi3rlvi2

hi3rlvi21#

接下来的应该很快。

{-# LANGUAGE BangPatterns #-}

import Data.Char
import qualified Data.Vector.Unboxed as V
import qualified Data.ByteString.Lazy as BL

numbers :: Int -> BL.ByteString -> V.Vector Int
numbers n = V.unfoldrExactN n $ go 0
  where go !acc bs = case BL.uncons bs of
          Just (c, bs') | c' >= zero && c' <= nine -> go (acc*10+c'-zero) bs'
                        | otherwise -> (acc, bs')
            where c' = fromIntegral c
                  zero = ord '0'
                  nine = ord '9'
          Nothing -> (acc, BL.empty)

main = do
  n <- readLn
  inp <- BL.getContents
  print $ V.sum (numbers n inp)

注意,这个版本没有输入验证,它只解析由单个非数字分隔符分隔的数字串,并且它会将重复的分隔符误读为额外的零值。
在我的机器上用GHC 8.10.4编译,它每秒处理大约5G字节,比类似的GCC编译的C版本性能高出大约10%,这有点可疑,但我没有看到我的C版本有什么明显的错误:

#include <stdio.h>

long v[100000000];

int
main()
{
        long n;
        scanf("%ld\n", &n);
        for (int i = 0; i < n; ++i) {
                long acc = 0;
                int c;
                while ((c=getchar())>='0')
                        acc = acc*10+c-'0';
                v[i] = acc;
        }
        long total = 0;
        for (int i = 0; i < n; ++i) {
                total += v[i];
        }
        printf("%ld\n",total);
        return 0;
}

相关问题