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

我将在下面保留对问题的描述，但是我正在去掉所有不相关的部分。

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论坛上得出的一个问题是：

给定一组唯一的，升序的（但不一定是连续的整数），如果该子范围具有所有100个元素，则从0开始的每个潜在子范围100（从0-99、100-199、1300-1399等） ，然后打印head值，后跟100：

0 100
145600 100

否则，对于从0（0-9、10-19、15430-15439等）开始的相同范围内的每10个连续集，请打印该范围的开头，然后打印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的计数器：“如果计数器1 == 100，则...”之类的东西。我想避免跟踪这些计数器的状态，而只使用可用的功能/ HOF。

到目前为止，这是我最好的尝试。它将在10.1秒（当前为5.8秒）内完成任务。从一个角度来看，我之前提到的线程的C版本在9.4秒内完成。我没有写过另一个Haskell版本，它使用计数器完成了8.1秒（当前为4.7秒）。这就是我的灵感（感谢Xyne并教案例陈述应运而生）。

**编辑**

我忘了提到它的作用了。它使用整数除法将输入数据分割为十个可能的范围，并将它们放入列表列表中（已编辑以阐明所询问的分割量）。所以：

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有多慢。我确实实现了正确的错误检查，这使事情变慢了一些，但是我仍然感到惊讶。除此之外，它看起来和我的代码完全一样。