我有一个数组 sums，它给出函数 f 的所有可能的总和。此函数接受整数(比如 1 到 200 之间，但同样适用于 1 和 10000)并将它们转换为 double 。我想将 sums 存储为一个数组，因为我还没有弄清楚如何在没有循环的情况下执行我需要的算法。
这是我如何生成和的代码:
let f n k = exp (double(k)/double(n)) - 1.0
let n = 200
let maxLimit = int(Math.Round(float(n)*1.5))
let FunctionValues = [|1..maxLimit|] |> Array.map (fun k -> f n k)
let sums = FunctionValues |> Array.map (fun i -> Array.map (fun j -> j + i) FunctionValues) |> Array.concat |> Array.sort
我发现数组 sums 的某些元素，我想找到一些整数，当输入到函数 f 中然后相加时，它们将等于 中的值总和。我可以将整数存储在 sums 中，但我发现这会破坏我的内存。
现在我有两种算法。算法 1 使用一个简单的循环和一个可变的 int 来存储我关心的值。它应该不是很有效，因为当它找到所有可能的整数时没有 break 语句。我尝试实现更具函数式风格的算法 2，但我发现它速度较慢(慢 10% 或 4200 毫秒 vs 4600 毫秒，n = 10000)，尽管 Seq 是懒惰的。这是为什么？
算法 1:
let mutable a = 0
let mutable b = 0
let mutable c = 0
let mutable d = 0
for i in 1..maxLimit do
for j in i..maxLimit do
if sums.[bestI] = f n i + f n j then
a <- i
b <- j
if sums.[bestMid] = f n i + f n j then
c <- i
d <- j
算法 2:
let findNM x =
let seq = {1..maxLimit} |> Seq.map (fun k -> (f n k, k))
let get2nd3rd (a, b, c) = (b, c)
seq |> Seq.map (fun (i, n) -> Seq.map (fun (j, m) -> (j + i, n, m) ) seq)
|> Seq.concat |> Seq.find (fun (i, n, m) -> i = x)
|> get2nd3rd
let digitsBestI = findNM sums.[bestI]
let digitsBestMid = findNM sums.[bestMid]
let a = fst digitsBestI
let b = snd digitsBestI
let c = fst digitsBestMid
let d = snd digitsBestMid
编辑:请注意数组sums 的长度是maxLimit*maxLimit 而不是长度n。 bestI 和 bestMid 是介于 0 和 maxLimit*maxLimit 之间的索引。出于这个问题的目的，它们可以是该范围内的任何数字。它们的具体值不是特别相关。
最佳答案
我稍微扩展了 OP 代码以对其进行分析
open System
let f n k = exp (double(k)/double(n)) - 1.0
let outer = 200
let n = 200
let maxLimit= int(Math.Round(float(n)*1.5))
let FunctionValues = [|1..maxLimit|] |> Array.map (fun k -> f n k)
let random = System.Random 19740531
let sums = FunctionValues |> Array.map (fun i -> Array.map (fun j -> j + i) FunctionValues) |> Array.concat |> Array.sort
let bests =
[| for i in [1..outer] -> (random.Next (n, maxLimit*maxLimit), random.Next (n, maxLimit*maxLimit))|]
let stopWatch =
let sw = System.Diagnostics.Stopwatch ()
sw.Start ()
sw
let timeIt (name : string) (a : int*int -> 'T) : unit =
let t = stopWatch.ElapsedMilliseconds
let v = a (bests.[0])
for i = 1 to (outer - 1) do
a bests.[i] |> ignore
let d = stopWatch.ElapsedMilliseconds - t
printfn "%s, elapsed %d ms, result %A" name d v
let algo1 (bestI, bestMid) =
let mutable a = 0
let mutable b = 0
let mutable c = 0
let mutable d = 0
for i in 1..maxLimit do
for j in i..maxLimit do
if sums.[bestI] = f n i + f n j then
a <- i
b <- j
if sums.[bestMid] = f n i + f n j then
c <- i
d <- j
a,b,c,d
let algo2 (bestI, bestMid) =
let findNM x =
let seq = {1..maxLimit} |> Seq.map (fun k -> (f n k, k))
let get2nd3rd (a, b, c) = (b, c)
seq |> Seq.map (fun (i, n) -> Seq.map (fun (j, m) -> (j + i, n, m) ) seq)
|> Seq.concat |> Seq.find (fun (i, n, m) -> i = x)
|> get2nd3rd
let digitsBestI = findNM sums.[bestI]
let digitsBestMid = findNM sums.[bestMid]
let a = fst digitsBestI
let b = snd digitsBestI
let c = fst digitsBestMid
let d = snd digitsBestMid
a,b,c,d
let algo3 (bestI, bestMid) =
let rec find best i j =
if best = f n i + f n j then i, j
elif i = maxLimit && j = maxLimit then 0, 0
elif j = maxLimit then find best (i + 1) 1
else find best i (j + 1)
let a, b = find sums.[bestI] 1 1
let c, d = find sums.[bestMid] 1 1
a, b, c, d
let algo4 (bestI, bestMid) =
let rec findI bestI mid i j =
if bestI = f n i + f n j then
let x, y = mid
i, j, x, y
elif i = maxLimit && j = maxLimit then 0, 0, 0, 0
elif j = maxLimit then findI bestI mid (i + 1) 1
else findI bestI mid i (j + 1)
let rec findMid ii bestMid i j =
if bestMid = f n i + f n j then
let x, y = ii
x, y, i, j
elif i = maxLimit && j = maxLimit then 0, 0, 0, 0
elif j = maxLimit then findMid ii bestMid (i + 1) 1
else findMid ii bestMid i (j + 1)
let rec find bestI bestMid i j =
if bestI = f n i + f n j then findMid (i, j) bestMid i j
elif bestMid = f n i + f n j then findI bestI (i, j) i j
elif i = maxLimit && j = maxLimit then 0, 0, 0, 0
elif j = maxLimit then find bestI bestMid (i + 1) 1
else find bestI bestMid i (j + 1)
find sums.[bestI] sums.[bestMid] 1 1
[<EntryPoint>]
let main argv =
timeIt "algo1" algo1
timeIt "algo2" algo2
timeIt "algo3" algo3
timeIt "algo4" algo4
0
我机器上的测试结果:
algo1, elapsed 438 ms, result (162, 268, 13, 135)
algo2, elapsed 1012 ms, result (162, 268, 13, 135)
algo3, elapsed 348 ms, result (162, 268, 13, 135)
algo4, elapsed 322 ms, result (162, 268, 13, 135)
algo1使用天真的 for loop执行。 algo2使用依赖于 Seq.find 的更精细的算法.我描述了algo3和 algo4稍后。
OP 想知道为什么天真 algo1即使它比 algo2 做更多的工作，表现也更好这是基于懒惰 Seq (本质上是一个 IEnumerable<> )。
答案是Seq抽象会引入开销并阻止有用的优化发生。
我通常会查看生成的 IL 代码以了解发生了什么(有很多很好的 .NET 反编译器，如 ILSpy)。
让我们看看algo1 (反编译为 C#)
// Program
public static Tuple<int, int, int, int> algo1(int bestI, int bestMid)
{
int a = 0;
int b = 0;
int c = 0;
int d = 0;
int i = 1;
int maxLimit = Program.maxLimit;
if (maxLimit >= i)
{
do
{
int j = i;
int maxLimit2 = Program.maxLimit;
if (maxLimit2 >= j)
{
do
{
if (Program.sums[bestI] == Math.Exp((double)i / (double)200) - 1.0 + (Math.Exp((double)j / (double)200) - 1.0))
{
a = i;
b = j;
}
if (Program.sums[bestMid] == Math.Exp((double)i / (double)200) - 1.0 + (Math.Exp((double)j / (double)200) - 1.0))
{
c = i;
d = j;
}
j++;
}
while (j != maxLimit2 + 1);
}
i++;
}
while (i != maxLimit + 1);
}
return new Tuple<int, int, int, int>(a, b, c, d);
}
algo1然后扩展为高效的 while loop .另外f是内联的。 JITter 可以轻松地从中创建高效的机器代码。
当我们查看 algo2 时解压整个结构对于这篇文章来说太多了，所以我专注于 findNM
internal static Tuple<int, int> findNM@48(double x)
{
IEnumerable<Tuple<double, int>> seq = SeqModule.Map<int, Tuple<double, int>>(new Program.seq@49(), Operators.OperatorIntrinsics.RangeInt32(1, 1, Program.maxLimit));
FSharpTypeFunc get2nd3rd = new Program.get2nd3rd@50-1();
Tuple<double, int, int> tupledArg = SeqModule.Find<Tuple<double, int, int>>(new Program.findNM@52-1(x), SeqModule.Concat<IEnumerable<Tuple<double, int, int>>, Tuple<double, int, int>>(SeqModule.Map<Tuple<double, int>, IEnumerable<Tuple<double, int, int>>>(new Program.findNM@51-2(seq), seq)));
FSharpFunc<Tuple<double, int, int>, Tuple<int, int>> fSharpFunc = (FSharpFunc<Tuple<double, int, int>, Tuple<int, int>>)((FSharpTypeFunc)((FSharpTypeFunc)get2nd3rd.Specialize<double>()).Specialize<int>()).Specialize<int>();
return Program.get2nd3rd@50<double, int, int>(tupledArg);
}
我们看到它需要创建多个对象来实现 IEnumerable<>以及传递给高阶函数的函数对象，如 Seq.find .虽然原则上 JITter 可以内联循环，但由于时间限制和内存原因，它很可能不会。这意味着每次调用函数对象都是一个虚拟调用，虚拟调用非常昂贵(提示:检查机器代码)。因为虚拟调用可能会做任何反过来阻止优化的事情，例如使用 SIMD 指令。
OP 指出 F# 循环表达式缺少 break/continue在编写高效时有用的构造 for loops .但是，F# 会隐式支持它，因为如果您编写尾递归函数，F# 会将其展开为使用 break/continue 的高效循环。提前退出。
algo3是实现 algo2 的一个例子使用尾递归。反汇编代码是这样的:
internal static Tuple<int, int> find@66(double best, int i, int j)
{
while (best != Math.Exp((double)i / (double)200) - 1.0 + (Math.Exp((double)j / (double)200) - 1.0))
{
if (i == Program.maxLimit && j == Program.maxLimit)
{
return new Tuple<int, int>(0, 0);
}
if (j == Program.maxLimit)
{
double arg_6F_0 = best;
int arg_6D_0 = i + 1;
j = 1;
i = arg_6D_0;
best = arg_6F_0;
}
else
{
double arg_7F_0 = best;
int arg_7D_0 = i;
j++;
i = arg_7D_0;
best = arg_7F_0;
}
}
return new Tuple<int, int>(i, j);
}
这使我们能够编写惯用的函数代码，同时获得非常好的性能，同时避免堆栈溢出。
在我意识到在 F# 中实现尾递归有多好之前，我尝试编写高效的 while在 while 中使用可变逻辑循环测试表达式。为了人类的利益，该代码现在已被废除。
algo4是一个优化版本，因为它只迭代 sums两者一次bestMid和 bestI很像 algo1但是algo4如果可以，尽早退出。
希望对你有帮助
关于arrays - 为什么遍历数组比 Seq.find 更快，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35347420/