我正试图解决hackerlink中的一个问题。
目前，我的代码是糟糕和错误的，但这不是这个问题的重点。问题是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都被赋予值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 record和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