algorithm - 最适合计算和内存昂贵算法的语言

Question

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

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

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

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

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

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

Answer 1

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

另一方面，你的观察

however in the case of this algorithm it's common to continuously allocate memory

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

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

it's possible to achieve a performance close to that of pure C while maintaining a fairly good readability

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