最合适的语言计算和内存昂贵的算法 [英] most suitable language for computationally and memory expensive algorithms

问题描述

比方说，你必须实现一个工具来有效地解决了NP问题，与内存使用（在某些情况下，指数以输入尺寸的输出尺寸）的不可避免的可能发生的爆炸，你特别关注这个演出工具的运行时间。该人士$ ​​C $ C也必须阅读和理解，一旦基本的理论而闻名，而这种要求是作为工具本身的效率一样重要。

Let's say you have to implement a tool to efficiently solve an NP-hard problem, with unavoidable possible explosion of memory usage (the output size in some cases exponential to the input size) and you are particularly concerned about the performances of this tool at running time. The source code has also to be readable and understandable once the underlying theory is known, and this requirement is as important as the efficiency of the tool itself.

我个人认为，3种语言可能是适合这三个要求：C ++，斯卡拉，爪哇。 它们都提供关于数据类型的权利的抽象，使得可以比较不同的结构或应用相同的算法（这也是重要的），不同类型的数据。

I personally think that 3 languages could be suitable for these three requirements: c++, scala, java. They all provide the right abstraction on data types that makes it possible to compare different structures or apply the same algorithms (which is also important) to different data types.

C ++有被静态编译和优化的优势，内联函数（如数据结构和算法都经过精心设计）等优化技术是可以实现的性能接近纯C的同时保持了相当不错的可读性。 如果你也投入了很多心血在数据重新presentation可以优化的缓存性能，它可以在速度获得数量级时，高速缓存未命中率较低。

C++ has the advantage of being statically compiled and optimized, and with function inlining (if the data structures and algorithms are designed carefully) and other optimisation techniques it's possible to achieve a performance close to that of pure C while maintaining a fairly good readability. If you also put a lot of care in data representation you can optimise the cache performance, which can gain orders of magnitude in speed when the cache miss rate is low.

Java是代替JIT编译，它允许在运行时期间要应用的优化，和这一类的，可能有不同的运行之间的不同的行为的算法，这可能是一个加在。恐怕不是，这种做法可能会遭受垃圾收集器，但是，在这个算法是很常见连续的分配内存和Java堆的表现是出了名的比C / C更好++的情况下，如果你执行的语言在你自己的内存管理器，你可以即使取得良好的效益。 这种做法反而是不能够内联方法调用（这导致了巨大的性能损失），不给你控制的缓存性能。其中的利弊有比C ++更好的和更清晰的语法。

Java is instead JIT compiled, which allows to apply optimisations during runtime, and in this category of algorithms that could have different behaviours between different runs, that may be a plus. I fear instead that such an approach could suffer from garbage collector, however in the case of this algorithm it's common to continuously allocate memory and java heap performance is notoriously better than C/C++ and if you implement your own memory manager inside the language you could even achieve good efficiency. This approach instead is not able to inline method invocation (which induces a huge performance penalty) and doesn't give you control over the cache performance. Among the pros there's a better and cleaner syntax than C++.

我对Scala的顾虑都或多或少一样的Java，再加上事实，我不能控制的语言进行了优化，除非我对编译器和标准库有深入的了解。但还有：我得到一个非常清晰的语法：）

My concerns about scala are more or less the same as Java, plus the fact that I can't control how the language is optimised unless I have a deep knowledge on the compiler and the standard library. But well: I get a very clean syntax :)

你如何看待关于这个问题的？你不得不处理这个了吗？你会实现一个算法这样的特性和要求，任何一种语言，或者你会建议其他的东西？你会如何​​对它们进行比较？

What's your take on the subject? Have you had to deal with this already? Would you implement an algorithm with such properties and requirements in any of these languages or would you suggest something else? How would you compare them?

推荐答案

通常我的心跳说：C ++。秘密在于C ++简单地产生较少的（内存）的垃圾，需要管理。

Usually I’d say "C++" in a heartbeat. The secret being that C++ simply produces less (memory) garbage that needs managing.

在另一方面，你的看法，即

On the other hand, your observation that

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

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

是一个暗示的Java /斯卡拉实际上可能更适合。但你可以用小对象堆在C ++中也是如此。升压有一个使用标准的分配器接口，如果没有记错。

is a hint that Java / Scala may actually be more suited. But then you could use a small object heap in C++ as well. Boost has one that uses the standard allocator interface, if memory serves.

C ++的另一个优势是明显的利用抽象而不受处罚，通过模板 - 也就是说，你可以轻松地创建通用的算法组件，可以不造成运行时开销由于抽象交互。事实上，你注意的是，

Another advantage of C++ is obviously the use of abstraction without penalty through templates – i.e. that you can easily create generic algorithmic components that can interact without incurring a runtime overhead due to abstraction. In fact, you noted that

这是可能实现的性能接近纯C，同时保持一个相当不错的可读性。

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

- 这是看待事物的错误的方式：<一href="http://programmers.stackexchange.com/questions/29109/is-there-any-reason-to-use-c-instead-of-c-perl-python-etc/29136#29136">Templates让C ++来实现业绩的优于的到的C，同时仍保持较高的抽象。

– this is looking at things the wrong way: Templates allow C++ to achieve performance superior to that of C while still maintaining high abstraction.

这篇关于最合适的语言计算和内存昂贵的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！