ARTS-week35

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

Algorithms

Ugly Number 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isUgly(int num) {
        if ( num == 0 )
            return false;
        if ( num == 1 )
            return true;
        
        while ( num % 2 == 0 ) num /= 2;
        while ( num % 3 == 0 ) num /= 3;
        while ( num % 5 == 0 ) num /= 5;
        
        return num == 1;
    }
};

Ugly Number II
思路: 首先1到N的丑数为 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …, 那么根据题中第二个隐藏的提示: 

1
2
3
(1) 1×2, 2×2, 3×2, 4×2, 5×2, ...
(2) 1×3, 2×3, 3×3, 4×3, 5×3, ...
(3) 1×5, 2×5, 3×5, 4×5, 5×5, ...

每次选取三个列表中最小的那个加入序列即可。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> res(1,1);
        int i=0, j=0, k=0;
        
        while(res.size() < n) {
            int tmp2 = res[i] * 2, tmp3 = res[j] * 3, tmp5 = res[k] * 5;
            int min_val = min(min(tmp2, tmp3), tmp5);
            
            if (min_val == tmp2)
                i++;
            if (min_val == tmp3)
                j++;
            if (min_val == tmp5)
                k++;
            res.push_back(min_val);
        }
        return res.back();
    }
};

Review

本周阅读英文文章
1、Cyber Hackers Salivating at AI Driverless Cars Advent, Safeguards Please

2、What the Hex?

3、How to solve the Knapsack Problem with dynamic programming

Technique

在看《Python高性能（第2版）》时，看到一些优化操作，比如使用推导式来替代显式的for循环。 

1
import timeit
1
2
3
4
5
6
7
8
9
10
11
12
13
def loop():
    res = []
    for i in range(100000):
        res.append(i * i)
    return sum(res)


def comprehension():
    return sum([i * i for i in range(100000)])


def generator():
    return sum(i * i for i in range(100000))
1
2
3
4
5
6
%timeit loop()
    11.6 ms ± 375 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit comprehension()
    7.97 ms ± 303 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit generator()
    8.79 ms ± 1.12 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)

还可结合使用迭代器和filter、map等函数实现高效的循环。 

1
2
3
4
5
def map_comprehension(numbers):
    a = [n * 2 for n in numbers]
    b = [n ** 2 for n in a]
    c = [n ** 0.33 for n in b]
    return max(c)

这种方法对于每个列表推导都将分配一个新列表，增加了内存使用量，使用map来重写前面的函数，这将创建中间生成器，动态地计算值以节省内存。 

1
2
3
4
5
def map_normal(numbers):
    a = map(lambda n: n * 2, numbers)
    b = map(lambda n: n ** 2, a)
    c = map(lambda n: n ** 0.33, b)
    return max(c)

安装memory_profiler后，使用memit来评估内存的使用情况 

1
pip install memory_profiler
1
2
3
4
5
6
7
8
%load_ext memory_profiler
numbers = range(1000000)

%memit map_comprehension(numbers)
    peak memory: 153.59 MiB, increment: 100.75 MiB

%memit map_normal(numbers)
    peak memory: 53.45 MiB, increment: 0.03 MiB

Share

使用pbzip2进行更快的压缩，它会自动检测系统中处理器核心的数量或使用-p选项手动指定处理器核心的数量，在内部使用的压缩算法和bzip2一样，但是它会利用pthreads来同时压缩多个数据块。

安装: 

1
sudo apt install pbzip2

压缩一个文件: 

1
2
3
4
5
6
7
8
$ ls
save.tar
$ pbzip2 save.tar 
$ tree
.
└── save.tar.bz2

0 directories, 1 file

pbzip2并不会创建归档文件，只能对单个文件进行操作，要压缩并归档多个文件或目录，需要使用tar配合pbzip2来实现: 

1
2
3
4
5
6
7
8
9
$ ls
res
$ tar cf save.tar.bz2 --use-compress-prog=pbzip2 res
$ tree
.
├── res
└── save.tar.bz2

1 directory, 1 file

可以利用管道从pbzip2格式的文件完成解压缩和提取：

1
2
3
4
5
6
7
8
9
$ ls
save.tar.bz2
$ pbzip2 -dc save.tar.bz2 | tar x
$ tree
.
├── res
└── save.tar.bz2

1 directory, 1 file