最适合计算和内存开销较大的算法的语言

Question

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

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

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

相反，Java是JIT编译的，这允许在运行时应用优化，并且在这类算法中，不同的运行之间可能具有不同的行为，这可能是一个加号。相反，我担心这样的方法可能会受到垃圾收集器的影响，但是在这种算法中，连续分配内存是很常见的，java堆的性能比C/C++好得出名，如果你在语言中实现自己的内存管理器，你甚至可以达到很好的效率。相反，这种方法不能内联方法调用(这会导致巨大的性能损失)，并且不能控制缓存性能。在优点中，有一种比C++更好、更干净的语法。

我对scala的担忧与Java大致相同，另外一个事实是，除非我对编译器和标准库有深入的了解，否则我无法控制如何优化语言。但是:我得到了一个非常干净的语法:)

你对这个问题有什么看法？你已经处理过这个问题了吗？你会用这些语言中的任何一种来实现具有这样的属性和要求的算法吗?或者你会提出其他的建议吗？你如何比较它们？

Answer 1

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

另一方面，你的观察表明

然而，在此算法的情况下，通常会连续分配内存

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

C++的另一个优势显然是通过模板- i.e使用抽象而没有损失，你可以很容易地创建可以交互的通用算法组件，而不会因为抽象而导致运行时开销。实际上，你注意到了

可以实现接近纯C语言的性能，同时保持相当好的可读性

-这是错误的看待事物的方式：Templates allow C++ to achieve performance to that of C while still maintaining high abstraction.

Answer 2

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

• 从表面上看，它比C++具有更好的源代码可读性，所以这是您要介绍的要点之一。
• 它还具有memory management，这使得与C++和D

的性能进行比较的算法有点easier.

• And templates

• Here is a stackoverflow discussion

Answer 3

您注意到的语言也是我的第一个猜测。

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

不可能区分哪一个是最好的，如果你对它们都足够熟悉，可以绕过它们各自的怪癖，那么可能没有太大的区别。

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

关于C++和Java的一点注意:这真的是一场圣战，如果您关注过最近的发展，您可能会有自己的看法。例如，我认为Java提供了足够好的方面来弥补它的缺陷。

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

最后，请记住，花在几个小时的编程/优化上的钱也可以用在略微优越的硬件上，以弥补遗漏的微小细节。

这一切都可以归结为:只要你做对了(领域知识)，你的任何选择都是可以的。