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

Question

我将在下面留下对问题的描述，但我正在编辑所有不相关的部分。

1) 多亏了 dfeuer，我已经能够从这个程序中减少几乎一整秒的时间。我从 10.1 降到了 9.2 秒。

2) 由于修改了 SO 用户 applicative posted ，我能够缩短到 7.0 秒，从而使 IO 变得非常高效。

3)多亏了不同版本的 groupBy 发现 here ，我现在是 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

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

鉴于我在上面发布的方法，有没有我遗漏的地方可以提高该程序的效率并因此提高该程序的性能？空间分配是最终的瓶颈吗？换句话说，groupBy 方法是否运行正常？

我可以通过哪些其他方式来看待这个问题，以提高效率，同时仍然试图避免传统意义上的计数器？我对 Haskell 的高级功能还没有经验，但请随时提供指点。

这是原来的问题。我留下了代码的第一个版本，但删除了所有分析器的东西

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

给定一组唯一的、升序但不一定是连续的整数，对于从 0(0-99、100-199、1300-1399 等)开始的 100 的每个潜在子范围，如果该子范围具有所有 100 个元素, 打印 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个int，其中10个有290197组，100个有4组。测试机有AMD 1090T处理器和8GB内存，在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 和教学案例陈述进入他们自己的地方)。

** 编辑 **

我忘了提及它的作用。它使用整数除法将输入数据拆分为 10 个潜在范围，并将它们放入一个列表列表中(编辑以澄清 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 那里我被提醒要小心那些只依赖像 map 这样的内置函数不一定是最好的方法。有时结合逻辑是有帮助的。在这种情况下，我获得了非常显着的性能提升。

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

如果有任何 Haskell/GHC 开发人员正在阅读此内容:

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

是否this真的有意义吗？我看到在 100% 准确率的情况下，与上述相同的数据集相比，性能至少提高了 10%。我知道 'rem' 和 'mod' 做不同的事情，并且它们倾向于向不同的“方向”四舍五入，但前者的性能远远超过后者。我可能不理解这个范围，但 10% 是很难忽视的。