意外的平方复杂度：当 Python 比 C++ 更快

导读

这篇论文讨论一个反直觉现象：在某些使用 C++ 标准容器和递归比较的代码中，比较器会被反复调用，使复杂度意外退化为二次（评论者指出最坏可到指数），结果反而比 Python 实现慢。它提醒复杂度分析要计入比较操作本身的代价和嵌套深度，而不能只看容器操作次数。

HN 关注点：『Python 比 C++ 快』究竟源于 C++ 使用/实现不当和常数因素，还是真正的渐近复杂度陷阱；讨论也延伸到最坏指数与 DoS 风险。

关键词　C++std::set算法复杂度性能

HN 评论精选

这几条评论里：支持 1　质疑 2　亲历 1

亲历亲历：C++ set 比较器重复调用带来显著常数开销，嵌套加深会放大。

如果你想知道这是理论问题还是实际问题：我实际上先在实践中观察到其中一些效应，思考一段时间后才意识到更大的问题（以及复杂度含义）。几年前我的程序里有类似 set<string> 或 set<set<string>>（或 map，记不清了），我试图优化性能。多次断点调试发现瓶颈似乎是 set<> 容器。我明白缓存局部性有影响，但影响似乎过大。为什么奇怪？因为其他语言（如 C#）也有树形 set/map，但我从没觉得它们像 C++ 这样慢。我单步观察，意识到这些函数被调用得比直觉上必要次数多。事后显然：less() 需要对同一对象多次调用（第 2 层 4 次）。这没导致二次行为，只因为数据结构没有任意深；但 slowdown 是核心的显著常数因子，最终只是线性增长。

mehrdadn查看英文原文

If you're wondering whether this is a theoretical or practical problem: I actually observed some of this effect in practice first, and only after thinking about it for a while did the larger issue (and the complexity implications) dawn on me. I had something like a set<string> or a set<set<string>> (or map... I can't remember which) somewhere in my program a few years ago, and I was trying to improve the program's performance. I tried breaking into it several times and found it quite perplexing that the bottleneck appeared to be the set<> container. I mean, I get that cache locality and all has an effect, but it seemed to be having a little too much of an effect. Why did I find this odd? Because other languages (like C#) have tree-based sets and maps too, but I'd never felt they were quite as slow as I was seeing them in C++. So I felt something weird must be going on. I tried to step through the program for a while and observe what's going on, and at some point, I realized (perhaps I hit the same breakpoint twice? I don't recall) that these functions were being called more often than I intuitively thought would be necessary. Which was obvious in hindsight, as less() needs to be called multiple times on the same objects (4 times at level 2). Now, this hadn't resulted in quadratic behavior, but that was only because my data structures weren't arbitrarily deep—the slowdown was nevertheless a significant constant factor at the core of my program, only linear because the data structure's depth was bounded. So once I had realized the implications of this, including that constant-factor differences can actually turn into polynomial ones, I eventually decided to post an article about it on arXiv... hence this article. Aside from the complexity issue illustrated in the article, one of my (unexpected) higher-level takeaways was that you can't just take any utility function in a program and blindly put it into a library: even if it's correct, you probably have hidden assumptions about its use cases that won't hold true in general. You really need to think about how it could be used in ways you didn't initially expect, and this may well require a different kind of code review with an entirely different mindset than before. It really drove home the point for me that writing a library is quite a bit different (and in some ways more difficult) than writing an application. It's possible there is more theory lying underneath this that I haven't touched on—it would be interesting if someone can take this and find more interesting consequences of it. For example, maybe when analyzing algorithms we need to consider something akin to a "recursive time complexity", too? Is there another useful notion of complexity that we can generalize here? Anyway, hope people enjoy reading it and take something useful away from it. :)

支持Python 更快通常因底层库或 C++ 使用不当；常数与实测很重要。

CPython 在以下情况比 C++ 快：1) 通过 Python 使用由比你更好的 C/C++ 程序员写的原生库，且大部分时间花在库里；2) Python 中用的原生库比对比的 C/C++ 库实现更好；3) 你不了解所用的 C/C++ 库（正是本文讨论的）。否则，如果只是基本控制流，优化编译器下的 C/C++ 几乎总是更快（除非用 numba/pypy）。关于常数的观点成立：渐近分析告诉缩放，但追求原始性能特别小数据时必须测量，因为软硬件实现细节影响更大（小 n 时执行时间增长甚至不平滑）。

a-dub查看英文原文

cpython is faster than c++ under the following circumstances: 1) when you're using native libraries via python that were written by better c/c++ programmers than you are and you're spending most of your time within them 2) when you're using native libraries in python that are better implementations than the c/c++ libraries you're comparing against 3) when you don't know the libraries you're using in c/c++ (what they're talking about here) ...otherwise, if you're just using doing basic control flow optimizing compiler c/c++ will almost always be faster. (unless you're using numba or pypy or something). point stands about the constants though. yes, asymptotic analysis will tell you about how an algorithm's performance scales, but if you're just looking for raw performance, especially if you have "little data", you really have to measure as implementation details of the software and hardware start to have a greater effect. (often times the growth of execution time isn't even smooth with the growth of n for small n)

质疑质疑『比 C 快』的指标意义，语言表达力差异使比较不公平。

我最近在想：你真的能比 C 快吗？任何 Python/Lisp/Haskell/Rust/JS 都能转译成 C，但反过来不一定，因为不是所有语言支持 C 的全部特性（goto、无边界检查、指针运算等）。所以任何算法比如 JSON 解析都能在 C 中同等高效表达，而巧妙 hack 的 C 专用算法不一定能在高级语言表达。换言之，如果『faster than C』只意味着『低效 C 实现会比高效非 C 实现快』，它还是好指标吗？

IgorPartola查看英文原文

I’ve been thinking about this lately. Can you actually be faster than C? Like, in the sense that you can transpile any bit of Python or Lisp or Haskell or Rust or JS into C but the opposite isn’t necessarily true because not all those language support all the features exposed in C (such as goto, no bounds checking, pointer arithmetic, etc.), any algorithm for say parsing JSON can be expressed equally as efficiently in C, while a clever and hacky C-specific algorithm cannot necessarily be expressed in those higher level languages. In other words, is “faster than C” even a good metric if all it means that “if you implement something inefficiently in C it will be faster than if it is implemented efficiently in not-C”?

质疑最坏是指数而非二次，且可被 DoS 利用。

等等，这不是意外二次，最坏情况是意外指数。如果把树的分支因子设成 1，C++ std::less 的运行时间会变成 2^h，但只有 h 个节点。演示（ideone.com/CBIEAE）创建约 60 个对象，但解析需要约 2^30 次操作（在线运行器超时，我笔记本 -O3 约 5s）。这比论文声称的严重得多！意外指数算法让 DoS 攻击变得容易。

nneonneo查看英文原文

Hang on, this isn't accidentally quadratic, this is accidentally exponential in the worst case. If you set the tree branching factor to one, then the running time of C++‘s std::less becomes 2^h, but there’s only h nodes. Demo: https://ideone.com/CBIEAE This creates ~60 objects, but takes something like 2^30 operations to resolve (it times out on this online runner, and takes around 5s on my laptop with -O3). That's much worse than claimed in this paper! An accidentally-exponential algorithm is the kind of thing that makes DoS attacks trivial...

历次讨论

2021Hacker News 讨论帖218 分 · 213 评

HN 二十年，最值得读的论文。

朋友分享的书单

专题阅读路线

本周最多人读

我的书单

必读 30 篇

论文库

这些论文是怎么挑出来的

全量扫一遍

只留论文本身

写导读、译评论

意外的平方复杂度：当 Python 比 C++ 更快

导读

HN 评论精选

相关资源

历次讨论

同领域还值得读

Google 的软件工程（2017）

Peter Naur：编程作为理论构建 (1985)

SciPy 1.0：Python 科学计算的基础算法

Lisp 的历史（1979）

使用 NumPy 进行数组编程

打赏支持

关注向阳乔木