f# - 为递归函数的性能分析 F#

Question

我决定用 F# 以有表现力的方式解决 Advent of Code 2018 第一天的第二个问题(执行循环求和并找到第一个重复求和)，但性能不足，找不到原因放缓。

在 Python 3 中解决的问题

For a given input 的总和约为 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 sums/sec 并且即使在一小时后也不会得出解决方案。一个荒谬数量级的戏剧性放缓。

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。