4

假设您必须实现一个工具来有效地解决一个 NP 难题，内存使用量不可避免地可能会激增（在某些情况下输出大小与输入大小成指数关系），并且您特别关心该工具在运行时的性能时间。一旦知道了基础理论，源代码也必须是可读和可理解的，这一要求与工具本身的效率一样重要。

我个人认为 3 种语言可能适合这三个需求：c++、scala、java。它们都提供了对数据类型的正确抽象，从而可以比较不同的结构或将相同的算法（这也很重要）应用于不同的数据类型。

C++ 具有静态编译和优化的优点，并且通过函数内联（如果数据结构和算法设计仔细）和其他优化技术，可以在保持相当好的可读性的同时实现接近纯 C 的性能。如果您还非常注意数据表示，则可以优化缓存性能，当缓存未命中率较低时，速度可以提高几个数量级。

相反，Java 是 JIT 编译的，它允许在运行时应用优化，并且在这类算法中，在不同的运行之间可能具有不同的行为，这可能是一个加分项。相反，我担心这种方法可能会受到垃圾收集器的影响，但是在这种算法的情况下，连续分配内存是很常见的，而且 java 堆性能比 C/C++ 好得多，如果你在语言中实现自己的内存管理器，你可以甚至达到良好的效率。相反，这种方法不能内联方法调用（这会导致巨大的性能损失），并且不能让您控制缓存性能。在专业人士中，有一种比 C++ 更好、更简洁的语法。

我对 scala 的担忧与 Java 或多或少相同，而且除非我对编译器和标准库有深入的了解，否则我无法控制语言的优化方式。但是很好：我得到了一个非常干净的语法:)

你对这个话题有什么看法？你已经不得不处理这个问题了吗？您会用这些语言中的任何一种实现具有此类属性和要求的算法，还是会提出其他建议？你会如何比较它们？

4

4 回答 4

5

通常我会在心跳中说“C++”。秘诀是 C++ 只产生更少的（内存）垃圾需要管理。

另一方面，你观察到

然而，在这种算法的情况下，连续分配内存是很常见的

暗示 Java / Scala 实际上可能更适合。但是你也可以在 C++ 中使用一个小对象堆。allocator如果没有记错的话，Boost 有一个使用标准接口的。

C++ 的另一个优点显然是使用抽象而不会通过模板受到惩罚——也就是说，您可以轻松地创建可以交互的通用算法组件，而不会因抽象而产生运行时开销。事实上，你注意到

在保持相当好的可读性的同时实现接近纯 C 的性能是可能的

——这是错误的看待事物的方式：模板允许 C++ 实现优于C 的性能，同时仍保持高度抽象。

于 2011-04-11T15:17:28.837 回答
2

D 可能值得一看，看看它如何努力成为更好的 C++。

  • 从表面上看，它比 C++ 具有更好的源代码可读性，所以这是你的观点之一。

  • 它还具有内存管理功能，这使得玩算法更容易一些。

  • 和模板

  • 这是一个比较 C++ 和 D 性能的stackoverflow 讨论

于 2011-04-11T17:28:31.987 回答
1

我会使用一种可以很容易地处理算法的语言。让算法正确，它很容易超过微调错误算法的任何优势。如果该语言更容易表达算法思想，请不要害怕使用通常被认为执行速度慢的语言。将正确的算法翻译成另一种语言通常比用最快的执行语言从错误的算法中找出最后一点速度要容易得多。

因此，请使用您熟悉且富有表现力的语言。您可能会惊讶自己并发现生成的速度足够快！

于 2011-04-20T18:24:40.360 回答
1

你注意到的语言也是我最初的猜测。

每种语言对如何处理编译、内存管理和源代码等特定问题都有不同的看法，但从理论上讲，它们中的任何一种都应该适合您的问题。

无法判断哪个是最好的，如果您对所有这些都足够熟悉以解决它们各自的怪癖，则可能没有重大区别。

显然，如果您真的发现需要优化（我不确定这是否是给定的），那么每种语言都有可能。低级语言显然提供了更多选择，但实际上改进起来也（远）更复杂。

关于 C++ 与 Java 的一个简单说明：这确实是一场圣战，如果您关注了最近的发展，您可能会有自己的看法。一方面，我认为 Java 通常提供了足够好的方面来弥补其缺陷。

关于 C++ 与 C 的最后一点说明：据我所知，差异通常相当于一个足够低的百分比，可以忽略这一点。它对源代码没有影响，使用 C 很好，如果 C++ 可以使源代码更易于阅读，则使用 C++。在任何情况下，选择都是微不足道的。

最后，请记住，花在几个小时的编程/优化上的钱也可以花在稍微高级的硬件上，以弥补错过的微小细节。

这一切都归结为：只要您做得对（领域知识），您的任何选择都可以。

于 2011-04-11T15:19:36.980 回答