C# Memoization optimization functional-programming

如何从“纯函数”中获得优化在 C# 中？

发布于 2024-08-03 11:09:12 字数 324 浏览 6 评论 0原文

如果我有以下函数，它被认为是纯粹的，因为它没有副作用，并且在给定相同的输入x的情况下总是会产生相同的结果。

public static int AddOne(int x) { return x + 1; }

据我了解，如果运行时理解函数纯度，它可以优化执行，这样就不必重新计算返回值。

有没有办法在 C# 中实现这种运行时优化？我认为这种优化有一个名称。它叫什么？

编辑：显然，我的示例函数不会从这种优化中获得很多好处。这个例子是为了表达我心目中的纯洁类型，而不是现实世界的例子。

原文

If I have the following function, it is considered pure in that it has no side effects and will always produce the same result given the same input x.

public static int AddOne(int x) { return x + 1; }

As I understand it, if the runtime understood the functional purity it could optimize execution so that return values wouldn't have to be re-calculated.

Is there a way to achieve this kind of runtime optimization in C#? And I assume there is a name for this kind of optimization. What's it called?

Edit: Obviously, my example function wouldn't have a lot of benefit from this kind of optimization. The example was given to express the type of purity I had in mind rather than the real-world example.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

时光与爱终年不遇 2024-08-10 11:09:12

正如其他人所指出的，如果您想节省重新计算已经计算过的结果的成本，那么您可以记住该函数。这会增加内存使用量以提高速度 - 如果您怀疑如果缓存无限增长，您可能会耗尽内存，请记住偶尔清除缓存。

然而，除了记忆结果之外，还可以对纯函数执行其他优化。例如，纯函数没有副作用，通常可以安全地在其他线程上调用。使用大量纯函数的算法通常可以并行化以利用多核。

随着大规模多核机器变得更便宜、更常见，这一领域将变得越来越重要。我们对 C# 语言有一个长期研究目标，即找到某种方法来利用语言、编译器和运行时中纯函数（以及不纯但“隔离”的函数）的强大功能。但这样做涉及到许多难题，业界或学术界对于最佳方法几乎没有达成共识。高层正在考虑这个问题，但不要指望很快就会有任何重大结果。

回复收藏 0 原文

情仇皆在手 2024-08-10 11:09:12

如果计算成本很高，您可以将结果缓存到字典中吗？

    static Dictionary<int, int> cache = new Dictionary<int, int>();
    public static int AddOne(int x)
    {
        int result;
        if(!cache.TryGetValue(x, out result))
        {
            result = x + 1;
            cache[x] = result;
        }
        return result;
    }

当然，这种情况下的字典查找比添加的成本更高:)

Wes Dyer 解释了另一种更酷的功能记忆化方法：http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx - 如果你做了很多这样的缓存，那么他的 Memoize 函数可能会为你节省很多代码......

if the calculation was a costly one, you could cache the result in a dictionary?

    static Dictionary<int, int> cache = new Dictionary<int, int>();
    public static int AddOne(int x)
    {
        int result;
        if(!cache.TryGetValue(x, out result))
        {
            result = x + 1;
            cache[x] = result;
        }
        return result;
    }

of course, the dictionary lookup in this case is more costly than the add :)

There's another much cooler way to do functional memoization explained by Wes Dyer here: http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx - if you do a LOT of this caching, then his Memoize function might save you a lot of code...

回复收藏 0 原文

幸福不弃 2024-08-10 11:09:12

我认为您正在寻找功能记忆化

回复收藏 0 原文

后来的我们 2024-08-10 11:09:12

您需要的技术是记忆化：在数组或字典中缓存执行结果，关闭传递给函数的参数。运行时不会自动应用它，尽管在某些情况下它们会自动应用它。 C# 和 .NET 都不会自动应用记忆化。您可以自己实现记忆化 - 这相当简单 - 但这样做通常仅对于较慢的纯函数有用，在这些纯函数中您倾向于重复计算并且您有足够的内存。

回复收藏 0 原文

贱贱哒 2024-08-10 11:09:12

这可能会被编译器内联（又名内联扩展） ...

只需确保使用“优化代码”标志集编译代码（在 VS 中：项目属性/构建选项卡/优化代码）

您可以做的另一件事是缓存结果（又名 记忆化）。然而，由于您的查找逻辑，初始性能会受到巨大影响，因此这仅对慢速函数（即不是 int 加法）有意义。

它还会对内存产生影响，但这可以通过巧妙使用弱引用来管理。

据我了解，如果运行时
了解功能纯度吧
可以优化执行，以便
返回值不必是
重新计算。

在您的示例中，运行时将必须计算结果，除非 x 在编译时已知。在这种情况下，您的代码将通过使用常量折叠< /a>

回复收藏 0 原文

云柯 2024-08-10 11:09:12

编译器怎么能这么做呢？它如何知道运行时将传入 x 的值？

以及回复：提到内联的其他答案......
我的理解是，内联（作为一种优化）对于仅使用一次（或仅很少几次......）的小函数是有保证的，而不是因为它们没有副作用......

回复收藏 0 原文

溺深海 2024-08-10 11:09:12

编译器可以通过内联（在调用站点用该函数的主体替换函数调用）和常量传播（用没有的表达式替换表达式）的组合来优化此函数带有该表达式结果的自由变量）。例如，在这段代码中：

AddOne(5);

AddOne 可以被内联：

5 + 1;

常量传播可以简化表达式：（

6;

死代码消除可以进一步简化该表达式，但这只是一个示例）。

知道 AddOne() 没有副作用也可能使编译器能够执行常见子表达式消除，因此：

AddOne(3) + AddOne(3)

转换为：

int x = AddOne(3);
x + x;

可以通过强度降低 or ，甚至：

2*AddOne(3);

没有办法命令c# JIT编译器执行这些优化；它自行优化。但它非常智能，您应该放心地依赖它来执行这些类型的转换，而无需您的干预。

A compiler can optimize this function through a combination of inlining (replacing a function call with the body of that function at the call site) and constant propagation (replacing an expression with no free variables with the result of that expression). For example, in this bit of code:

AddOne(5);

AddOne can be inlined:

5 + 1;

Constant propagation can then simplify the expression:

6;

(Dead code elimination can then simplify this expression even further, but this is just an example).

Knowing that AddOne() has no side effects might also enable the a compiler to perform common subexpression elimination, so that:

AddOne(3) + AddOne(3)

may be transformed to:

int x = AddOne(3);
x + x;

or by strength reduction, even:

2*AddOne(3);

There is no way to command the c# JIT compiler to perform these optimizations; it optimizes at its own discretion. But it's pretty smart, and you should feel comfortable relying on it to perform these sorts of transformations without your intervention.

回复收藏 0 原文