18

我需要编写一个程序（大学项目）来解决（大约）一个 NP 难题。它是线性排序问题的一种变体。一般来说，我将有非常大的输入（作为图表）并会尝试找到最佳解决方案（基于将“评价”每个解决方案的函数）

如果我用 C 风格的代码（一个 main 和函数）编写这个或构建一个 Solver 类，创建一个实例并从 main 调用一个“运行”方法（类似于 Java），会有什么不同吗？

此外，每次迭代都会进行大量浮点数学运算。

谢谢！

4

14 回答 14

58

不。

最大的性能提升/缺陷将取决于您实现的算法，以及您执行了多少不需要的工作（不需要的工作可能是从重新计算可能已缓存的先前值到使用过多的 malloc/free 与使用内存池，通过值而不是引用传递大型不可变数据）

于 2009-11-17T18:49:50.267 回答
19

优化代码的最大障碍不再是语言（对于正确编译的语言），而是程序员。

于 2009-11-17T18:52:54.770 回答
9

不，除非您使用虚拟功能。

编辑：如果您有需要运行时动态的情况，那么是的，虚函数与手动构造的if-else语句一样快或更快。但是，如果您在virtual方法前面插入关键字，但实际上并不需要多态性，那么您将付出不必要的开销。编译器不会在编译时优化它。我只是指出这一点，因为它是 C++ 的特性之一，它打破了“零开销原则”（引用 Stroustrup）。

作为旁注，由于您提到大量使用 fp 数学：

  • 以下 gcc 标志可以帮助您加快速度（我确信对于 Visual C++ 有等效的标志，但我不使用它）：-mfpmath=sse和-ffast-math（-mrecip最后两个是“有点危险”，这意味着它们可以给你在边缘情况下会产生奇怪的结果以换取速度。第一个会降低精度——你有 64 位双精度而不是 80 位双精度——但这种额外的精度通常是不需要的。）这些标志同样适用用于 C 和 C++ 编译器。

  • 根据您的处理器，您可能还会发现INFINITY使用较大但不是无限的值模拟 true 可以提高速度。这是因为 trueINFINITY必须由处理器作为特殊情况处理。

    • 于 2009-11-17T18:59:54.293 回答
    6

    经验法则 - 在您知道要优化什么之前不要优化。所以从 C++ 开始，并有一些工作原型。然后对其进行轮廓分析并重写装配中的瓶颈。但正如其他人所指出的，选择的算法将比语言产生更大的影响。

    于 2009-11-17T18:56:37.490 回答
    6

    说到性能，你可以在 C 中做的任何事情都可以在 C++ 中完成。例如，众所周知，虚方法“慢”，但如果确实有问题，您仍然可以求助于 C 习惯用法。

    C++ 还带来了模板，这比void*用于泛型编程具有更好的性能。

    于 2009-11-17T19:14:10.590 回答
    3

    类将Solver被构造一次，我接受它，并且run方法执行一次......在那种环境中，你不会看到任何区别。相反，这里有一些事情需要注意：

    • 内存管理非常昂贵。如果你需要做很多小malloc()s，操作系统会吃掉你的午餐。如果您知道自己很快会再次做同样的事情，请下定决心重用您创建的任何数据结构！

    • 实例化类通常意味着......分配内存！同样，实例化少量对象并重新使用它们实际上没有任何成本。但要注意创建对象只是为了将它们拆除并在不久之后重建它们！

    • 在问题允许的范围内，为您的架构选择合适的浮点类型。尽管它需要更多内存，但最终可能double会比 更快。float您应该尝试对此进行微调。理想情况下，您将使用#defineortypedef来指定类型，以便您可以在一个地方轻松更改它。

    • 整数计算可能比浮点计算快。根据数据的数值范围，您还可以考虑将整数视为定点小数。如果您需要 3 位小数，您可以使用ints 并将它们视为“milli-somethings”。你必须记住在除法和乘法之后移动小数......但没什么大不了的。当然，如果您使用基本算术之外的任何数学函数，那当然会消除这种可能性。

    于 2009-11-17T19:05:59.757 回答
    1

    由于两者都已编译，而且现在的编译器非常擅长处理 C++，我认为唯一的问题来自于代码的优化程度。我认为用 C++ 编写较慢的代码会更容易，但这取决于您的模型最适合哪种风格。

    归根结底，我怀疑是否会有任何真正的区别，假设两者都写得很好，你使用的任何库，它们写得有多好，如果你在同一台计算机上测量。

    于 2009-11-17T18:50:28.893 回答
    1

    只要您不使用任何虚拟功能等，您就不会注意到任何显着的性能差异。早期的 C++ 被编译为 C，所以只要您知道这会产生任何相当大的开销（例如使用虚函数）的精确点，您就可以清楚地计算出差异。

    另外我想指出，如果您使用 STL 和 Boost 库，使用 C++ 可以给您带来很多好处。特别是 STL 为最重要的数据结构和算法提供了非常有效且经过验证的实现，因此您可以节省大量开发时间。

    实际上，它还取决于您将使用的编译器以及它将如何优化代码。

    于 2009-11-17T18:51:06.503 回答
    1

    与文件输入和算法本身相比，函数调用与成员函数调用开销不太可能成为限制因素。C++ iostream 不一定是超高速的。如果你真的在优化，C 有“限制”，在 C++ 中，内联函数调用更容易。总体而言，C++ 为清晰地组织代码提供了更多选择，但如果它不是一个大程序，或者你只是要以类似的方式编写它，无论是 C 还是 C++，那么 C 库的可移植性就变得更加重要。

    于 2009-11-17T18:59:18.127 回答
    1

    首先，用 C++ 编写并不意味着使用 OOP，看看 STL 算法。其次，C++ 在运行时甚至可以稍微快一些（编译时间与 C 相比可能很糟糕，但这是因为现代 C++ 往往严重依赖于对编译器征税的抽象）。

    编辑：好的，请参阅 Bjarne Stroustrup对 qsort 和 std::sort 的讨论，以及常见问题解答提到的文章（学习标准 C++ 作为一种新语言），其中他表明 C++ 样式的代码不仅可以更短且更具可读性（因为更高的抽象），但也有点快。

    于 2009-11-17T19:11:45.510 回答
    1

    另一个方面：

    C++ 模板可以成为生成特定类型/优化代码变体的绝佳工具。

    例如，Cqsort需要对比较器进行函数调用，而std::sort可以内联传递的函子。当比较和交换自己很便宜时，这可能会产生重大影响。

    请注意，您可以使用大量定义或代码生成器或手动生成针对各种类型优化的“自定义 qsorts”——您也可以在 C 中进行这些优化，但成本要高得多。

    （它不是通用武器，模板仅在特定场景中有所帮助 - 通常将单个算法应用于不同的数据类型或注入不同的小段代码。）

    于 2009-11-17T20:02:17.173 回答
    0

    很好的答案。我会这样说：

    1. 使算法在其形式结构方面尽可能高效。

    2. C++ 将和 C 一样快，除了它会诱使你做一些愚蠢的事情，比如构造你不需要的对象，所以不要上钩。STL 容器类和迭代器之类的东西可能看起来是最新最好的东西，但它们会在热点中杀死你。

    3. 即便如此，还是在反汇编级别单步执行。您应该看到它非常直接地解决了您的问题。如果它花费大量周期进入和退出例程，请尝试一些内联（或宏）。如果它在大部分时间里徘徊在内存分配和释放中，请停止它。如果它有循环开销占很大比例的内部循环，请尝试展开循环。

    这样你就可以尽可能快地完成它。

    于 2009-11-17T20:33:16.367 回答
    0

    我肯定会选择 C++。如果您小心设计并避免在热点内创建繁重的对象，您应该不会看到任何性能差异，但代码将更易于理解、维护和扩展。

    明智地使用模板和类。通过引用传递对象来避免不必要的对象创建。避免过多的内存分配，如果需要，在热点之前分配内存。在内存指针上使用 restrict 关键字来告诉编译器指针是否重叠。

    至于优化，请注意内存对齐。假设您正在使用英特尔处理器，您可以使用向量指令，前提是您通过编译指示告诉编译器您的内存对齐和别名指针。您还可以通过内在函数直接使用向量指令。

    如果您有不同大小的短循环之类的东西，您还可以使用模板自动创建热点代码并让编译器对其进行优化。要找出性能并深入了解您的瓶颈，英特尔 vtune 或 oprofile 非常有帮助。

    希望有帮助

    于 2009-11-17T21:43:24.410 回答
    0

    我做了一些 DSP 编码，有时使用汇编语言仍然是值得的。我会说使用 C 或 C++ 中的任何一种，并准备好在需要时使用汇编语言，尤其是利用 SIMD 指令。

    于 2009-11-17T21:48:50.097 回答