实战 最长状态

Table of Content:
  1. 题目
  2. 实战
    1. 副作用
    2. 函数式
      1. 评论
    3. 性能问题
    4. 兼容性

从去年开始,陆续学习了一点Haskell的东西,当时在codewars上面着实写了一些练习题,还有H99之类的.

最近又开始回头看SICP,然后看到racket,接触到CSE341的课程,这个过程中自己也有和Haskell进行比较.

比较的结果,就是Haskell还是有着自己的独特之处的,值得再继续学习下去.

学习要结合着练习,毕竟学的都是死的,真的能够在日常生活中使用起来,才能够保持对相关知识的活力.

所以就有了今天这个实战的小code.

题目

要完成的功能其实非常简单.

日志处理
日志按行分布,部分行中带有BufferS的信息.
这些行的Log中,有的带有status信息.具体的的status,则是从status到该行的最后.
找到停留在该status最长的状态,并且输出对应的停留的行数.
注意:带有BufferS的行并不一定是连续的.

这个要求其实比较简单,就是求出该日志中停留在什么状态最长.

其中可能涉及到的方法有:

参数解析
文件读取,和标准输出
文本处理

其他东西,则涉及到Haskell具体的一些东西了,后面再说.

实战

本文涉及到的Haskell的特点

副作用

很多资料都介绍说Haskell是一个没有副作用的语言.这其实是不可能的,如果完全没有副作用,那么其实就等于不能够运行一样.

盗图一张啊 :)

Haskell

但是Haskell的副作用限制比较大,至少要符合其对应的类型系统中去.这样的结果就是副作用比较集中,从而不会散布在代码的各个地方.

例如:

1
2
3
4
main = do
        args  <- getArgs
        s <- C.readFile $ head args
        print $ process s

所用的带副作用的代码,都在main函数的控制中.而这里代用副作用的函数其实就三个getArgs获得参数,readFile,以及print打印.比如我想把打印直接放在process的函数里面,这个时候就会有问题,因为process的类型就必须是IO类型的.这和一般的代码结构是矛盾的.

函数式

在上面的代码片段中,以及可以获取参数,读取文件,标准输出都包含了.下面就集中在文本处理process的过程上.

首先需要将整个文件读取内容按行进行划分,使用lines函数.lines函数将内容划分成字符串列表[String].


评论

从此可以看到Haskell的一个特点,自带电池,库的强大性.这点基本上在所有的编程语言的发展历史上都有所体现.从C到C++,到Java,包括Haskell,以及一堆在jvm上面的语言.

第二个特点,数据结构的支持,原始的编程语言中很少带有强大的数据结构,但是后续的编程语言都带有强大的数据结构,包括列表,map(或者dict字典,关联数组).

如果说各种各样的库,使得编程语言的能力加性的提高,那么数据结构在使得编程语言的能力有着乘性的提高.


下面需要过滤字符串列表,带有BufferS并且带有status的继续处理,其他的可以丢失掉.结合函数式编程语言标配的filter,只需要提供一个谓词函数就可以了.

1
isStatus x = isInfixOf "BufferS" x && isInfixOf "status" x

函数式编程语言的函数式的特点,可以提供更高的抽象性.一般的函数操作其输入输出数据,高阶的函数操作函数,从而提高更高的抽象性.

1
2
(.&&.) f g a = (f a) && (g a)
isStatus = isInfixOf "BufferS" .&&. isInfixOf "status"

这里的.&&.,其实是一个函数,类似于C++的操作符重载.这里相当于建立一个新的操作符.这个操作将两个谓词函数都应用在参数上并且与起来.也就是组成一个新的谓词函数,要求同时满足两个谓词函数.听起来觉得好像和一般的与似乎差不多啊.

&& -> 返回一个布尔值,该布尔值是两个值的`与`
.&&. -> 返回一个谓词函数,该函数要求同时满足(`与`)两个谓词函数

这样对比一下,好像清晰一点点了.

紧接着,从满足条件的字符串中提取除相应的状态信息.

然后就到了最核心的逻辑的地方了.

1
2
3
4
5
-- find status in bufferstatus line log
probeState = snd . breakOnEnd " status "
-- max Run Length Encoding
maxRLE = maximumBy (comparing snd) . map (head &&& length) . group
  1. 从右向左边看,group将列表划分成列表的列表,这个新的列表中的每个列表都是相同的.
  2. 同时应用head和length函数到列表的元素(第二级的列表).
  3. maximumBy函数,则比较元素的第二个参数.

例如:

["a", "a", "b", "c", "c", "c", "a"]
->
[["a", "a"], ["b"], ["c", "c", "c"], ["a"]]
->
[("a", 2), ("b", 1), ("c", 4), ("a", 1)]
->
("c", 4)

从这一段可以看到Haskell强大的表现力.对Haskell熟悉以后,这一段就像直接翻译处核心逻辑一样.除了关键点的逻辑之外,没有一点点噪声,没有奇奇怪怪的中间变量和下标,没有特意构造出来的临时的数据结构.甚至可以说肯定没有bug,因为这些已经是最上层的逻辑的翻译了,如果有问题,那也是程序员对需求的逻辑没有理解清楚,而不是代码本身的bug.

性能问题

从上面来看,Haskell的这段代码岂不是很好,没有一点问题了?

也不尽然,这段代码的性能比较慢,对于100M+的日志文件,需要处理40s+.这个时间在实际的使用过程中是不能接受的.日常工作中节奏的连贯性是非常重要的,过长的等待时间会使得程序员的注意力无法保持集中,从而打断其工作的状态,因此需要优化.

Haskell的优化可以通过profiling来进行.如果没有profiling则不要做任何优化,因为这个时候根本不知道要优化什么地方,仅仅依赖于幻想来优化,往往只是浪费时间而已.

profile的结果显示,第一步的lines就需要很长的时间.从网上搜索发现,可以通过将String优化为ByteString数据结构,从而大大加快其性能.

兼容性

而Haskell上,ByteString和String是两种数据结构,但是有很多的成员函数?都是API兼容的,从而比较容易切换过去.

注意的是,这里的兼容和一般的API兼容是不同的,这里其实是其域上的函子是一致的.

比如,两个结构上都有isInfixOf函数.

-- Stirng, [Char] 使用的
isInfixOf :: [a] -> [a] -> Bool
-- ByteString
isInfixOf :: ByteString -> ByteString -> Bool
-- 只是保持这个形式不变
T -> T -> Bool

完整的代码在这里

github

回头看,很多地方就是在胡言乱语,姑且先记在这里吧.