Haskell算法建议和替代解决方案的建议

Question

我将离开下面问题的描述,但我正在编辑所有不相关的位.

1)感谢dfeuer,我已经能够完成这个项目几乎整整一秒的时间.我从10.1下降到9.2秒.

2)由于修改了SO用户应用程序发布的内容,我能够达到7.0秒,使IO非常高效.

3)感谢这里发现的不同版本的groupBy ,我现在处于6.2秒.

4)重新实现构建器输出,现在为5.8秒.

import qualified Data.ByteString.Builder    as BB  
import qualified Data.ByteString.Lazy.Char8 as DB
import qualified Data.Function              as DF

import Control.Applicative
import Data.Monoid
import System.IO

groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy rel []     = []
groupBy rel (x:xs) = (x:ys) : groupBy rel zs
    where (ys,zs) = groupByAux x xs
          groupByAux x0 (x:xs) 
              | rel x0 x = (x:ys, zs)
              where (ys,zs) = groupByAux x xs
          groupByAux y xs = ([], xs)

filterLengthBy :: (Int -> Bool) -> [[a]] -> [[a]]
filterLengthBy fn = filter (flb fn)
    where flb fn xs = fn $ length xs  

buildOutput x y =  BB.intDec x <> BB.char7 ' ' <> BB.intDec y <> BB.char7 '\n'

tensAndHundreds :: [[[Int]]] -> [BB.Builder]
tensAndHundreds [] = []
tensAndHundreds (x:xs) 
    | length x /= 10 = tens x ++ tensAndHundreds xs
    | otherwise      = buildOutput (head $ head x) 100 : tensAndHundreds xs

tens :: [[Int]] -> [BB.Builder]
tens = foldr (\x acc -> buildOutput (head x) 10 : acc) []

dbIntVals :: DB.ByteString -> [Int]
dbIntVals xs = 
    case (DB.readInt xs) of
         Just (x', xs') -> x' : dbIntVals (DB.tail xs')
         Nothing        -> if xs == DB.empty
                           then []
                           else dbIntVals (DB.tail xs)

generateResults :: [Int] -> [BB.Builder]
generateResults xs = tensAndHundreds 
                   $ groupBy ((==) `DF.on` (`quot` 100) . head) 
                   $ filterLengthBy (== 10)
                   $ groupBy ((==) `DF.on` (`quot` 10)) xs

displayResults :: [BB.Builder] -> IO ()
displayResults xs = BB.hPutBuilder stdout $ mconcat xs

main :: IO ()
main = DB.getContents >>= 
       displayResults . generateResults . dbIntVals

我在原帖子底部的两个问题是:

1. 鉴于我上面发布的方法,我有什么遗漏可以提高该计划的效率并因此提高该计划的性能吗？空间分配是最后的瓶颈吗？换句话说,groupBy方法是否正常运行？

2. 还有哪些其他方法可以解决这个问题,这个问题可以提高效率,同时仍然试图避免使用传统意义上的计数器？我还没有体验过Haskell的先进功能,但请随时提供指示.

这是最初的问题.我离开了代码的第一个版本,但删除了所有的探查器内容

我开始学习Haskell(再次)并决定尝试一些我发现的随机问题.我在Arch Linux论坛上解决的一个问题是这样的:

给定一组唯一的,上升的但不一定是连续的整数,对于从0开始的每个可能的子范围100(0-99,100-199,130​​0-1399等),如果该子范围具有所有100个元素,打印头值后跟100:

0 100
145600 100

否则,对于从0开始的相同范围内的每个连续10组(0-9,10-19,15430-15439等),打印该范围的头部,然后是10:

30 10
70 10
145620 10 
145650 10

微小测试集的示例输出如下所示:

0 10
19000 100
20320 10
54540 100

我的主要测试文件有56,653,371个整数,其中有290,197个十组和四组100个.测试机器有一个AMD 1090T处理器和8 GB RAM,并且在64位Linux上运行GHC 7.8.3.使用的唯一编译器标志是'-O2 -fflvm'.

有一点需要注意:我有意避免使用经常用于编程的计数器.例如,拥有跟踪10和100的计数器:'如果计数器一个== 100,那么......'那种东西.我想避免跟踪这些计数器的状态,只使用可用的功能/ HOF.

以下是迄今为止我最好的尝试.它在10.1秒内完成任务(目前为5.​​8秒).从透视角度来看,我提到的线程中的C版本在9.4秒内完成.还有另一个我没写过的Haskell版本使用的计数器完成了8.1秒(目前为4.7).这是我的灵感(感谢Xyne,并教导案例陈述自成一体).

**编辑**

我忘了提它它做了什么.它使用整数除法将输入数据分成十个可能的范围,并将它们放入列表列表中(编辑以澄清分裂的luqui问题).所以:

1 4 7 9                                      -> [1,4,7,9]
1 2 3 8                                      -> [1,2,3,8]
0 1 2 3 4 5 6 7 8 9                          -> [0,1,2,3,4,5,6,7,8,9]
7 8 9 10 11 12 13 14 15 16 17 18 19 20 25 27 -> [7,8,9] [10,11,12,13,14,15,16,17,18,19] [20,25,27]

filterLengthBy然后删除不长度为10的所有内容,因为我们不需要它.结果列表基于头部的整数除法被分成列表列表.所以:

[[0,1,2,3,4,5,6,7,8,9],[10,11,12,13,14,15,16,17,18,19],[100,101,102,103,104,105,106,107,108,109]]

变为:

[[[0,1,2,3,4,5,6,7,8,9],[10,11,12,13,14,15,16,17,18,19]],[[100,101,102,103,104,105,106,107,108,109]]]

如果列表的第二级长度为10,则匹配范围为100并输出到解集.否则,该列表包含范围为10的列表,应单独添加到解决方案集中.

旧版本的代码

import qualified Data.ByteString.Lazy.Char8  as DB
import qualified Data.Function               as DF
import qualified Data.List                   as DL
import Control.Applicative

groupByEqOn :: Eq b => (a -> b) -> [a] -> [[a]]
groupByEqOn fn = DL.groupBy ((==) `DF.on` fn)

filterLengthBy :: (Int -> Bool) -> [[a]] -> [[a]]
filterLengthBy fn = filter (flb fn)
    where flb fn xs = fn $ length xs   

tensAndHundreds :: [[[Int]]] -> [(Int, Int)]
tensAndHundreds [] = []
tensAndHundreds (x:xs) 
    | length x /= 10 = tens x ++ tensAndHundreds xs
    | otherwise      = (head $ head x, 100) : tensAndHundreds xs

tens :: [[Int]] -> [(Int, Int)]
tens = map (\x -> (head x, 10))

dbEmpty :: DB.ByteString
dbEmpty = DB.empty

dbIntVals :: [DB.ByteString] -> [Int]
dbIntVals [] = []
dbIntVals (x:xs) =
    case (DB.readInt x) of
         (Just (x', dbEmpty)) -> x' : dbIntVals xs
         _                    -> error "*** Error: Non-integer input ***"

generateResults :: [Int] -> [(Int, Int)]
generateResults xs = tensAndHundreds 
                   $ groupByEqOn ((`quot` 100) . head) 
                   $ filterLengthBy (== 10) 
                   $ groupByEqOn (`quot` 10) xs

displayResults :: [(Int, Int)] -> IO ()
displayResults = mapM_ (\(a, b) -> putStrLn (show a ++ " " ++ show b)) 

main :: IO ()
main = dbIntVals <$> DB.lines <$> DB.getContents >>= 
       displayResults . generateResults

对于我来说,分析器中唯一令我惊讶的两件事就是filterLengthBy的速度.所有参与过滤器的人都非常荣幸.考虑到我投入了多少数据,这真是一件了不起的事.就此而言,我所写的内容和它一样快.另一个惊喜是dbIntVals的速度有多慢.我确实实现了正确的错误检查,这让事情变得有点慢,但我仍然感到惊讶.除此之外,它似乎与我的代码完全一样.

Answer 1

我已经完成了这个线程。我来这里是为了了解 SO Haskell 社区提供的内容，并得到了一些有用的回复。为此我很感激。

我发布的最新版本的代码表明，只要有好的代码，GHC 就可以仅使用函数式习惯用法生成速度极快、准确的程序。这看起来似乎很明显，但这是我从头开始编写的第一个 Haskell 程序（带有明显的 groupBy 复制和粘贴）。

我学到了什么？

dfeuer 提醒我要小心，仅依赖像地图这样的内置函数不一定是最好的方法。有时结合逻辑很有帮助。在这种情况下，我的性能得到了非常显着的提升。

从应用中我学到了高效输出。性能的提升是惊人的。

如果不知何故有任何 Haskell/GHC 开发人员正在阅读此内容：

在我看来，这里的groupBy应该包含在标准库中，而不是推到Hackage中。为什么？它速度快，同时保持准确性。对于数百万个元素的完全相同的操作并产生完全相同的结果，性能提高了约 8.2%。我知道它做的事情并不完全相同；我觉得还是值得一看的。

这实际上有意义吗？我发现与上述相同的数据集相比，性能至少提高了 10%，且准确度为 100%。我知道“rem”和“mod”做不同的事情，并且它们倾向于朝不同的“方向”舍入，但前者的表现远远超过后者。我可能不明白这个范围，但 10% 是很难忽视的。