简单的问题,问Haskellites:Haskell是否迭代整个序列以获取最后一个值?具体来说,这两个表达式执行的指令数量是否不同?
Prelude> last "asdf"
'f'
Prelude> last "qwerty"
'y'
简单的问题,问Haskellites:Haskell是否迭代整个序列以获取最后一个值?具体来说,这两个表达式执行的指令数量是否不同?
Prelude> last "asdf"
'f'
Prelude> last "qwerty"
'y'
是的,Haskell的列表是单链表,因此last
需要遍历整个列表,使其运行时间为O(n)
。
O(n)
的时间。其次,尝试并发现它需要更长的时间,并不能解释为什么它需要更长的时间(这就是说Haskell列表是单向链接的原因)。 - sepp2k除了sepp2k所说的之外,这很容易确定:只需运行“last [1..1000000000]”并查看是否需要一段时间。如预期的那样,它确实需要一段时间。
正如其他两个答案所说:是的,对于标准列表,last是O(n)的操作。如果您正在处理文本数据,可以考虑使用text package,该软件包提供了一个O(1)的last function。如果您不处理文本数据,则可以查看bytestring或vector软件包。