Prefix tree

这两个题都提到了一种树:Trie,也叫做 prefix tree 或者 digital tree,属于所搜树的一种。通常用于字符串的分段搜索,也可以用来做输入提示,即给出一些字母,搜索后续可用的路径。搜索方式属于 DFS,每个节点可以通过带有一些属性,从而实现其他功能,比如不同的action等等。

第三题呢,乍一看跟 Trie 没关系但是,用 Trie 可以大大提高效率。

第一个题是中等,后两个都是困难题。

Read more »

CSAPP 5 程序的优化

优化方式:

  • 程序层面
    • loop unrolling
    • 减少内存renference
    • 减少函数调用
    • 分支优化
  • 内存优化
    • 读写循环优化

现代CPU都有独立的功能组件进行内存的读取和写入,这些组件通常都有自己的缓存。比如Intel i7处理器的读取单元可以缓存48个读取指令,他们通常可以在一个cycle内完成一个操作。

CSAPP 4 处理器架构

CPU Pipeline 的基本原理,通过将任务拆解成不同的阶段,并行执行多个任务,增加 throughput,相应的会提高延迟。不过这样可以提高CPU的时钟频率,降低延迟。

这是比指令集更低一个的一个层次,每一个指令集指令都被分解成多个不同的阶段,由对应的硬件分别执行。分解后,为并行提供了可能。

1
2
3
A B C
A B C
A B C

Pipeline 的复杂度在于错误处理、每个阶段的延迟等等。

Read more »

Calculator I,II,III

问题:

1
2
3
Given a string s which represents an expression, evaluate this expression and return its value. 

The integer division should truncate toward zero.

例子:

1
2
3
4
5
6
7
8
9
10
11
12
Example 1:

Input: s = "3+2*2"
Output: 7
Example 2:

Input: s = " 3/2 "
Output: 1
Example 3:

Input: s = " 3+5 / 2 "
Output: 5
Read more »

CSAPP 3 程序的机器层面表达

这一章主要从汇编程序和机器码的角度看程序。包括call stack, local variable, 以及一些基本的数据结构,比如array, structure, union 等等。

Fun fact: 64位寻址空间是2**48 而不是 2**64。为什么?

IA32机器码与C语言代码不同,可以接触到一些CPU 的计算状态:

  • 程序指针,PC
  • 寄存器文件,regiester file
  • 条件寄存器,
  • 浮点数寄存器
Read more »

Leetcode Jump Game (1-3)

这个系列的三个题虽然名字很像,但是第一和第二个思路类似,属于贪心问题,而第三题其实是搜索问题。

55. Jump Game I

问题

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.

Read more »

CSAPP 1 概览

这本书之前非常简略的阅读过一次,过了这么一年多,重新拿起这本书反倒有了更多理解。可能这就是一本好书的特点把,他随着你的经验增加,提供给你更多的信息。给人的感觉就是,第一次读醍醐灌顶,第二次读,还是醍醐灌顶。。。

作者首先描述了一个 hello 程序是如何从源代码变成可以被执行的机器码,然后通过简单介绍计算机的硬件组成说明了程序是如何被执行的。在这个过程中有几个比较重要的点:

  • 编译器就是一个把一段程序(源代码)翻译成另一种程序(机器码)一个程序(机器码)
  • 计算机的主要操作就是读取指令(数据),运算,输出数据
  • 由于不同数据存储介质的读取速度和容量负相关,缓存机制尤其重要

随后引入了操作系统的三个重要抽象:

Read more »

nSum 问题

2 Sum

方法1:去重、排序、字典、穷举

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
cache = {}

for i in range(len(nums)):
residual = target - nums[i]

if residual in cache:
return [cache[residual], i]

cache[nums[i]] = i

return []

3 Sum

Read more »

CSAPP 2 信息的表达和操作

目前的计算机技术存储信息是二进制的,我们用0和1表达信息。最基本的信息有两种:整数和浮点数。字符串也会被编码成整数表达。从根本上说,我们规定了一些规则(向下文)来解释这些0和1。通过基本的代数法则就可以实现运算了。

为了方便人类阅读,常用的编码进制包括8进制和16进制。

Code

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include "csapp.h"
#include <stdio.h>

void print_int(int x) { printf("int: %d\n", x); }
void print_dbl(double x) { printf("double: %g\n", x); }
void print_int_arr(int a[]) {
int i;
printf("int array: [");
for (i=0;i<=(sizeof(a))/sizeof(a[0]); i++) {
printf("%d, ", a[i]);
}
printf("]\n");
}
void print_default() { puts("unknown argument"); }
#define print(X) _Generic((X), \
int: print_int, \
double: print_dbl, \
int*: print_int_arr, \
default: print_default)(X)

#define problem(x) printf("\n * Problem %s: \n", x)
#define comment(x) printf("%s\n", x)

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, int len) {
int i;
for (i=0; i<len; i++) {
printf(" %.2x", start[i]);
}
printf("\n");
}

void show_int(int x) {
show_bytes((byte_pointer) &x, sizeof(int));
}

void show_float(float x) {
show_bytes((byte_pointer) &x, sizeof(float));
}

void show_pointer(void* x) {
show_bytes((byte_pointer) &x, sizeof(void *));
}

void swap(int *x, int *y) {
*y = *x^*y;
*x = *x^*y; /*Step2*/
*y = *x^*y; /*Step3*/
}

void reverse_array(int a[], int cnt) {
// 1,2,3 -> 3,2,1
int first, last;
for (first=0, last=cnt-1;
first < last;
first++, last--) {
swap(&a[first], &a[last]);
};
}

int main()
{
int x = 1;
float y = 1.0;
show_int(x);
show_float(y);
show_pointer(&x);
printf("Sizeof float is %lu \n", sizeof(float));
printf("Sizeof int is %lu \n", sizeof(int));
// Problem 2.6
problem("2.6");
int a = 3510593;
int b = 3510593.0;
show_int(b); // ? why this shows as same as a?
show_int(a); // 1101011001000101000001
show_float(b); // 1001010010101100100010100000100
// Problem 2.7
const char *s = "abcdef";
show_bytes((byte_pointer)s, strlen(s)); // 61 62 63 64 65 66

/*
a = 110
b = 001

b = a ^ b -> b = 110 ^ 001 = 111
a = a ^ b -> a = 110 ^ 111 = 001
b = a ^ b -> b = 001 ^ 111 = 110
*/
problem("2.10");
int aa = 1;
int bb = 2;
swap(&aa, &bb);
print(aa);
print(bb);

problem("2.11");
comment("Note that a ^ a = 0");
int a2[] = {1, 2, 3};
print(a2);
reverse_array(a2, 3);
print(a2);

problem("2.12");
int x12 = 0x87654321;
printf("%x\n", x12 & 0xFF);
printf("%x\n", ~( x12 ^ 0xFF ));
printf("%x\n", x12 | 0xFF);
printf("%x\n", ~( 0x11 ^ 0xFF ));
}