CUDA

CUDA-线程-warp-延时隐藏

什么是线程

一个线程包括程序代码，程序执行当前点，变量数值和数据结构。线程的执行是串行的。CUDA启动kernel后，启动大量线程，以充分利用数据的并行性。

CPU中的线程生成和调度需要上千的时钟周期，相比GPU只需要很少的时钟周期。更具体说，在一个Warp中的线程的切换几乎是没有开销的，因为线程的上下文直接存储在物理空间中。

线程是如何实现的

线程是啥，在上面说过了。程序的代码存储在主存中，寄存器PC记录程序执行点，寄存器IR存储当前需要执行的指令，寄存器和主存记录变量值和数据结构。

同CPU一样，GPU也提供上下文切换功能，多个线程以轮的方式共享处理单元，通过保存和恢复PC值，寄存器和存储器的内容，可以暂停一个线程的执行，并在稍后正确地恢复这个线程。

GPU的每个SM提供多个执行单元SP，他们共享一个PC和IR（存在与共享的控制单元中），如此以来同一时间，所有的线程执行形同的指令（这个指令就是IR中所存储内容）。

SIMD

SIMD系统中，所有的并行处理单元在任何时候都执行相同的指令。因为是单指令。

CUDA采用的是SPMD，单程序多数据的执行形式，但是在一个SM内部其实是SIMD执行warp中的所有线程，单指令多数据。这涉及到warp的工作原理。

warp与延时隐藏

一个Block中的线程被进一步分为32个为一个warp。由于单指令的定义，任何时刻一个warp中的所有线程只能取一条指令执行（IR中的指令）。在硬件结构中，每个SM有一个取指/分派单元，由这个单元来向warp中的线程提供所要执行的指令。warp中每个线程的数据不同，但执行时间都相同。

一个SM中的使用线程数要多于SP数量，SM中硬件只能执行所有warp的一部分，这样做的目的是提高长延时操作的效率，达到延时隐藏的目的。具体说：当一个warp的一条指令需要等待一个长延时的操作时，这个warp将不会被SP选中执行，这个SP会去执行不需要等待的warp，从而达到隐藏等待时间的目的。所以当由足够多的warp时，硬件可以随时找到可悲执行的warp，如此变充分利用硬件资源。warp的被选择是零开销的。零开销的线程调度。在warp的调度机制下，长延迟的操作被其他warp的指令执行隐藏，即延时隐藏。

这也是为什么GPU不像CPU一样引入大量的缓存和分支预测，为了将更多的芯片面积作为浮点数的计算资源。

Warp中的线程访问Global memory时，做好的访问方式是coalesced access即连续访问，如果不是连续访问，则会由于Cache miss增加移动数据的开销。

LeetCode

LeetCode-Trie-search regular expression

问题描述：

设计一个数据结构，并且实现两个方法：

1
2
void addWord(word)
bool search(word)

其中word中孩子包含26个字母，而需要查找的pattern是26个字母和’.’，’.’可以匹配任何一个字母，如下：

1
2
3
4
5
6
7
addWord("bad")
addWord("dad")

search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

实现：

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

class TrieNode{
public:
    bool is_word;
    TrieNode* next[26];
    TrieNode(bool b=false){
        is_word = b;
        memset(next, NULL, sizeof(next));
    }
};

class WordDictionary {
private:
    TrieNode* root;
/// 后续遍历，销毁Trie
    void clear(TrieNode* root){
        for (int i=0;i<26;i++){
            if (root->next[i] != nullptr)
                clear(root->next[i]);
        }
        delete root;
    }
/// 递归实现匹配
    bool search_(const char* word, TrieNode* root){
        // 遍历word中每一个字符
		for (int i=0; word[i]&&root; i++){
            // 如果当前字符　是26个字母，指针向下移动即可
			if (word[i] != '.'){
				root　=　root->next[word[i]-'a'];
			}
            // 如果当前字符是'.'，
            else{
				TrieNode* node = root;
                // 遍历这个结点next所有域，
				for (int j=0;j<26;j++){
					root = node->next[j];
					if (search_( word+i+1, root)){
						return true;
					}
				}
			}
		}
		return root && root->is_word;
	}
    
public:
    WordDictionary() {
        root = new TrieNode();
    }
    ~WordDictionary(){
        clear(root);
    }
    
    void addWord(string word) {
        TrieNode* tmp = root;
        for (int i=0;i<word.size();i++){
            if (tmp->next[word[i]-'a'] == nullptr)
                tmp->next[word[i]-'a'] = new TrieNode();
            tmp = tmp->next[word[i]-'a'];
        }
        tmp->is_word = true;
    }
    
/// 匹配入口
    bool search(string word){
		return search_(word.c_str() ,root);
	}
};

体会递归函数：search_()。

LeetCode

LeetCode-Trie

Trie是用来存储和查找大量string的带有结点和边的树型结构。对于字母string来讲，每个结点最多有26个子节点，如此构成一棵多叉树。这棵树的每一条从root的下一个结点到任意结点都是一个string。

Trie的结点可以如下定义：

1
2
3
4
5
6
7
8
9
10
class TrieNode {
public:
    TrieNode* next[26];
    bool is_word;

    TrieNode(bool b = false){
        is_word = b;
        memset(next, 0, sizeof(next));
    }
};

注意：

  1. memset(next, 0, sizeof(next))表示在next地址，从头开始将sizeof(next)个字节设置为0（0在此其实是nullptr，表示初始化不指向任何地址。）

  2. memset(next, 0, sizeof(next))等价于：

    1
    2
    3
    for(int i=0;i<26;i++){
        next[i] = nullptr;
    }

    手动将所有next指针域置为空。

  3. 所有next结点的is_word默认为false。

  4. 指针指向一个结点的首地址，所以一个结点的成员不同，首地址不同。

每个结点有26个子节点和一个bool型的成员。bool成员表示从root到当前结点的上一个结点形成的路径，这条路径表示的string是否存在于Trie中的。当为True时，这条路径表示的string存在于Trie，False则为不存在。看下图。

有了结点，可以构造Trie。开辟root空间即可，之后便可以向其中保存指定string，在其中搜索指定string。

1
2
3
4
5
/// Trie START
class Trie{
public:
	Trie(){ root = new TrieNode(); }
	~Trie(){ clear(root); }

初始化一个Trie，构造一个Trie结点作为root。

Trie的成员方法：

向Trie中添加string。只要遍历整个string，若没有当前字母，则新建一个结点；否则，自自由指针向下移动。

1
2
3
4
5
6
7
8
9
10
11
void insert(string word) {
       // tmp为自由指针，
       TrieNode* tmp = root;
       for(int i = 0; i < word.size(); i++){
           if(tmp->next[word[i] - 'a'] == nullptr)
               tmp->next[word[i] - 'a'] = new TrieNode();
           tmp = tmp->next[word[i]-'a'];
       }
	// 将单词结尾设为true，表示这条路径是一个单词
       tmp->is_word = true;
   }

注意：

  1. tmp->next[word[i] - 'a'] = new TrieNode();智力只是开辟了空间，并没有向其中写入当前的字母，这里是使用26个不同 的位置来唯一标识每一个字母。如果字母‘b’出现，那么next的第二个位置（next[word[i] - ‘a’]）将指向一个新的TrieNode结点，当然也可以使用其他TrieNode的实现方式，比如将26个字符作为key，将其子节点设为value，这种字典类型。下图是个例假设只有abc三个字符，将string bac插入Trie的过程：

    将“bac”插入Trie

  2. is_word默认是false，但一个单词写入trie结束后，手动将最后一个字母的下一个结点的is_word置为true。

在trie中搜索一个string：

1
2
3
4
5
6
7
8
9
10
bool search(string word) {
       // tmp指向单词的最后一个字母结点
       TrieNode* tmp = find_string(word);
	// 如果tmp（这个单词的最后一个字母）不是空且tmp的bool为true，
	// 表示由完整的这个单词
       if(tmp != nullptr && (tmp->is_word))
           return true;
       else
           return false;
   }

在trie中搜索一个前缀。与search方法唯一的区别是，不论tmp的is_word是否为true，即prefix是否是一个完整的单词，都就算找到。

1
2
3
4
5
6
7
bool startWith(string prifix) {
       TrieNode* tmp = find_string(prifix);
       if(tmp != nullptr)
           return true;
       else
           return false;
   }

从Trie 中删除一个已经存在的word。只需要将这个word末尾结点的is_word置位false即可。

1
2
3
4
5
6
7
8
9
void remove(string word){
	if (search(word)){
		TrieNode* tmp = root;
		for (int i=0;i<word.size();i++){
			tmp = tmp->next[word[i]-'a'];
		}
		tmp->is_word = false;
	}
}

Trie对象的头：

1
2
private:
	TrieNode* root;

找到word的最后一个字母的结点:

1
2
3
4
5
6
7
8
9
10
11
12
TrieNode* find_string(string word){
       TrieNode* tmp = root;
       for(int i = 0; i < word.size(); i++){
           if(tmp->next[word[i] - 'a'] != nullptr)
               tmp = tmp -> next[word[i] - 'a'];
           else {
               tmp = nullptr;
               break;
           }
       }
       return tmp;
   }

后序遍历 释放Trie

1
2
3
4
5
6
7
8
9
10
	void clear(TrieNode *root){
        for(int i = 0; i < 26; i++){
            if(root->next[i] != nullptr){
                clear(root->next[i]);
            }
        }
        delete root;
    }
};
/// Trie END

敲黑板：TrieNode结点的定义与链表结点定义，树结点定义相同。都会有若干自身类型的指针，且这些指针初始化为nullptr，表示指针不保存任何地址。当其中某个指针要指向一个新的结点时：tmp->next[word[i] - 'a'] = new TrieNode()，先开辟一个结点空间，后将其地址存入指针。如此，由结点构成的链就形成了。

LeetCode

LeetCode-BST 找前驱与后继结点

描述：
加入构造了一BST： 

1
2
3
4
5
     4
   /   \
  2     6
 / \    /\
1   3  5  7

现在要找到每个结点的前驱和后继结点。

思路：

可以将树的所有结点有序存储，后对于这个有序的数组操作。这里给出递归的思路。

  1. 对于前驱结点。

    第一步，首先搜索目标结点，即谁的前驱。这个过程是左->中->右中序遍历，过程中记录target结点属于第几大的结点，将结果保存到count中。

    第二步。重新左->中->右中序遍历，找到第count-1大的结点，即第一个比target小的结点。

  2. 对于后继结点。

    第一步，首先搜索目标结点，即谁的后驱。这个过程是左->中->右中序遍历，过程中记录target结点属于第几大的结点，将结果保存到count中。

    第二步。重新左->中->右中序遍历，找到第count+1大的结点，即第一个比target大的结点。

实现过程：

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
class Sol_successor_predecessor{
public:
/// 前驱结点的入口函数
	void predecessor(TreeNode* root, const TreeNode* const target, int count){
        // 遍历的count_
		inOrder(root, target, count);
        // 搜索第count_-1的结点
		predecessor_(root, target);
		if (res_)
			cout<<"predecessor node: "<<res_->val<<endl;
		else
			cout<<"predecessor node: nullptr"<<endl;
        // 重置
		count_=0;
		res_=nullptr;
		
	}
/// 后继结点的入口函数
	void successor(TreeNode* root, const TreeNode* const target, int count){
        // 遍历的count_
		inOrder(root, target, count);
        // 搜索第count_+1的结点
		successor_(root, target);
		if (res_)
			cout<<"successor node: "<<res_->val<<endl;
		else
			cout<<"successor node: nullptr"<<endl;
        // 重置
		count_=0;
		res_=nullptr;
	}


private:
	int count_ = 0;
	TreeNode* res_ = nullptr;

/// find the predecessor when count_ decreased to 1
	void predecessor_(TreeNode* root, const TreeNode* const target){
		if (root!=nullptr ){
            predecessor_(root->left, target);  
			count_--; 
            // 直到count_ 减掉count_-1个数后，找到前驱结点
			if (count_ == 1){
				res_ = root;
				return;
			}
            predecessor_(root->right, target);
        }
	}
/// find the successor when count_ decreased to -1
	void successor_(TreeNode* root, const TreeNode* const target){
		if (root!=nullptr ){
            successor_(root->left, target);  
			count_--; 
            // 直到count_ 减掉count_+1个数后，找到后继结点
			if ( count_ == -1){
				res_ = root;
				return;
			}
            successor_(root->right, target);
        }
	}

/// traverse to find the target node, and keep counting
	void inOrder(TreeNode* root, const TreeNode* const target, int& count){
        if (root!=NULL){
            inOrder(root->left, target, count);  
			count++;
			if (root->val == target->val){
                // 记录target结点是第几大的结点
				count_ = count;
				return;
			}  
            inOrder(root->right, target, count);
        }
    }
};

过程如注释。测试：

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
/// 后续遍历 用于销毁Tree
void destroyTree(TreeNode* root){
	if (root){
		destroyTree(root->left);
		destroyTree(root->right);
		delete root;
		root = nullptr;
		return;
	}
}

int main(int argc, char** argv){
	TreeNode* root = new TreeNode(4);
	TreeNode* node1 = new TreeNode(2);
	TreeNode* node2 = new TreeNode(6);
	TreeNode* node3 = new TreeNode(1);
	TreeNode* node4 = new TreeNode(3);
	TreeNode* node5 = new TreeNode(5);
	TreeNode* node6 = new TreeNode(7);

/// create a tree
	root->left = node1;
	root->right = node2;

	node1->left = node3;
	node1->right = node4;

	node2->left = node5;
	node2->right = node6;

/// create a vector
	vector<TreeNode*> treeVec = {node3,node1,node4,root,node5, 
								node2, node6};
	Sol_successor_predecessor sol;
	for (auto item: treeVec){
		sol.predecessor(root, item, 0);
		sol.successor(root, item, 0);
	}
/// 销毁
    destroyTree(root);
    return 0;
}

输出结果：

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
target node: 1
predecessor node: nullptr
successor node: 2

target node: 2
predecessor node: 1
successor node: 3

target node: 3
predecessor node: 2
successor node: 4

target node: 4
predecessor node: 3
successor node: 5

target node: 5
predecessor node: 4
successor node: 6

target node: 6
predecessor node: 5
successor node: 7

target node: 7
predecessor node: 6
successor node: nullptr

结果正确。

CUDA

CUDA-并行Radix Sort

啥是Radix Sorting

Radix Sorting CPU 版本

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
#define NUM_ELEM 100
void cpu_sort(int32_t* const data, const int32_t num_elements) {
	static int32_t cpu_tmp_0[NUM_ELEM];
	static int32_t cpu_tmp_1[NUM_ELEM];
    // for every bits of an element
	for (int32_t bit=0; bit<32; bit++) {
		int32_t base_cnt_0 = 0;
		int32_t base_cnt_1 = 0;
        // for every elements
		for (int32_t i=0; i<num_elements; i++){
			const int32_t d = data[i];
			const int32_t bit_mask = (1 << bit);
			if ( (d & bit_mask) > 0 ) {
				cpu_tmp_1[base_cnt_1] = d;
				base_cnt_1++;
			}
			else{
				cpu_tmp_0[base_cnt_0] = d;
				base_cnt_0++;
			}
		}
		// Copy data back to source - first the ZERO list
		for (int32_t i=0; i<base_cnt_0; i++){
			data[i] = cpu_tmp_0[i];
		}
		// Copy data back to source - then the ONE list
		for (int32_t i=0; i<base_cnt_1; i++){
			data[base_cnt_0+i] = cpu_tmp_1[i];
		}
	}
}

上述过程没有办法并行，但是可以将Radix排序作为基本算子，将待处理的数组分成若干段，段与段之间并行执行Radix排序，之后调用Merge，将所有段（每一段都是有序的）并行归于成一段。这就是基本平行排序思路。

有了这个并行思路，对于排序算子，就可以使用任何可行的排序方法了。

先实现CPU的对多个有序数组的Merge操作：

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
// 合并多个有序的子序列
void merge_arrays(const int* src_array, 
					int* const dest_array,
					const int num_lists, 
					const int num_elements){

	const int num_element_per_list = (num_elements/num_lists);

	int list_indexes[5]; // 分成5段
	for (int l=0; l<num_lists; l++){
		list_indexes[l] = 0;
	}

	for (int i=0; i<num_elements; i++){
		dest_array[i] = find_min(src_array, 
								list_indexes,
								num_lists,
								num_element_per_list);
	}
	return;
}

// 遍历所有段（子序列），找到当前所有段段首的最小值，写入目标数组的对应位置。
int find_min(const int* src_array,
			int* const list_indexes,
			const int num_lists,
			const int num_elements_per_list){
	
	int min_val = INT_MAX;
	int min_idx = 0;
	// Iterate over each of the lists
	for (int i=0; i<num_lists; i++){
	// If the current list has already been emptied
	// then ignore it
		if (list_indexes[i] < num_elements_per_list){
			const int src_idx = list_indexes[i] + num_elements_per_list * i;
			const int data = src_array[src_idx];
			if (data <= min_val){
				min_val = data;
				min_idx = i;
			}
		}
	}
	list_indexes[min_idx]++;
	return min_val;
}

int main(){
    // 共有15个元素，分成5段，每一段都有序。
    vector<int> tmp = {	2,4,7,
						1,90,91,
						3,5,7,
						10,11,13,
						8,9,12};
}

Radix Sorting GPU 版本

这个在Thrust库中有相应实现。

敲黑板：每一个数与其二进制对应，Radix排序方法对二进制做判断，而在源数上做操作。

LeetCode

LeetCode-判断链表是否相交

描述：两个链表，均没有环，判断这两个链表是否相交。

关键要知道：链表中一个结点的唯一标识是它的地址。若两个结点的地址相同，表示这是同一个结点。

给出结点的定义：

1
2
3
4
5
6
7
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

方法一 遍历

对于相交的情况像字母“Y”，即只要有一个结点开始相同，那么之后的结点都相同。这种情况下，只要有相交，那么两个链表的最后一个结点一定相同。所以，分别遍历两个链表，记录尾结点，判断为节点是否是同一个结点。

时间复杂度是O(M+N)，空间复杂度是O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool crossLists1(ListNode* head1, ListNode* head2){
    ListNode* dhead1 = new ListNode(-1, head1);
    ListNode* dhead2 = new ListNode(-1, head2);
    ListNode* cur1 = dhead1;
    ListNode* cur2 = dhead2;

    while (cur1->next){
        cur1 = cur1->next;
    }
    while (cur2->next){
        cur2 = cur2->next;
    }

    return cur1==cur2;
}

注意，由于链表结点的定义，指出，一个结点只有一个next指针域，所以不会出现像字母“X”的相交情况。

方法二 连接两个链表

可以将链表1的尾接到链表2的头，此时遍历链表1，如果遍历指针走到了链表的结尾，即nullptr，表示新的链表中没有环，原链表不相交；若有环，则原链表相交。

时间复杂度是O(M+N)，空间复杂度是O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool crossLists2(ListNode* head1, ListNode* head2){
    if (!head1 || !head2 ) return true;
    ListNode* dhead = new ListNode(-1, head1);
    
    ListNode* needle = dhead;
    // move needle to the end of head1
    while (needle->next){
        needle = needle->next;
    }
    // link the tail of head1 to the head of head2;
    needle->next = head2;

    // check if there exists a loop
    return hasCycle(head1);
}

其中hasCycle():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool hasCycle(ListNode* head){
    if (!head) return false;
    ListNode* fast = head;
    ListNode* slow = head;

    while(fast && slow){
        fast = fast->next;
        slow = slow->next;

        if (fast) fast = fast->next;
        // 先判断移动后的fast是否非空
        if (fast && fast==slow)
            return true;
    }
    return false;
}

方法三 使用查找表

将head1的结点放入set，然后对于head2中每个结点，在set中find()，如果能找到，则表示由公共的结点，交叉；否则不交叉。

时间复杂度：O(max(M,N)), 空间复杂度：O(M)。需要M的空间创造查找表set。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool crossLists3(ListNode* head1, ListNode* head2){
    std::set<ListNode*> st;
    ListNode* cur = head1;
    // 将head1的结点放入set
    while(cur){
        st.insert(cur);
        cur=cur->next;
    }
    cur = head2;
    // 从head2中，对每个结点在set中find，
    while(cur){
        if (st.find(cur)!=st.end())
            return true;
        cur=cur->next;
    }
    return false;
}

现在如果进一步要求出相交的结点是哪个，如何求？

方法一不适用，方法二，可以修改为带环的链表求环的入口，看笔记LeetCode-链表相关的#142。

方法三，只需要将查找表改为顺序存储，即可，如此找到的公共结点就是第一个在查找表中找到的结点。

强调：链表中一个结点的唯一标识是它的地址。当打印一个ListNode* head时，打印的是head中的内容，即一个结点对象的地址。

C++

cpp-静态内存-栈内存-动态内存

一个cpp程序会使用到的内存类型有：

  1. 静态内存：用来保存局部static变量，类中static变量，任何函数外的全局变量。
  2. 栈内存（stack）：保存定义在函数内的非static变量。
  3. 动态内存（heap）：存储动态分配的对象。但是使用完后，调用着必须显式地将空间释放。通常使用new和delete关键字。

动态内存使用时，new在动态内存中分配空间并且返回一个指向该空间的指针（两件事）。delete时，接受一个动态对象的指针，销毁该指针所指向的对象，并释放空间。

但是在正确的时间释放空间有时是很困难的，为了可以安全的使用动态内存，标准库提供了智能指针：shared_ptr和unique_ptr。

多个shared_ptr能共享一个对象；而一个unique_ptr只能独享一个对象。

待归类

比特币-以太坊-区块链

本笔记内容来自卓克讲座及讨论内容。

比特币的目

比特币的目的是生成一个任何人都不能更改的账本，这个账本在分布式系统中的每一个结点都保存一份，并且同步更新。账本可以是一条交易记录，比如：我向李三转账100个比特币。这个动作，在相应的软件上会做3件事：

  1. 将“我向李三转账100个比特币”作为原始信息，对其做一次SHA-256运算，得到的结果是一个原哈希值。
  2. 用我自己的私钥给上一个结果（原哈希值）加密，得到加密后的密哈希。
  3. 将原始信息，公钥（我自己的私钥对应的公钥），密哈希，3项内容广播到网络中。

之后图中三个矩形框的内容就被广播到网络中。

对任何内容进行SHA-256运算都能生成唯一的256bit的二进制数，没有办法从这个二进制数推出原始信息，所以SHA-256函数特别用于对比两条信息是否相同。比如我完成向李三转账100个比特币之后，别人就可以对纸条交易信息用SHA-256函数进行验证，如果结果与我给出的原哈希值相同，则表示这条信息是没哟被篡改过的。

使用公钥私钥的方式是非对称加密，那么对称加密有什么不好呢。

对称加密

加入我要向李三发一条信息：315，对他加密，方法是每一位加2，得到加密后的信息537,537在网络中传播，到达李三后，用我俩约定的加密解密方式只需要每一位减2，得到原始信息315。此过程中的“2”称为对称钥匙。

对称钥匙的缺点是，我不论是以什么样的方式告知李三，钥匙最少需要一次的传递。这个传递过程可以被监听。所以有了非对称加密技术。

非对称加密

1978年新的加密技术出现了。加密解密使用不同的两把钥匙，使用其中任何一个加密，那么另一个就可用来解密。非对称加密技术是通过一种很巧妙的且不可逆的数学运算的，成对存在。两把钥匙中，一把永远保留在自己手中，且只有自己知道，这个叫私钥，另一个公开给他人的称为公钥。

公钥私钥-加密&签名

私钥公钥有两个功能：

  1. 加密信息。当他人要给我发送加密消息，只要查询我的公钥，用公钥加密后发给我，我收到后送我的私钥解密，就可以获取原消息。整个过程没有任何钥匙的传递。所以这种方式由很强的安全性。
  2. 签名。此时对钥匙的使用是反着来的。当我要想他人证明这条消息确实是我发出的，我需要先使用私钥加密，后将加密后的信息广播出去，他人使用我的公钥解开就可以了。若解开了，则证明该信息是由我发出。

回顾一下，SHA-256函数的作用是为了确认原文是否被修改过，公钥私钥是用来确认交易信息签名的。到此，这个交易的加密信息和公钥就被传播出去了。

那交易记录为什么要被加密呢？如果没有加密，那么同一条消息可以由任何人写出，如何判断对比哪一个才是我的呢，由我授权的呢。所以需要私钥加密，后别人用公钥解密判断是否是我授权的。经过这一过程，这个交易（区块）就有可能成为链上的新区块。注意是“有可能成为”。

区块

矿工验证若干条交易信息，按照一定格式打包后，得到的称作区块。一个区块包括头部和交易部分。

矿工做验证

交易的加密信息和公钥就被传播出去了之后，需要验证，这些人使用客户端软件验证，他们被称为矿工。当矿工从网络中获得我广播的3条信息后，矿工根据其做下面两件事：

如果原哈希==解哈希，表示这个区块的信息没有被篡改，是经过我签名的。到此，这个交易就有可能成为区块链上的新区块。

矿工验证的过程是竞争让自己打包的交易信息成为区块挂在区块链的结尾。为什么这里需要竞争？【物理位置不同，搜索到的交易信息也不同】全世界的矿工即使都打包好了自己的区块，相互区块之间的差别是很大的，那哪一个才有资格称为幸运儿呢，这需要一项额外的（无意义的）工作来证明：工作量证明。

这里猜测一下，添加到链上的区块不是关注其原始交易是什么，而是看这个区块的前若干位是否都是零。其实互不相干的多条交易信息相对于同一个时间是无序的，所以两条不同交易信息谁在前谁在后，对于区块链没有关系，反正所有历史信息都会被记录。所以添加区块的资格就需要工作量证明。

添加新区块的资格

工作量证明：将打包的区块看做一个字符串，在其末尾添加一个随机数，最后对这个字符串执行SHA-256操作，已经知道SHA-256操作的结果是一个长度为256的二进制数。谁先计算出的结果中的前72位都是零，那么谁就有资格将自己的区块添加到链尾。成功提交这个区块的人，系统会奖励其若干个比特币，这个奖励是逐渐减半的，等差数列计算一下就知道，总的比特币数量为2100万个。

最长链，主链

比特币协议中只承认最长链，所以如果在某个结点出现了分支，那么哪一个分支最先出现下一个区块，表示这个支链就会更长，它将作为从此之后的主链，而另一个分支的交易会作为无效，比特币退回。

有了这个规则，即使一个区块被人篡改，对主链也不会有影响。因为所有算力都在主链上，那个被篡改的支链，只能确保自己的推进速度超过主链的推进速度，才有可能在未来某个时间成为新的主链，但显然一个人的算力对抗其他所有算力，是赢不了的。所以，篡改无效。

当前区块包含了全部交易历史信息的特

一个区块包含两部分，头部和交易信息，其中头部包括上一个区块的信息，具体是上一个区块的SHA-256函数值。如此递归，容易知道，链中的每一个区块都含有其上一个区块的信息。所以说任何一个区块都含有这个区块之前整条链的所有信息。

比特币有很多问题

根据上述描述，可以发现比特币的问题：

  1. 竞争获得添加新块的资格是靠算力裁决（工作量证明）的，而这个计算简单且没有实际意义的，损耗硬件算力和电能。
  2. 这个网络的交易频率太低，只有7笔交易每秒钟，VISA可以每秒钟处理千笔交易。比特币作为交易的属性太不明显。
  3. 区块链是在一个分布式系统中构建的，但是整个链都需要完整复制到每一个结点，并保持同步，所以存储，带宽成了大问题。其实这个系统的性能是由系统中性能最差的结点决定。
  4. 比特币意义不大，只是因为它是第一个出现的相关概念，外加大众的炒币，使其价格高，却极不稳定。

区块链诞生

行业黑话，给交易打包，叫块，将块连接成链。两者结合实现支付和账本功能，叫区块链。（这个区块链上流通的货币是比特币）

以太坊

对比特币改进的虚拟币由很多种，其中技术改进最大的是以太坊。以太坊中实现了许多比特币中没有的特性和功能。

以太坊vs比特币

主要有两点不同：

  1. 以太坊有两种账户：普通账户和合约账户。普通账户可以主动发起交易；合约账户不能主动发起交易，但是可以回应普通账户执行交易。比特币系统中保存的是不可更改的交易历史，而以太坊中除了不可更改的历史交易，还有一些不可更改的执行程序。
  2. 比特币是采用工作量证明来裁决，而以太坊是采用权益证明裁决。就是谁拥有的虚拟币多，谁打包成块后提交的成功率高。

以太坊对应的区块链被称为“智能合约”，不可更改，分布式存储，等待执行。其实并不智能，智能是可以自动选择最优方案的。

DAO案件

以太坊对应的区块链上哪个时候有漏洞，如果要打补丁，会重新产生一条新的主链，这是个大改动，而且碰到漏洞的概率很小。所以没有及时打补丁。直到黑客动手，偷走了5%的以太坊，价值5000万美元。又因为区块链是一个分布式系统（去中心系统，像最常接触的操作系统，都是中心化的，有漏洞，打补丁后重新发布新的版本就好），偷盗行为不能被禁止。幸好代码中有一条“28天后才能提现”的规定，最终90%的人同意将被盗后的主链设为无效，但10%的人由于在事件发生后合法地赚到了钱，而反对。所以之后以太坊被分为ETH和ETC两种，两个主链。

没有绝对安全的系统。

区块链的缺点

  1. 虽是分布式，但算力没有提升。一般的分布式系统是为了提高计算效率，而区块链的分布式系统，并没有增加计算效率。
  2. 存储低效。上万个结点要长时间保持同步，每个结点存储完整的区块链。

所以从计算机科学的角度讲，区块链设计精妙，但效率地，浪费资源的缺点是注定的。

区块链的应用落地太困难

一个应用是支付宝的“相互宝”，使用了区块链的技术，但民众真正使用它更多的是因为对支付宝的品牌信任。想象一下，如果不是支付宝，而是一个不知名的公司，大众还会考虑吗。

另外的应用是虚拟币交易所。

从无到有的创新在区块链上太难了。其中一个原因就是，创造区块链历史的都是一些挑战既有秩序的人，而这个级别的创新在中国不太可能出现。

中国的创新是对现有技术的延伸

回顾中国的互联网发展，正是通过中国的工程师在已有的技术上延伸而发展来的。一旦区块链技术在一个应用领域落地，在中国普及起来将会是很快的。

LeetCode

LeetCode-优先队列相关

STL中priority—queue的定义，需要给出元素类型，容器类型，比较函数。其中比较函数可以由lambda函数，或struct定义。最常使用的操作有push(), top(), pop()。

347 Top-K freqent elements

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
vector<int> topKFrequent(vector<int>& nums, int k){
	// 1) build a map:
	unordered_map<int, int>mp;
	for(auto item: nums){
		mp[item]++;
	}

	// 2) build a heap: make_pair<frequent, value>
	auto Comp = [](pair<int, int>& a, pair<int, int>& b) {
		return a.first < b.first;
	};
	priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(Comp)> pq(Comp);
	for(auto itr=mp.begin(); itr!=mp.end(); itr++){
		pq.push(make_pair(itr->second, itr->first));
	}

	// 3) push top k of heap to 'res'
	vector<int> res;
	for(int i=0;i<k;i++){
		res.push_back(pq.top().second);
		pq.pop();
	}

	return res;
}

如测试用例：{1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,4,4,4,5,6,7,8} 返回频数最大的前3个元素2,3,1。

692 Top-K freqent words

同上一个问题

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
vector<string> topKFrequent(vector<string>& words, int k) {
    // 1) build a map
    unordered_map<string, int> mp;
    for(auto item: words)
        mp[item]++;

    //2) build a Max heap
    // 2.1) use lambda func and pass lambda to 'pq'
    auto comp = [](pair<int, string>& a, pair<int, string>& b){
        return a.first<b.first || (a.first==b.first && a.second>b.second);
    };
    
    priority_queue<pair<int, string>, vector<pair<int, string>>, decltype(comp)> pq(comp);

    // 2.2) declare container && the element type
    // priority_queue<pair<int,string>, vector<pair<int, string>>, Comp> pq;

    for(auto itr=mp.begin(); itr!=mp.end(); itr++)
        pq.push(make_pair(itr->second, itr->first));

    // 3) push top k words to 'res'
    vector<string> res;
    for(int i=0;i<mp.size();i++){
        cout<<pq.top().second<<": "<<pq.top().first<<" ";
        res.push_back(pq.top().second);
        pq.pop();
    }
    cout<<endl;
    return res;
}
struct Comp{
    bool operator()(pair<int, string>& a, pair<int, string>& b)
        return a.first<b.first || (a.first==b.first && a.second>b.second);
}
Caffe

caffe-工具箱

caffe使用工具

caffe 编译后生成动态链接库 libcaffe.so。使用caffe时，在main.cpp中调用相应API，编译时包含对应的头文件，链接时加入 libcaffe.so。如此才是一个完整的caffe应用。

在tools/中就是一些调用libcaffe.so的工具源码。

前面提到过，caffe.bin工具由4个功能：

1
2
3
4
./caffe.bin train           #train or finetune a model
./caffe.bin test            #score a model
./caffe.bin device_query    #show GPU diagnostic information
./caffe.bin time            #benchmark model execution time

从tools/caffe.cpp中看看是如何实现传递不同的参数，执行不同的功能。

首先定义一个caffe命令注册表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef int (*BrewFunction)();
typedef std::map<caffe::string, BrewFunction> BrewMap;
BrewMap g_brew_map;

#define RegisterBrewFunction(func) \
namespace { \
class __Registerer_##func { \
    public: /* NOLINT */ \
        __Registerer_##func() { \
    g_brew_map[#func] = &func; \
    } \
}; \
__Registerer_##func g_registerer_##func; \
}

device_query命令：

1
2
3
4
5
6
7
8
9
10
11
int device_query() {
    LOG(INFO) << "Querying GPUs " << FLAGS_gpu;
    vector<int> gpus;
    get_gpus(&gpus);  // TODO 
    for (int i = 0; i < gpus.size(); ++i) {
        caffe::Caffe::SetDevice(gpus[i]);
        caffe::Caffe::DeviceQuery();
    }
    return 0;
}
RegisterBrewFunction(device_query);

train命令

1
2
int train() {...}
RegisterBrewFunction(train);

test命令

1
2
int test() {...}
RegisterBrewFunction(test);

time命令

1
2
int time() {...}
RegisterBrewFunction(time);

上述将4条命令加入注册表。

从注册表中取对应的命令：

1
2
3
4
5
static BrewFunction GetBrewFunction(const caffe::string& name) {
    if (g_brew_map.count(name)) {
        return g_brew_map[name];
    } else {...}
}

从main函数中调用：

1
2
3
4
5
6
7
8
9
10
11
12
int main(int argc, char** argv) {
    ...
    gflags::SetUsageMessage("command line brew\n"
        "usage: caffe <command> <args>\n\n"
        "commands:\n"
        "  train           train or finetune a model\n"
        "  test            score a model\n"
        "  device_query    show GPU diagnostic information\n"
        "  time            benchmark model execution time");
    ...
    return GetBrewFunction(caffe::string(argv[1]))();
}

如上实现了在caffe.bin工具中执行不同的命令。

还有其他工具：特征提取，图像格式转换，计算图像均值，等等。

编写自己的工具

编写自己的工具帮助理解 caffe 框架和操作。

caffe中的GPU实现

其实caffe不需要手动编写CUDA程序，而是直接使用cuBLAS实现数学计算，相当于CPU端的OpenBLAS和MKL计算库。

上述是从数学计算角度，而对于DL中常见算子，如卷积，下采样等，在cuDNN中都已实现。