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

Question

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

我个人认为3种语言可能适合这三个要求:c ++,scala,java.它们都提供了对数据类型的正确抽象,使得可以比较不同的结构或将相同的算法(这也很重要)应用于不同的数据类型.

C++具有静态编译和优化的优点,并且通过函数内联(如果数据结构和算法经过精心设计)和其他优化技术,可以在保持相当好的可读性的同时实现接近纯C的性能.如果您在数据表示中也非常谨慎,则可以优化缓存性能,当缓存未命中率较低时,缓存性能可以获得数量级的速度.

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

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

你对这个问题有什么看法？你有没有必须处理这个？您是否会使用这些语言中的任何一种语言实现具有此类属性和要求的算法,或者您会建议其他什么？你会如何比较它们？

Answer 1

通常我会在心跳中说"C++".秘密在于C++只会产生需要管理的较少(内存)垃圾.

另一方面,你的观察

但是在这种算法的情况下,连续分配内存是很常见的

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

C++的另一个优点显然是通过模板使用抽象而不会受到惩罚 - 即,您可以轻松创建可以交互的通用算法组件,而不会因抽象而导致运行时开销.事实上,你注意到了

它可以实现接近纯C的性能,同时保持相当好的可读性

- 这是以错误的方式看待事物:模板允许C++实现优于 C的性能,同时仍然保持高抽象.