推荐一个算法示踪库

104 天前
 Dynesshely

事情的开始是我在调试一段算法题的代码, 这段代码的算法比较复杂, 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_int to avoid using pint

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                   |
+-----------------------------+
938 次点击
所在节点    分享创造
2 条回复
hanssx
103 天前
可以，那个栈的感觉用 ASCII 表示，看上去不自然。
Dynesshely
99 天前
@hanssx 栈的那个炸掉了, GitHub 网页版渲染的是正常的
总之, 只要是等宽字体就没问题
后续我应该会琢磨琢磨加上自定义输出样式的功能

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/1014272

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX