这是一个创建于 317 天前的主题，其中的信息可能已经有所发展或是发生改变。
事情的开始是我在调试一段算法题的代码, 这段代码的算法比较复杂, debug 非常不便, 我便萌生出跟踪算法每一步的执行的想法, 尽管 IDE 提供了断点的功能, 但实在也不是特别方便, 于是我开发了 Prouter 算法示踪库
GitHub: https://github.com/Dynesshely/Prouter
下面是从仓库复制过来的 README:
About
Prouter is a library that allows you to trace your code and visualize your algorithm.
Usages
Includes
#include <prouter/includes.h>
and you'd better include predefine.h after main function like this:
#include <prouter/includes.h>
int main() {
#include <prouter/predefine.h>
......
Trace a var
double a = 3.0;
a = 4.0, a *= 2.0;
std::cout << a.history() << std::endl << std::endl;
Output:
3.000000 -> 4.000000 -> 8.000000
Trace an array
auto int_arrTracer = prouter::traceArray().named("int arr tracer");
int intarr[10] = {0};
int_arrTracer.trace(intarr, 10);
for (int i = 0; i < 10; ++i) intarr[i] = i;
int_arrTracer.printTo(std::cout, true).dispose();
auto num_arrTracer = prouter::traceArray().named("num arr tracer");
double numarr[10] = {0};
num_arrTracer.trace(numarr, 10);
for (int i = 0; i < 10; ++i) numarr[i] = i;
std::cout << num_arrTracer.history() << std::endl;
num_arrTracer.dispose(numarr);
Output:
╔════════════════════════════════╗
║ int arr tracer ║
╠════════════════════════════════╣
║ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ║
╠════════════════════════════════╣
║ [0, 1, 0, 0, 0, 0, 0, 0, 0, 0] ║
╠════════════════════════════════╣
║ [0, 1, 2, 0, 0, 0, 0, 0, 0, 0] ║
╠════════════════════════════════╣
║ [0, 1, 2, 3, 0, 0, 0, 0, 0, 0] ║
╠════════════════════════════════╣
║ [0, 1, 2, 3, 4, 0, 0, 0, 0, 0] ║
╠════════════════════════════════╣
║ [0, 1, 2, 3, 4, 5, 0, 0, 0, 0] ║
╠════════════════════════════════╣
║ [0, 1, 2, 3, 4, 5, 6, 0, 0, 0] ║
╠════════════════════════════════╣
║ [0, 1, 2, 3, 4, 5, 6, 7, 0, 0] ║
╠════════════════════════════════╣
║ [0, 1, 2, 3, 4, 5, 6, 7, 8, 0] ║
╠════════════════════════════════╣
║ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] ║
╚════════════════════════════════╝
[0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000]
[0.000000, 1.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000]
[0.000000, 1.000000, 2.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000]
[0.000000, 1.000000, 2.000000, 3.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000]
[0.000000, 1.000000, 2.000000, 3.000000, 4.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000]
[0.000000, 1.000000, 2.000000, 3.000000, 4.000000, 5.000000, 0.000000, 0.000000, 0.000000, 0.000000]
[0.000000, 1.000000, 2.000000, 3.000000, 4.000000, 5.000000, 6.000000, 0.000000, 0.000000, 0.000000]
[0.000000, 1.000000, 2.000000, 3.000000, 4.000000, 5.000000, 6.000000, 7.000000, 0.000000, 0.000000]
[0.000000, 1.000000, 2.000000, 3.000000, 4.000000, 5.000000, 6.000000, 7.000000, 8.000000, 0.000000]
[0.000000, 1.000000, 2.000000, 3.000000, 4.000000, 5.000000, 6.000000, 7.000000, 8.000000, 9.000000]
Trace a loop
auto loopTracer = prouter::traceLoop().named("loop 1");
int f[13], i = 1, fc;
f[1] = 1, f[2] = 1;
loopTracer.trace(&i.named("i"))
.trace(&fc.named("fc"))
.trace(f, 13, 2);
for (; i <= 10; ++i, loopTracer.loop()) {
if (i >= 3)
f[i] = f[i - 1] + f[i - 2];
fc.setValue(f[i]);
}
loopTracer.end().printTo(std::cout);
Output:
╔═══╦══════════╦══════════╦═════════════════════════════════════════════╗
║ ║ i ║ fc ║ default array tracer ║
╠═══╬══════════╬══════════╬═════════════════════════════════════════════╣
║ 0 ║ 1 -> 2 ║ 0 -> 1 ║ [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ║
╠═══╬══════════╬══════════╬═════════════════════════════════════════════╣
║ 1 ║ 2 -> 3 ║ 1 -> 1 ║ [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ║
╠═══╬══════════╬══════════╬═════════════════════════════════════════════╣
║ 2 ║ 3 -> 4 ║ 1 -> 2 ║ [0, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0] ║
╠═══╬══════════╬══════════╬═════════════════════════════════════════════╣
║ 3 ║ 4 -> 5 ║ 2 -> 3 ║ [0, 1, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0] ║
╠═══╬══════════╬══════════╬═════════════════════════════════════════════╣
║ 4 ║ 5 -> 6 ║ 3 -> 5 ║ [0, 1, 1, 2, 3, 5, 0, 0, 0, 0, 0, 0, 0] ║
╠═══╬══════════╬══════════╬═════════════════════════════════════════════╣
║ 5 ║ 6 -> 7 ║ 5 -> 8 ║ [0, 1, 1, 2, 3, 5, 8, 0, 0, 0, 0, 0, 0] ║
╠═══╬══════════╬══════════╬═════════════════════════════════════════════╣
║ 6 ║ 7 -> 8 ║ 8 -> 13 ║ [0, 1, 1, 2, 3, 5, 8, 13, 0, 0, 0, 0, 0] ║
╠═══╬══════════╬══════════╬═════════════════════════════════════════════╣
║ 7 ║ 8 -> 9 ║ 13 -> 21 ║ [0, 1, 1, 2, 3, 5, 8, 13, 21, 0, 0, 0, 0] ║
╠═══╬══════════╬══════════╬═════════════════════════════════════════════╣
║ 8 ║ 9 -> 10 ║ 21 -> 34 ║ [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 0, 0, 0] ║
╠═══╬══════════╬══════════╬═════════════════════════════════════════════╣
║ 9 ║ 10 -> 11 ║ 34 -> 55 ║ [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 0, 0] ║
╚═══╩══════════╩══════════╩═════════════════════════════════════════════╝
Trace a stack
auto pstackTest = (new stack<s_int>())->push(4)
.push(8)
.push(2)
.pop()
.push(9)
.pop()
.push(3)
.pop()
.push(1)
.pop()
.clear()
.printHistoryTo(std::cout);
Here use
s_intto avoid usingpint
Output:
+---+ +---+ +---+ +---+
| | | | | | | |
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
--> | | --> | 2 | --> | | --> | 9 | --> | | --> | 3 | --> | | --> | 1 | --> | | -->
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
| | | 8 | | 8 | | 8 | | 8 | | 8 | | 8 | | 8 | | 8 | | 8 |
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
| 4 | | 4 | | 4 | | 4 | | 4 | | 4 | | 4 | | 4 | | 4 | | 4 | | |
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
Trace a queue
auto pqueueTest = (new queue<int>())->push(3)
.push(7)
.pop()
.push(16)
.pop()
.push(12)
.push(244)
.push(9)
.pop()
.pop()
.clear()
.printHistoryTo(std::cout);
Output:
+----+---+----+
0 | <- | 3 | <- |
+----+---+----+
+----+---+---+----+
1 | <- | 3 | 7 | <- |
+----+---+---+----+
+----+---+----+
2 | <- | 7 | <- |
+----+---+----+
+----+---+----+----+
3 | <- | 7 | 16 | <- |
+----+---+----+----+
+----+----+----+
4 | <- | 16 | <- |
+----+----+----+
+----+----+----+----+
5 | <- | 16 | 12 | <- |
+----+----+----+----+
+----+----+----+-----+----+
6 | <- | 16 | 12 | 244 | <- |
+----+----+----+-----+----+
+----+----+----+-----+---+----+
7 | <- | 16 | 12 | 244 | 9 | <- |
+----+----+----+-----+---+----+
+----+----+-----+---+----+
8 | <- | 12 | 244 | 9 | <- |
+----+----+-----+---+----+
+----+-----+---+----+
9 | <- | 244 | 9 | <- |
+----+-----+---+----+
+----+---------------+----+
10 | <- | <empty queue> | <- |
+----+---------------+----+
Trace Algorithms
LCS (Longest Common Sequence)
auto lcs = (new alg_lcs())->setValue(
"ABCBDAB",
"BDCABA"
).run().printLcsTo(std::cout);
Output:
+-----------------------------+
| Longest Common Sequence |
+-----------------------------+
| - - A B C B D A B |
| - 0 0 0 0 0 0 0 0 |
| B 0 0 1 1 1 1 1 1 |
| D 0 0 1 1 1 2 2 2 |
| C 0 0 1 2 2 2 2 2 |
| A 0 1 1 2 2 2 3 3 |
| B 0 1 2 2 3 3 3 4 |
| A 0 1 2 2 3 3 4 4 |
+-----------------------------+
| len: 4 |
+-----------------------------+
| lcs: BCBA |
+-----------------------------+
| lcs: BDAB |
+-----------------------------+
 |
1
hanssx 316 天前
可以，那个栈的感觉用 ASCII 表示，看上去不自然。
|
 |
2
Dynesshely OP |
Select Language