ARTS-week24

发表于 分类于 本文字数： 2.9k 阅读时长 ≈ 3 分钟

Algorithms

Excel Sheet Column Number 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int titleToNumber(string s) {
        int n = s.size();
        int res = 0;
        for (int i = 0; i < n; i++) {
            int tmp = s[i] - 'A' + 1;
            res = res * 26 + tmp;
        }
        return res;
    }
};

Factorial Trailing Zeroes
思路：要找0的个数，10等于2*5，也就是找出5的个数。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int trailingZeroes(int n) {
        int sum = 0;
        while (n > 0) {
            sum += n / 5;
            n /= 5;
        }
        return sum;
    }
};

使用递归的方式来解决：

1
2
3
4
5
6
class Solution {
public:
    int trailingZeroes(int n) {
        return  n < 5 ? 0 :trailingZeroes(n/5) + n/5;
    }
};

Review

本周阅读英文文章 The Next Level of Data Visualization in Python

Technique

在《内存泄漏了，我该如何定位和处理？》一文中学习到使用bcc工具包中的memleak检测内存泄漏，来跟踪系统或指定进程的内存分配、释放请求，然后定期输出一个未释放内存和相应调用栈的汇总情况(默认5秒)。
OS: Ubuntu18.04

1
2
3
4
sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 4052245BD4284CDD
echo "deb https://repo.iovisor.org/apt/bionic bionic main" | sudo tee /etc/apt/sources.list.d/iovisor.list
sudo apt-get update
sudo apt-get install -y bcc-tools libbcc-examples linux-headers-$(uname -r)

编译并运行如下代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

long long *fibonacci(long long *n0, long long *n1)
{
    //分配1024个长整数空间方便观测内存的变化情况
    long long *v = (long long *) calloc(1024, sizeof(long long));
    *v = *n0 + *n1;
    return v;
}

void *child(void *arg)
{
    long long n0 = 0;
    long long n1 = 1;
    long long *v = NULL;
    int n = 2;
    for (n = 2; n > 0; n++) {
        v = fibonacci(&n0, &n1);
        n0 = n1;
        n1 = *v;
        printf("%dth => %lld\n", n, *v);
        sleep(1);
    }
}

int main(void)
{
    pthread_t tid;
    pthread_create(&tid, NULL, child, NULL);
    pthread_join(tid, NULL);
    printf("main thread exit\n");
    return 0;
}

运行程序后，通过memleak进行分析，可以看出fibonacci分配的内存没有释放。

1
2
3
4
5
6
7
8
9
10
11
12
root@top:~# /usr/share/bcc/tools/memleak -a -p $(pidof app)
Attaching to pid 10612, Ctrl+C to quit.
[13:41:44] Top 10 stacks with outstanding allocations:
    addr = 7fc8c005f220 size = 8192
    addr = 7fc8c0067260 size = 8192
    addr = 7fc8c0063240 size = 8192
    addr = 7fc8c0065250 size = 8192
    addr = 7fc8c0061230 size = 8192
    40960 bytes in 5 allocations from stack
        fibonacci+0x1f [app]
        child+0x56 [app]
        start_thread+0xe4 [libpthread-2.28.so]

对child函数进行修正：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void *child(void *arg)
{
    long long n0 = 0;
    long long n1 = 1;
    long long *v = NULL;
    int n = 2;
    for (n = 2; n > 0; n++) {
        v = fibonacci(&n0, &n1);
        n0 = n1;
        n1 = *v;
        free(v);
        printf("%dth => %lld\n", n, *v);
        sleep(1);
    }
}

再次编译运行代码，并执行memleak工具，可以看到已经修正成功。

1
2
3
4
5
root@top:~# /usr/share/bcc/tools/memleak -a -p $(pidof app)
Attaching to pid 10775, Ctrl+C to quit.
[13:50:04] Top 10 stacks with outstanding allocations:
[13:50:09] Top 10 stacks with outstanding allocations:
[13:50:14] Top 10 stacks with outstanding allocations:

Share

《C++性能优化指南》测量性能-90/10原则

性能优化的基本规则是90/10规则：一个程序花费90%的时间执行其中10%的代码。这只是一条启发性的规则，并非自然法则，但对于我们的思考和计划却具有指导性。这条规则有时也被称为80/20规则，但思想是一样的。直观地说，90/10规则表示某些代码块是会被频繁地执行的热点（hot spot），而其他代码则几乎不会被执行。这些热点就是我们要进行性能优化的对象。

90/10规则的一个结论是，优化程序中的所有例程并没有太大帮助。优化一小部分代码事实上已经足够提供你所想要的性能提升了。识别出10%的热点代码是值得花费时间的，但靠猜想选择优化哪些代码可能只是浪费时间。