C/C++ program memory layout

发表于 | 更新于 | 分类于

C语言程序在内存中的组成部分

C语言程序在内存中的构成如下所示：
c_program_in_memory
即一个C语言程序在内存中由text segment, data segment，heap和stack组成。在程序执行的过程中，exec从程序文件中读取代码段和初始化数据段相关内容，然后exec负责将未初始化数据(bss)段中的内容初始化为0。
所有的static和全局变量存放在数据段，所有的自动变量和临时变量都存在stack中，动态变量存放在heap中。
所有的函数参数存放在stack中，每一个函数都有一个不同的stack frames。
在栈的最上面，存放的是命令行参数和环境变量，这个空间是不可扩展的，因为它在进程地址空间的最上面所以不能向上扩展，而它下面的所有栈帧是不可移动的，所以也不能向下扩展。

Text segment （代码段）

Text Segment，CPU执行的机器指令部分。通常，正文段是可共享的，所以即使是频繁执行的程序在存储中也只有一个副本。正文段通常是只读的，防止程序由于意外而修改指令。代码段也可能会放在heap或者stack下面，当它们溢出时就会覆盖代码段。

Initialized Data Segment

Initialized data segment（初始化段），通常简称数据段，数据段包含程序员初始化的global变量和static变量。
这个段也可以被划分成初始只读区域和初始读写区域，例如：

1
2
3
4
5
6
7
8
9
char s[] = "hello world";   //s在初始化数据段，存放的是"hello world"
int debug = 1;      //全局初始化变量
static int i = 10;  //全局静态变量

const char *str = "hello world";    //字符串常量存放在字符串常量区，str是全局指向常量的指针，存放的是字符串常量"hello world"在内存中的地址。
int main()
{
    statit int si;  //局部static 变量。
}

Uninitialized Data Segment

Uninitizlized data segment（未初始化段），通常被称为bss段，这个名称来自于早期汇编程序的一个操作符，意思是"block started by symbol"。在程序开始执行前，内核将这个段中的数据初始化0或者空指针。
未初始化段从数据段的结束开始，包含所有初始化为0的global和static变量以及在源代码中没有显式初始化的global和static变量。

1
2
static int i;   //static 变量
int j;      //global变量

Heap （堆）

堆是动态分配的内存，从低地址往高地址增长，存放的是用户手动分配的内存，即malloc()和calloc()等函数生成的数据存放地址。位于bss段和栈之间。

Stack （栈）

栈也是动态分配的内存，从高地址向低地址增长，栈中存放的是临时数据：自动变量，函数参数，返回地址，局部变量等等。栈可以用来保存函数调用的现场，在递归调用中，如果调用次数太多，就可能会有stack overflow问题。

size

可以使用size(1)命令查看可执行文件的text segmen, initialized data segment(data segment)和uninitialized data segment(bss)段的大小。

参考文献

1.https://www.geeksforgeeks.org/memory-layout-of-c-program/
2.https://www.tenouk.com/ModuleZ.html
3.https://en.wikipedia.org/wiki/Executable_and_Linkable_Format
4.https://en.wikipedia.org/wiki/Data_segment
5.https://www.tutorialspoint.com/memory-layout-of-c-programs

AI confereneces papers download site

发表于 | 更新于 | 分类于

ICLR

下载

2019:
https://iclr.cc/Conferences/2019/Schedule?type=Poster
2018:
https://openreview.net/group?id=ICLR.cc/2018/Conference#accepted-poster-papers
https://iclr.cc/Conferences/2018/Schedule?type=Poster
2017:
https://openreview.net/group?id=ICLR.cc/2017/conference
2016:
https://iclr.cc/archive/www/doku.php%3Fid=iclr2016:accepted-main.html
2015:
https://iclr.cc/archive/www/doku.php%3Fid=iclr2015:accepted-main.html
2014:
https://iclr.cc/archive/2014/conference-proceedings/

查询（不能下载）

https://dblp.org/db/conf/iclr/iclr2019
https://dblp.org/db/conf/iclr/iclr2018
https://dblp.org/db/conf/iclr/iclr2017

NIPS

2019:
https://nips.cc/Conferences/2019/AcceptedPapersInitial
1987-2018:
http://papers.nips.cc/

AAMAS

http://aamas2019.encs.concordia.ca/accp.html
http://celweb.vuse.vanderbilt.edu/aamas18/acceptedPapers/
http://www.aamas2017.org/accepted-papers-main-track_aamas2017.php

algorithm-sort

发表于 | 更新于 | 分类于

排序分类

内部排序

基于比较的排序

交换排序

  • 冒泡排序
  • 快速排序

插入排序

  • 简单插入排序
  • 希尔排序

选择排序

  • 简单选择排序
  • 堆排序

归并排序

非比较排序

  • 计数排序
  • 桶排序
  • 基数排序

外部排序

  • 多路合并
  • 置换选择排序

交换排序

bubble sort

思路

在第$i$趟排序过程中，最后$i-1$个值是有序的，对剩余的$n-i+1$个元素，不断的交换两个相邻位置的值，使得后面的值大于前面的值，最后这$n-i+1$个元素中的最大值跑到了倒数第$i$个位置，就像冒泡一样。。
核心思想就是只交换两个相邻的值。

属性

  • 稳定
  • 最坏时间复杂度$O(n^2 )$
  • 最好时间复杂度$O(n )$，在数组正序的情况下，只进行一轮排序，$n-1$次比较，在数组倒序的情况下，进行$n-1$轮排序，进行很多次比较，是$O(n^2 )$。
  • 平均时间复杂度$O(n^2 )$
  • 空间复杂度$O(n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bubble_sort(int a[], int n)
{
    for(int i = 0; i < n - 1; i++)
    {
        for(int j = 0; j < n - i - 1; j++)
        {
            if(a[j] > a[j+1])
            {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}

quick sort

思路

把一个数组分成两部分，然后在将这两部分的每一部分继续分下去，一直分解到每一个部分只有一个元素，这样子就有序了。

属性

  • 不稳定
  • 最坏时间复杂度$O(n^2 )$，在数组基本有序的情况下退化成冒泡排序了。
  • 最好时间复杂度$O(n\log n )$
  • 平均时间复杂度$O(n\log n )$
  • 最好空间复杂度$O(\log n)$，最差是$O(n)$的空间复杂度。每一次需要$O(1)$常数空间存储pivot的位置，在递归调用保存栈的时候需要空间。至多有$\log n$或者$O(n)$次，所以空间复杂度就是$O(n)$。

时间复杂度计算

最坏情况下

数组有序，扫描一遍将它分解成了N-1和1，N-1分解称了N-2, 1
对于$N$个元素的数组，partition的时间复杂度是：
$T(N) = N - 1 + T(N-1)$，即扫描一遍需要比较的次数
$T(N-1) = N - 2 + T(N-2)$
$T(N-2) = N - 3 + T(N-3)$
$\cdots $
$T(3) = 2 + T(2)$
$T(2) = 1 + T(1)$
$T(1) = 0$
合计就是：$N-1 + N-2 + \cdots + 2 + 1 + 0= O(N^2 )$

平均情况下

$T(N) = 2T(\frac{N}{2}) + N$ 做了近似
$\frac{T(N)}{N}) = \frac{T(\frac{N}{2})}{\frac{N}{2}} + 1$
$\frac{T(\frac{N}{2})}{\frac{N}{2}} =\frac{T(\frac{N}{4})}{\frac{N}{4}} + 1 $
$\cdots$
$\frac{4}{4} =\frac{T(4)}{4} + 1$
$\frac{2}{2} =\frac{T(1)}{1} + 1$
而
$T(1) = 0$
$\frac{T(2)}{2} = 1$
$\frac{T(4)}{4} = T(2) + T(1) = 2$
$\frac{T(8)}{8} = T(4) + T(2) + T(1) = 3$
$\frac{T(16)}{16} = T(8) T(4) + T(2) + T(1) = 4$
所以
$\frac{T(N)}{N} = \log N$
$T(N) = N\log N$

代码

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
int partition(int a[], int low, int high)
{
    int pivot = a[low];
    while(low < high)
    {
        while(low < high && a[high] >= pivot)
        {
            high --;
        }
        a[low] = a[high];
        while(low < high && a[low] <= pivot)
        {
            low ++;
        }
        a[high] = a[low];
    }
    a[low] =  pivot;
    return low;
}


int qsort(int a[], int low, int high)
{
    if( low < high)
    {
        int pivot = partition(a, low, high);
        qsort(a, low,  pivot - 1);
        qsort(a, pivot + 1, high);
    }
}


void quicksort(int a[], int n)
{
    qsort(a, 0, n-1);
}

性能测试

自己实现的：
1万数据，大概是0.004秒
10万数据，大概是0.013秒
100万数据，大概是0.13秒

C语言qsort：
100万数据，大概是0.03到0.06秒
1000万数据，大概是0.3秒左右
1亿数据，大概是3秒左右
C++sort：
100万数据，大概是0.13秒左右
1000万数据，大概是1.4秒左右
1亿数据，大概是16秒左右

插入排序

简单插入排序insert sort

思路分析

在第$i$趟排序过程中，前面$i-1$个值是有序的，将第i个数字插入前面有序的长为$i-1$的序列中，构成长为$i$的有序序列。

特点

  • 稳定
  • 最坏时间复杂度$O(n^2 )$
  • 最好时间复杂度$O(n )$，在数组有序的情况下
  • 平均时间复杂度$O(n^2 )$
  • 空间复杂度$O(n)$

代码

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
//首先我写了下面的代码，实际上是有问题的，
//错误示例！！！！！！！！！！！！！！！！！！！！！！！
void insert_sort(int a[], int n)
{
    int i = -1, j = -1, temp = -1;
    for(i = 1; i < n; i++)
    {
        temp = a[i];
        for(j = i - 1; j >= 0; j--)
        {
            if(a[j] > temp)
            {
                a[j+1] = a[j];
            }
            else 
            {
                //如果第j论插入应该插入在0位置时，会跳过这一步的执行。
                a[j+1] = temp;
                break;
            }
        }
    }
}
//正确示例
void insert_sort(int a[], int n)
{
    int i = -1, j = -1, temp = -1;
    for(i = 1; i < n; i++)
    {
        temp = a[i];
        for(j = i - 1; j >= 0; j--)
        {
            if(a[j] > temp)
            {
                a[j+1] = a[j];
            }
            else 
            {
                break;
            }
        }
        a[j+1] = temp;
    }
}

希尔排序

思路简介

希尔排序是对插入排序的扩展。

属性

  • 不稳定
  • 平均的时间复杂度$O(n^{1.3} )$
  • 最坏的时间复杂度$O(n^2 )$
  • 最好的时间复杂度$O(n )$
  • 空间复杂度是$O(1)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void shell_sort(int a[], int n)
{
    int i = -1, j = -1, temp = -1;
    for(int gap = n/2; gap > 0; gap/=2)
    {
        for(i = gap; i < n; i++)
        {
            temp = a[i];
            for(j = i - gap; j >= 0; j -= gap)
            {
                if(temp < a[j])
                {
                    a[j+gap] =  a[j];
                }
                else
                {
                    break;
                }
            }
            a[j+gap] = temp;
        }
    }
}

选择排序

简单选择排序

思路简介

在第$i$趟排序过程中，前面$i-1$个值有序，从后面$n-i+1$个值中选择第$i$小的数，记下下标min_index，如果$i$和min_index不相等的话，交换它们的值。

属性

  • 不稳定
  • 最坏时间复杂度$O(n^2 )$
  • 最好时间复杂度$O(n^2 )$
  • 平均时间复杂度$O(n^2 )$
  • 空间复杂度$O(n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void selection_sort(int a[], int n)
{
    for(int i = 0; i < n - 1; i++)
    {
        int min_index = i;
        for(int j = i; j < n; j++)
        {
            if(a[j] < a[min_index]) 
                min_index = j;
        }
        if(min_index != i)
        {
            int temp = a[min_index];
            a[min_index] = a[i];
            a[i] = temp;
        }
    }
}

heapsort

1.https://www.geeksforgeeks.org/heap-sort/
2.http://www.techgeekbuzz.com/heap-sort-in-c/
3.http://www.techgeekbuzz.com/heap-sort-in-c/
4.https://www.zentut.com/c-tutorial/c-heapsort/

归并排序

思路

将数组分为原来的一半，一直分到每一个都只有一个元素，然后这两个有序数组合并到一块。

属性

  • 稳定
  • 最坏时间复杂度$O(n\log n)$
  • 最好时间复杂度$O(n\log n)$
  • 平均时间复杂度$O(n\log n)$
  • 空间复杂度$O(n)$

代码

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
void merge_sort(int a[], int l, int r)
{
    if(l < r)
    {
        //int middle = (l+r)/2 may be overflow, use (r-l)/2 + l 
        int m = (r-l)/2 + l;
        merge_sort(a, l, m);
        merge_sort(a, m+1, r);
        merge(a, l , m, r);
    }

}


// 这个代码的话，有问题，每次都声明一个N的数组，时间和空间消耗都很大，所以需要进行改善，只需要声明一个r-l+1的临时数组就行了。
void merge(int a[], int l, int m, int r)
{
    //!!!错误
    //int res[N] = { 0 };
    int res[r-l+1] = {0};
    int i = l, j = m+1, k = 0;
    // merge
    while((i <= m) && (j <= r))
    {
        if(a[i] < a[j])
        {
            res[k++] = a[i++];
        }
        else
        {
            res[k++] = a[j++];
        }
    }

    // copy left
    for( ; i <= m; )
    {
        res[k++] = a[i++];
    }

    for( ; j <= r; )
    {
        res[k++] = a[j++];
    }

    // copy to a
    for(int t = l; t <=r; t++)
    {
        a[t] = res[t-l];
    }
}

性能

100万，0.1秒左右
10万，0.02左右
1万，0.003左右

非比较排序

计数排序

思路

假设输入的$n$个数都在$0-k$之间，对于输入的每个元素$x$，统计比它小的值或者和它相等的值的个数，那么这个值在排序后的位置也就确定了。

排序过程

输入数组：[2, 5, 3, 0, 2, 3, 0, 3]
排序后的数组应该是：[0, 0, 2, 2, 3, 3, 3, 5]

  1. 输入待排序数组a：
    0, 1, 2, 3, 4, 5, 6, 7
    a = [2, 5, 3, 0, 2, 3, 0, 3], n=8
  2. 使用数组c统计出现的次数：
    0, 1, 2, 3, 4, 5
    c = [2, 0, 2, 3, 0, 1], k=5
  3. 对c进行操作，计算每个值应该在的位置
    0, 1, 2, 3, 4, 5
    c = [2, 2, 4, 7, 7, 8], k=5
  4. 根据数组c和数组a给出排序后的数组output:
    遍历数组的每一个值，给出他们应该在哪个位置
    a[0] = 2, c[a[0]] = c[2] = 4, c[2]=3, output[4] = a[0] = 2;
    a[1] = 5，c[a[1]] = c[5] = 8, c[5]=7, output[8] = a[1] = 5;
    a[2] = 5，c[a[2]] = c[3] = 7, c[3]=6, output[7] = a[2] = 3; 7中放的是第一个3
    a[3] = 5，c[a[3]] = c[0] = 2, c[0]=1, output[2] = a[3] = 0;
    a[4] = 5，c[a[4]] = c[2] = 3, c[2]=2, output[3] = a[4] = 2;
    a[5] = 5，c[a[5]] = c[3] = 6, c[3]=5, output[6] = a[5] = 3;
    a[6] = 5，c[a[6]] = c[0] = 1, c[0]=0, output[1] = a[6] = 0;
    a[7] = 5，c[a[7]] = c[3] = 5, c[3]=4, output[5] = a[7] = 3;
    正序遍历是不稳定的，倒序遍历是稳定的。上面就是正序的，可以发现不稳定

属性

  • 稳定
  • 不基于比较
  • 时间复杂度是$O(n+k)$
  • 空间复杂度是$O(n+k)$

代码

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
void counting_sort(int a[], int n, int k)
{
    int output[n];
    int freq[k];
    memset(freq, 0, sizeof(freq));

    // freq[i] contains the number of elements equal to i
    for(int i = 0; i < n; i++)
    {
        freq[a[i]] ++;
    }
    
    // freq[i] contains the number of elements equal or less to i
    for(int i = 1; i <= k; i++)
    {
        freq[i] = freq[i] + freq[i-1];
    }
    
    for(int i = n - 1; i >= 0 ; i--)
    {
        output[freq[a[i]]--] = a[i];
    }
               
    for(int i = 0; i < n; i++)
    {
        a[i] = output[i+1];
    }
}

基数排序

思路

借助多关键字排序的思想对单逻辑关键字排序。简单来说，对于十进制数字，依次按照个十百千万上每个位上的数字进行排序，假设有$d$位，需要分别对这$d$位进行排序。对每一位进行排序时，可以使用计数排序，因为$k$不大。

排序过程

给出一组待排序数字：[329, 457, 657, 839, 436, 726, 255]
先按照个位数进行排序，
再按照十位数进行排序，
最后按照百位数进行排序

属性

  • 稳定
  • 时间复杂度$O(d(n+k))$
  • 空间复杂度$O(n+k)$

代码

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
void bucket_sort(int a[], int n)
{
    int max = get_max(a, n);
    printf("max=%d\n", max);
    for(int exp=1; max/exp > 0; exp*=10)
    {
        counting_sort(a, n, exp);
    }
}


int get_max(int a[], int n)
{
    int max = a[0];
    for(int i = 1; i < n ;i++)
    {
        if(a[i] > max)
            max = a[i];
    }
    return max;
}


void counting_sort(int a[], int n, int exp)
{
    int count[10];
    int output[n+1];
    memset(count, 0, sizeof(count));

    //329, 457, 657, 839, 436, 726, 255
    // 1.count
    for(int i = 0; i < n; i ++)
    {
        int temp = (a[i] / exp) % 10;
        count[temp] ++;
    }

    // 2.accumulate count
    for(int i = 1; i < 10; i++)
    {
        count[i] = count[i] + count[i-1];
    }

    // 3.sort
    for(int i = n - 1; i >= 0; i--)
    {
        int temp = (a[i] / exp) % 10;
        output[count[temp]--] = a[i];
    }

    // 4. copy
    for(int i = 0; i < n; i++)
    {
        a[i] = output[i+1];
        printf("%d, ", a[i]);
    }
    printf("\n");
}

桶排序

思路

计数排序是桶排序的一个特例，计数排序中使用的桶的个数和max-min+1的值相同，而通排序中桶的个数要小于等于max-min+1，等于max-min+1时，桶排序就退化成了计数排序。

属性

  • 稳定
  • 最好的时间复杂度是$O(n)$
  • 最坏的时间复杂度是$O(n^2 )$
  • 平均时间复杂度是$O(n+k)$
  • 空间复杂度是$O(n+k)$

代码

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
int get_min(int a[], int n)
{
    int min = a[0];
    for(int i=1; i < n; i++)
    {
        if(a[i] < min)
        {
            min = a[i];
        }
    }
    return min;
}

int get_max(int a[], int n)
{
    int max = a[0];
    for(int i=1; i < n; i++)
    {
        if(a[i] > max)
        {
            max = a[i];
        }
    }
    return max;
}


void bucket_sort(int a[], int n, int bucket_number)
{
    // 1.创建n个桶
    std::vector<int> b[bucket_number];

    int max = get_max(a, n);
    int min = get_min(a, n);

    // 2.每个桶的大小
    int bucket_size = (max - min + 1) / bucket_number;
    for(int i = 0 ; i< n; i++)
    {
        int bucket_index = (a[i] - min) / bucket_size;
        b[bucket_index].push_back(a[i]);
    }

    for(int i = 0; i < bucket_number; i++)
    {
        sort(b[i].begin(), b[i].end());
    }
    int count = 0;
    for(int i = 0; i < bucket_number; i++)
    {
        for(int j = 0; j < b[i].size(); j++)
        {
            a[count++] = b[i][j];
        }
    }
}

快速排序vs归并排序

  • 辅助空间：快排可以使用in-place方法实现，在每一个排序过程中不需要额外的空间，但是快排的递归实现，需要保存栈调用（是常数），平均情况下是$O(\log n)$，最坏情况下是$O(n)$；使用尾递归的快排最坏情况下空间复杂度也是$O(\log n)$。而归并排序需要临时数组存储归并后的排序数组，需要$O(n)$的空间复杂度。
  • 时间复杂度：快排在最坏情况下的时间复杂度是$O(n^2 )$，但是可以使用随机选择pivot的方式避免。
  • 归并排序更适合大的数据结构，mergesore是稳定排序，可以修改成适合链表等数据结构的算法，以及内存和网络上的排序。因为在链表中，插入的时间和空间复杂度都是$O(1)$，因此链表的归并排序可以不需要额外的辅助空间。
  • 快排和归并的平均时间复杂度都是$O(n\log n)$，但是因为归并排序需要分配以及销毁临时数组，所以要更慢一些。
  • 快排是cache friendly的，对于数据来说，他有locality of reference。（即是否很大可能性从cache中读取大量元素）。

简单排序

常见的三大简单排序：冒泡排序，简单选择排序，简单插入排序。
冒泡排序：

  • 优点:比较简单，空间复杂度较低，是稳定的；
  • 缺点:时间复杂度太高，效率慢；

选择排序：

  • 优点：一轮比较只需要一次交换；
  • 缺点：效率慢，不稳定（举个例子2，2，1， 假设我们每趟排序都选择第一个元素作为比较值，第一趟排序会交换第一个2和1，两个2的位置已经变了）。

冒泡排序和简单选择排序的区别和联系：

  • 冒泡排序每趟都是比较无序序列中相邻位置的两个数，而选择排序每趟都是选择无序序列中的最小数；
  • 冒泡排序每一轮比较后，位置不对都需要换位置，选择排序每一趟排序都只需要一次交换；
  • 冒泡排序是通过数去找位置，选择排序是给定位置去找数；

参考文献

1.https://www.quora.com/What-is-the-time-complexity-of-quick-sort/answer/Lakshmi-Narayana-217
2.https://www.cnblogs.com/Good-good-stady-day-day-up/p/9055698.html
3.https://www.cnblogs.com/onepixel/p/7674659.html
4.https://www.geeksforgeeks.org/radix-sort/
5.https://www.geeksforgeeks.org/quicksort-better-mergesort/
6.https://cs.stackexchange.com/a/35510
7.https://www.geeksforgeeks.org/quicksort-tail-call-optimization-reducing-worst-case-space-log-n/

Docker

发表于 | 更新于 | 分类于

什么是docker

Docker是一个开源的应用容器引擎，开发者可以打包应用及依赖包到一个可移植的容器中，然后发布到其他机器上，与平台，硬件等无关。容器是完全使用沙箱机制，相互之间不会有任何接口。

Docker构成

Docker包含三大组件：镜像(image)，容器(container)和仓库(registry)。

  1. Docker镜像是创建Docker容器的模板，其中包含了应用程序所需的各项资源。可以使用dockerfile创建docker镜像。
  2. Docker容器是独立运行的一个或者一组应用，镜像和容器的关系相当于面向对象中的类和对象。
  3. Docker仓库用来存放镜像，可以理解为代码控制中的代码仓库，默认的docker仓库是Docker Hub。

Docker采用CS架构，所以docker还有Docker client和docker服务器。

  1. Docker client(客户端)，Docker client通过命令行或者其他工具使用Docker API与Docker服务器(Docker daemon)通信。
  2. Docker服务器(主要是一个docker daemon)，包含docker镜像并以容器形式运行镜像的主机，或者说运行Docker daemon和容器的主机。

镜像

Dockerfile

在Dockerfile中，每一条指令都会创建一个镜像层，增加整体镜像的大小。
https://www.cnblogs.com/lsgxeva/p/8746644.html

容器

仓库

Ubuntu Docker安装

方法1

方法2

方法3

  1. 获取最新版本的docker
1
2
3
4
5
6
7
8
9
10
11
12
wget -qO- https://get.docker.com/ | sh
# 从https://get.docker.com下载安装脚本，通过管道执行
``` 报错：``` txt
Got permission denied while trying to connect to the Docker daemon socket at unix:///var/run/docker.sock: Get http://%2Fvar%2Frun%2Fdocker.sock/v1.40/images/json: dial unix /var/run/docker.sock: connect: permission denied
``` 是因为docker daemon使用socker at unix，需要root权限才可以访问，解决方案有以下两种：
1.使用sudo
2.docker daemon启动时，会给docker用户组读写unix socket的权限，所以只需要将当前用户加入docker用户组即可： ``` shell
sudo groudadd docker    # 添加docker用户组
cat /etc/group | grep 'docker'  # 查看docker group中的成员
sudo gpasswd -a $USER docker    # 将当前用户加入到docker用户组中
newgrp docker   # 更新docker用户组
cat /etc/gropu | grep 'docker'  # 查看docker group中是否有当前用户

Docker使用

镜像操作

从Docker Hub查找镜像

1
docker search [OPTIONS] TERM

从Docker仓库pull镜像

以下shell命令从Docker仓库拉取指定镜像：

1
docker pull [OPTIONS] [Docker Registry地址] NAME[:TAG]

Docker client利用pull命令从Docker registry拉取Docker Image到Docker host，然后使用run命令在Docker host上运行一个Docker container运行拉取的Docker image。

Push镜像到Docker仓库

将本地镜像上传到镜像仓库，需要先登录：

1
docker push [OPTIONS] NAME[:TAG]

或者反过来，Docker client通过build命令在Docker host创建一个子集的Docker image，然后Docker client使用push命令将Docker iamge推送到Docker Registry。这个Docker Image就可以被自己或者其他人pull了。

列出本地镜像

1
2
3
docker images
# 或者
docker image ls

使用Dockerfile创建镜像

1
2
docker build [OPTIONS] PATH | URL | -
# docker build -t name:tag . #使用当前目标的Dockerfile创建镜像

运行一个新的容器

1
docker run [OPTIONS] IMAGE [COMMAND] [ARG...]

运行docker

1
2
3
4
# 启动docker后台服务
sudo service docker start
# 测试
docker run hello-world

更换docker仓库镜像

修改/etc/docker/daemon.json文件，在其中加入：

1
2
3
{
  "registry-mirrors": ["http://hub-mirror.c.163.com"]
}

示例

Docker安装tensorflow

1
2
docker pull tensorflow/tensorflow:1.14.0-py3
docker run --name docker-tensorflow-1.14-py3 -ti tensorflow/tensorflow:1.14.0-py3 /bin/bash

Docker安装python 3.7

1
2
3
4
5
6
7
8
docker pull python:3.7
mkdir -p ~/python/myapp
cd ~/python/myapp
# 在该目录下创建helloworl.py文件
docker run -v $PWD/myapp:/usr/src/myapp -w /usr/src/myapp python:3.7 helloworld.py
# -v $PWD/myapp:/usr/src/myapp: 将主机中当前目录的myapp挂在到容器中的/usr/src/myapp
# -w /usr/src/myapp:指定容器的/usr/src/myapp为工作目录
# python helloworl.py 使用容器中的python命令执行工作目录中的helloworld.py

基于tensorflow创建RL docker

编写Dockerfile如下

1
2
3
4
5
# tensorflow=1.14.0, gym=0.15.3, torch=1.3.0
FROM tensorflow/tensorflow:1.14.0-py3
MAINTAINER Docker mxxhcm mxxhcm@gmail.com
RUN pip install --upgrade pip
RUN pip install torch==1.3.0+cpu torchvision==0.4.1+cpu -f https://download.pytorch.org/whl/torch_stable.html && pip install gym==0.15.3

然后创建image：

1
docker build -t mxxhcm/rl-py-3.6:v1

Docker命令

NAME[:TAG]默认是 NAME:latest

常见命令

  • 列出本地镜像

    1
    2
    3
    docker images
    # 或者
    docker image ls

  • 从Docker Hub查找镜像

    1
    2
    3
    4
    5
    docker search [OPTIONS] TERM
    # --automated：
    # --no-trunc：显示完整的镜像描述
    # -s：列出收藏数不小于指定值的镜像
    docker search ubuntu

  • 从Docker仓库拉取指定镜像

    1
    2
    3
    4
    5
    6
    7
    docker pull [OPTIONS] [Docker Registry地址] NAME[:TAG]
    # -a:拉取所有tagged镜像
    # --disable-content-trust:忽略镜像的校验，默认是开启的
    # 默认的Docker registry地址是DockerHub
    docker pull java # 从Docker Hub下载最新版Java镜像
    docker pull ubuntu:14.04 
    # 完整的仓库名和标签名是libary/ubuntu:14.04

  • 使用Dockerfile创建镜像

    1
    2
    3
    docker build -t name:tag #使用当前目标的Dockerfile创建镜像
    docker build github.com/creack/docker-firefox #使用URL地址创建镜像
    docker build -f /path/to/a/Dockerfile   # 使用-f指定Dockerfile文件位置

  • 将本地镜像上传到镜像仓库，需要先登录

    1
    2
    docker push [OPTIONS] NAME[:TAG]
    # --disable-content-trust:忽略镜像的校验，默认是开启的

  • 运行一个容器

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    docker run [OPTIONS] IMAGE [COMMAND] [ARG...]
    # --name:自己指定一个容器名字，
    # -t为容器重新分配一个伪输入终端，常和-i连用
    # -i以交互模式运行容器，常和-t连用
    # -d表示后台运行
    # -p指定端口映射，格式为：主机端口:容器端口
    # images-name:运行的image名称
    # tag:镜像的版本
    docker run --name container-name -d images-name:tag
    docker run --name docker_tensorflow -it tensroflow/tensorflow  bash

  • 连接到正在运行的容器

    1
    docker attach [OPTIONS] CONTAINER

  • 开始，停止，重启一个容器

    1
    docker start/stop/restart container-name

  • 杀死一个运行中的容器

    1
    docker kill -s KILL container-name

  • 创建一个容器但是不启动

    1
    docker create --name container-name -d images-name:tag

  • 列出容器

    1
    2
    docker ps
    # 加上-a显示所有的容器，包含未运行的

容器生命周期管理

  • run
  • start/stop/restart
  • kill
  • rm
  • pause/unpause
  • create
  • exec

容器操作

  • ps
  • inspect
  • top
  • attach
  • events
  • logs
  • wait
  • export
  • port

容器rootfs命令

  • commit
  • cp
  • diff

镜像仓库

  • login
  • pull
  • push
  • search

本地镜像管理

  • images
  • rmi
  • tag
  • build
  • history
  • save
  • load
  • import

info/version

  • info
  • version

参考文献

1.https://docs.docker.com/engine/install/ubuntu/
2.https://juejin.im/post/5d57c1b5f265da03dc076ba6
3.https://www.cnblogs.com/chenxuming/p/9682571.html
4.https://www.cnblogs.com/wushuaishuai/p/9984228.html
5.https://www.cnblogs.com/informatics/p/8276172.html

Actor-Mimic

发表于 | 更新于 | 分类于

Actor Mimic

本文提出了Actor-Mimic，一个multitask和transfer learning方法，使用多个expert DQN指导训练一个可以在多个taskes上使用的单个policy network，并且可以将这些经验迁移到新的taskes上。

Policy Regression Objective

给定多个sources games $S_1, \cdots, S_N$，我们的第一个目标是获得一个能玩任何source games，并且尽可能和expert DQN性能相近的single multitask policy network。为了训练这样一个网络，使用$N$个expert DQN $E_1, \cdots, E_N$进行指导。一个可能的方法是定义student network和expert network之间$Q$值的均方根误差。因为expert values funcitons在不同的游戏之间可能变化很大，所以作者首先将$Q$值经过softmax变成了policies，softmax的输出都在$0$和$1$之间，所以可以提高训练的稳定性。我们可以把softmax看成让student更多的关注expert DQN在每个state选择的action（DQN选择的是Q值最大的action），经过softmax相当于让它更sharp了。
最后得到了一个actor，或者说是一个policy，它模仿了所有DQN experts的decisions。比如，在$Q$值上计算Boltzman分布：
$$\pi_{E_i} (a|s) = \frac{ e^{\tau^{-1} Q_{E_i}(s,a) } }{\sum_{a’\in A_{E_i} } e^{\tau^{-1} Q_{E_i}(s,a) } } \tag{1}$$
其中$\tau$是温度，$A_{E_i}$是expert DQN $E_i$使用的action space。给定$S_i$的一个state s，定义multitask network的policy objective是expert network’s policy和currnet multitask policcy的cross-entropy:
$$L^i_{policy}(\theta) = \sum_{a\in A_{E_i} }\pi_{E_i} (a|s) \log \pi_{AMN}(a|s;\theta) \tag{2}$$
其中$\pi_{AMN}(a|s;\theta) $是$\theta$参数化的multitask Actor Mimic Network policy。和Q-learning把自身当做target value相比，AMN得到了一个stable supervised training signal (expert network)指导 multitask network训练。
为了获得训练数据，可以sample expert network后者使用AMN action outputs生成trajectories。即使AMN还在学习过程中，也能得到好的结果。至少在AMN是linear function approximator时，可以证明AMN会收敛到expert policy。

Feature Regression Objective

除了对policy进行回归以外，还可以对feature进行回归。用$h_{AMN}(s)$和$h_{E_i}(s)$分别表示AMN和第$i$个expert network在state s处feature的hidden activation，他们两个的dimension不一定要相等。使用一个feature回归网络$f_i(h_{AMN}(s))$，预测$s$处$h_{E_i}(s)$到$h_{AMN}(s)$的映射，映射$f_i$的结构是随意的，可以使用以下的回归loss进行训练：
$$L^i_{FeatureRegression}(\theta, \theta_{f_i}) = || f_i(h_{AMN}(s;\theta); \theta_{f_i}) - h_{E_i}(s) ||^2_2 \tag{3}$$
其中$\theta$是AMN的参数，$\theta_{f_i}$是第$i$个特征回归网络的参数。使用这个loss训练，最终我们的目标是得到一个multitask network能够包含多个expert network的features。

Actor-Mimic Objective

将policy objective和feature objective结合在一起，就得到了actor-mimic objective：
$$ L^i_{ActorMimic}(\theta, \theta_{f_i}) = L^i_{policy}(\theta) + \beta L^i_{FeatureRegression}(\theta, \theta_{f_i}) \tag{4}$$
$\beta$用来控制两个objective的权重。直观上来说，我们可以把policy objective看成expert network教会AMN该怎么act（模仿expert的action），而feature objective类似于expert network教会AMN为什么这样act，模仿expert的思考过程（特征提取过程）。

Transfering Knowledge

通过优化actor-mimic objective，我们得到一个在所有source target上都表现不错的expert network，接下来我们可以把它迁移到相关的target task上。为了迁移到新的task上，首先移除掉AMN的final softmax layer，然后用AMN的参数初始化一个DQN在新的task上继续训练，接下来和标准的DQN训练方式一样。Multitask pretaining可以看成学习了related tasks中对于policies definition相当有效的特征，然后初始化DQN。如果source和target tasks很像的话，pretained features对于target task是相当有效的。

Multitask experiments

简介

Multitask任务中并不进行transfer，仅仅使用policy regression objective同时在multitask上训练一个AMN。

baselines

  • Multitask DQN: 使用多个games训练一个DQN，只有最后的full-connected layer不同。
  • Multitask Convolutions DQN: 使用多个games训练一个DQN，但是只共享convolutional layer，每个game都有自己的全连接层和softmax层。

网络架构：

32个步长为$4$的$8\times 8$filters
64个步长为$2$的$4\times 4$filters
64个步长为$1$的$3\times 3$filters
$512$ fully-connected units
$18$个actions
除了最后一层都有一个relu。

实验数据采集

AMN和DQN expert对比

DQN训练到收敛，使用的是训练到收敛过程中的max test reward，收敛过程中最后10个epochs的mean test reward。
AMN在每个source game上训练100个epochs， 每一个epoch是250000 frames，总共有2500万 frames。图中展示了AMN在100个epochs中最大的test reward和最后100个epochs的mean test reward。

AMN和MDQN，MCDQN对比

AMN，MDQN和MCDQN在每个source game上训练40个epochs， 每一个epoch是250000 frames，总共有2500万frames，每一个training epoch之后进行一个$125000$ frames的tesing epoch。最后图中展示了AMN,MDQN以及MCDQN在每个tesing epoch的test average episode rewrad。

Transfer experiments

小的AMN（和DQN expert架构相同）的AMN能够学习多个source tasks的knowledge，而大一些的AMN能够更容易的迁移。在transfer实验中，使用了比DQN expert更复杂的AMN model，能够同时玩13个source games。为了防止过拟合，AMN在每个source game上训练400万个frames。
然后用训练完的AMN当做新任务上DQN的初始化权重。仅仅使用policy regression objective的叫做AMN-policy，而使用feature和policy objective的叫做AMN-feature。将AMN-feature以及AMN-policy的结果和随机初始化的DQN baseline进行比较。
每隔4个traing epoches，每个training epoch后都有一个testing epoch，输出这4个epoches的average test reward。
使用的网络架构：
256个步长为$4$的$8\times 8$filters
512个步长为$2$的$4\times 4$filters
512个步长为$1$的$3\times 3$filters
512个步长为$1$的$3\times 3$filters
$2048$ fully-connected units
$1024$ fully-connected units
$18$个actions
除了最后一层都有一个relu。

AMN的细节

所有的AMN使用Adam优化器，有一个18-unit的output layer，每一个对应atari 18个actions中可能的一个，使用18个actions简化了不同游戏有不同的action subsets。训练一个特定的游戏时，mask那些not valid的actions，然后在valid actions上使用softmax。AMN每个game使用100000大小的replay memeory。
在feature regression objective中，设置$\beta$是$0.01$，设置$f_i$是第$i$个expert feature的线性投影。在训练过程中，AMN使用的$\epsilon$-greedy policy中$\epsilon$是常数$0.1$。在训练过程中，基于AMN而不是expert DQN选择actions。
在实验中使用的DQN，使用RMSProp优化，和nature-DQN的架构，超参数以及训练过程都一样。Replay memory总共有1000000 frames。

参考文献

data structure linked-list

发表于 | 更新于 | 分类于

表

常见的表的操作。

  • print_list和make_empty；
  • find返回关键字首次出现的位置；
  • insert和delete从表的某个位置进行插入或者删除；
  • find_k_th返回第$k$个位置上的元素。

表的两种实现方式

  1. 数组实现的表
  2. 链表

数组实现的表

对表的操作可以通过使用数组实现。

  • 需要连续的存储空间，数组的大小通常要比链表所需要的大一些
  • 获得第$k$个位置上的元素的时间复杂度是$O(1)$
  • 遍历和查找的时间复杂度是线性的$O(n)$。
  • 插入和删除的平均时间复杂度是$O(n)$，平均情况下每次插入和删除需要移动一半的元素。
  • 通过$n$次插入创建一个表需要$O(n^2 )$的时间复杂度。

链表

  • 不连续存储，减少插入和删除的时间复杂度
  • 链表由一系列不必在内存中连续存储的结构体组成。每一个结构含有表元素和指向表元素后继元素的指针，叫做next指针。最后一个结构的next指针指向NULL，它的取值是$0$。
  • 遍历和查找的时间复杂度是$O(n)$
  • 获得第$k$个位置的元素的时间复杂度也是$O(n)$
  • 插入和删除的时候不需要进行移动，只需要在插入或者删除节点进行操作。

表头节点（哑结点）

为了使得在表头处节点的操作和在其他节点的操作一样，可以通过添加一个哑结点实现。在删除表的第一个元素的时候，就可以使用哑结点帮助操作。

链表逆序

链表的排序

参考文献