分析F#以表示递归函数

Question

我决定使用F#解决第2018号代码出现的第一天(执行循环求和并找到第一个重复的和)的第二个问题,但是性能不足,我找不到原因放缓.

问题在Python 3中得到了解决

对于具有~140,000个求和的给定输入,此代码在几秒钟内执行.

data = list(map(int, '''
+1
-1
'''.strip().splitlines()))
from itertools import cycle, accumulate
class superset(set):
    def add(self, other):
        super().add(other)
        return other

def mapwhile(func, pred, iterable):
    for i in iterable:
        if not pred(i):
            yield func(i)
            return
        yield func(i)

def last(iterable):
    return list(iterable)[-1]

s = superset([0])
print(last(mapwhile(s.add, lambda x: x not in s, accumulate(cycle(data)))))

问题在F#中解决了

我在匹配表达式上添加了一个条件断点,每千i分钟一次,看起来这个代码执行~100次/秒,即使一小时后也不会出现解决方案.一个荒谬的秩序大幅放缓.

let input = @"
+1
-1
"
let cycle xs = seq { while true do yield! xs }
let accumusum xs = Seq.scan(fun acc elem -> acc + elem) 0 xs

let rec findfreqcycle i (s:int Set) (data:int seq) = 
    let head, tail = Seq.head data, Seq.tail data
    match s.Contains(head) with
    | false -> findfreqcycle (i+1) (s.Add(head)) (tail)
    | true ->  head


let data = input.Trim().Split('\n') |> Seq.map int |> Seq.toList |> cycle
accumusum data |> findfreqcycle 0 Set.empty

据我所知,每个代码示例背后的核心思想或多或少都是一样的.输入只被急切地解析一次,生成器函数/序列懒洋洋地重复每个数字.

唯一的区别是实际找到第一个重复求和的函数在F#示例中是递归的.内存分析表明内存使用几乎是恒定的,尾递归是活动的.

我可能做错了什么,我怎样才能更好地分析这些递归和生成函数的性能？

Answer 1

正如评论中所提到的那样,Seq.tail效率非常低,特别是如果你按照自己的方式在循环中使用它.原因是它创建了一个新的序列,它迭代原始序列并跳过第一个元素(因此,在1000次迭代之后,你必须超过1000个序列,每个序列跳过一个元素).

如果使用列表,头部和尾部的模式效果会更好,因为功能列表已经设计用于此类处理.在你的情况下,你可以做这样的事情(它遵循与原始函数相同的模式):

let rec findfreqcycle sum (s:int Set) input data = 
    match data with 
    | x::xs when s.Contains (sum + x) -> (sum + x)
    | x::xs -> findfreqcycle (sum + x) (s.Add (sum + x)) input xs
    | [] ->  findfreqcycle sum s input input

let data = input.Trim().Split('\n') |> Seq.map int |> Seq.toList 
findfreqcycle 0 Set.empty data data

我更改了它,以便它使用模式匹配(在列表上).我还更改了代码,以便它采用有限列表,当它到达结束时,它再次启动.因此,它还会动态汇总数字(而不是使用Seq.scan- 这在这里不起作用,因为我没有使用无限列表).

在来自Pastebin的输入上,我在大约0.17秒内得到结果448.

Answer 2

我决定放弃使用Seq.scan和Seq.pick根据托马斯的回答一试推行,并得到了这样的结果.他是对的,这不是很好.在好的方面,它在~0.3秒内执行.

let cycle xs = seq { while true do yield! xs }    
let accumusum xs = Seq.scan(fun acc elem -> acc + elem) 0 xs

let tryfind (sum, s:int Set) =
    match s.Contains(sum) with
    | true -> Some(sum)
    | false -> None

let scanstate (sum, s:int Set) el =
    el, s.Add(sum)

let findfreqcycle (data:int seq) =
    let seen = Seq.scan scanstate (Seq.head data, Set.empty) (Seq.tail data)
    Seq.pick tryfind seen

let data = cycle <| (input.Trim().Split('\n') |> Seq.map int |> Seq.toList)
accumusum data |> findfreqcycle