c++ - for-loop的条件只有在断点后才生效
问题描述
我正在尝试解决来自hackerrank的问题。
目前我的代码是错误的，但这不是这个问题的重点。问题是for循环，它的条件似乎并不总是有效。这是代码：
#include <cassert>
#include <iostream>
#include <set>
using namespace std;
// Integer power.
long ipow(int x, int y)
{
assert(x > 0);
assert(y >= 0);
long res = 1;
while (y--)
res *= x;
return res;
}
std::set<int> compute_distinct_sequence_numbers(int n, int s, int p, int q)
{
static_assert(sizeof(long) > 4, "long is assumed to be larger 4 bytes");
set<int> distinct_numbers;
const long max1 = ipow(2, 31); // maximum plus 1
// Compute first number of sequence.
int prev = s % max1;
distinct_numbers.emplace(prev);
// Compute subsequent elements of sequence and put them in set.
for (int i = 1; i < n; ++i) {
prev = (prev * p + q) % max1;
distinct_numbers.emplace(prev);
}
return distinct_numbers;
}
int main(int argc, char** argv)
{
// Read numbers.
int n, s, p, q;
if (!(cin >> n >> s >> p >> q))
throw std::runtime_error("error on input");;
// Compute set containing distinct number of sequence.
std::set<int> distinct_numbers = compute_distinct_sequence_numbers(n, s, p, q);
// Print number of distinct numbers in sequence.
cout << distinct_numbers.size() << std::endl;
return 0;
}
如果我使用输入“10000000 658061970 695098531 1430548937”运行程序，则需要很长时间才能完成（几乎 20 秒）。
i我遇到的主要问题是到达时循环不退出n。当我在 GDB 中停止程序时，程序卡在循环中并且i可能有一个大于n.
以下 GDB 会话演示了这一点：
(gdb) run
Starting program: /home/janosch/programming/hackerrank/cpp/main
10000000 658061970 695098531 1430548937
Breakpoint 1, compute_distinct_sequence_numbers (n=10000000, s=658061970, p=695098531, q=1430548937) at main.cpp:32
32 prev = (prev * p + q) % max1;
(gdb) print i
$7 = 10000000
(gdb) info breakpoints
Num Type Disp Enb Address What
1 breakpoint keep y 0x00000000004010c0 in compute_distinct_sequence_numbers(int, int, int, int) at main.cpp:32
stop only if i = n
breakpoint already hit 1 time
(gdb) n
33 distinct_numbers.emplace(prev);
(gdb)
31 for (int i = 1; i < n; ++i) {
(gdb)
36 return distinct_numbers;
(gdb)
37 }
我i == n在行上设置了一个条件断点 ()
prev = (prev * p + q) % max1;。通常不可能命中这个断点，因为循环应该在命中之前退出n。即使我为条件断点使用了更高的值（如i == 2*n），也会触发断点。
一旦我到达断点，程序就会立即退出循环。这适用于单步执行（GDB 命令n）和继续执行（GDB 命令c）。
这是我超级简单的 Makefile：
CC = g++
CFLAGS = -Wall -std=c++14 -c -g
LDFLAGS =
all: main
main: main.o
$(CC) $(LDFLAGS) main.o -o main
main.o: main.cpp
$(CC) $(CFLAGS) main.cpp
该程序在 Ubuntu 16.04 上运行。
我究竟做错了什么？程序在 GDB 中运行时的行为有何不同？这似乎简单得令人尴尬。
解决方案
一旦我到达断点，程序就会立即退出循环。
这是PEBKAC的一个实例。正如 Mark Plotnick 所注意到的，您的断点条件不仅仅是一个条件，而是一个条件和一个赋值。
每次评估条件时，i都会分配 value n，然后根据 0 评估结果。
这意味着在调试器下，有了这个特定的“条件”断点，你的循环只执行一次。
现在，当我根本不附加 GDB 时，我观察到：
$ g++ -g t.cc -O0 && echo "10000000 658061970 695098531 1430548937" | time ./a.out
10000000
18.15user 0.20system 0:18.36elapsed 99%CPU (0avgtext+0avgdata 472032maxresident)k
0inputs+0outputs (0major+117322minor)pagefaults 0swaps
$ g++ -g t.cc -O2 && echo "10000000 658061970 695098531 1430548937" | time ./a.out
10000000
12.09user 0.14system 0:12.27elapsed 99%CPU (0avgtext+0avgdata 472028maxresident)k
0inputs+0outputs (0major+117322minor)pagefaults 0swaps
从中我们可以得出结论，程序很慢是因为它执行了 1000 万次迭代，而不是因为for循环被某种方式破坏了。
使用perf recordand perf report，我们可以看到所有这些时间都花在了哪里：
# Samples: 50K of event 'cycles:uppp'
# Event count (approx.): 50290745010
#
# Overhead Command Shared Object Symbol
# ........ ....... ................... ...............................................................................................................
#
79.02% a.out a.out [.] std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_M_emplace_unique<int&>
8.75% a.out a.out [.] std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_M_erase
5.82% a.out libstdc++.so.6.0.25 [.] std::_Rb_tree_insert_and_rebalance
0.93% a.out libstdc++.so.6.0.25 [.] 0x00000000000a9440
0.89% a.out libc-2.28.so [.] _int_malloc
0.86% a.out libc-2.28.so [.] cfree@GLIBC_2.2.5
0.81% a.out a.out [.] compute_distinct_sequence_numbers
0.78% a.out libc-2.28.so [.] _int_free