三指针法翻转单向链表

定义3个指针, 原理是三个指针分别指向前三个元素，将第一个元素指向第二个元素，然后全部后移

1. 第三个指针向前移动
2. 将第二个元素指向第一个元素
3. 第一个指针和第二个指针向前移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

struct Node{
　　int data;
　　Node *next;
};

Node *reverse(Node *head) {
  Node *pPrev = nullptr;
  Node *pHead = head;
  Node *pNext = nullptr;
  while (pHead) {
    pNext = pHead->next;
    pHead->next = pPrev;
    pPrev = pHead;
    pHead = pNext;
  }
  return pHead;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Node *reverse(Node *head) {
  if (!head) {
    return head;
  }
  Node *first = nullptr;
  Node *second = head;
  Node *third = head->next;

  while (third) {
    second->next = first;

    first = second;
    second = third;
    third = third->next;
  }

  second->next = first;

  return second;
}

翻转链表的部分节点

翻转node[m]->node[N]部分， 理解时先将链表分为3部分: part1->part2->part3, 只翻转part2

翻转动作套用三指针法，但部分翻转的难点在于处理part1为空和非空的情况，所以要判断m时候为1

• m==1即要翻转第一个元素时，需要先记录part2翻转后的tail node，最后将其next指向part3的第一个元素
• m!=1即part1不为空，需要先记录part2翻转后的tail node和part1的最后一个node，最后将其指向part2的新head,以及将part2的第一个node指向part3

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

struct ListNode *reverseBetween(struct ListNode *head, int m, int n) {
  if (m == n) {
    return head;
  }

  if(!head || !head->next){
    return head;
  }

  // write code here
  struct ListNode *pleft = NULL;
  struct ListNode *phead = head;
  struct ListNode *pright = NULL;


  // 只有当m！=1时才需要，指向part1的最后一个元素
  struct ListNode *pPart1Tail = NULL;
  // 当m=1时指向part2的第一个元素
  struct ListNode *pPart2NewTail = NULL;

  // skip m
  for (int i = 1; i < m; i++) {
    pleft = phead; 
    phead = phead->next;
  }

  // 保存part2的head,也是翻转后的tail
  pPart2NewTail = phead;
  // m != 1 时pleft不为NULL
  struct ListNode *pPartOneTail = pleft;

  int i = 0;
  // 翻转次数要比m-n大1
  while (phead && i < n - m + 1) {
    pright = phead->next;

    phead->next = pleft;

    pleft = phead;
    phead = pright;
    i++;
  }

  if(m==1){
    // 指向part3的头
    pPart2NewTail->next = phead;
    return pleft;
  }

  pPartOneTail->next = pleft;
  pPart2NewTail->next = phead;

  return head;
}

在Linux下使用sdcc进行单片机开发

周末研究了下单片机，本来准备写个定时器来控制电扇开关，发现比起树梅派，单片机实在不太方便

开发环境搭建

Windows大家都用Keil, 一站式比较方便，但这是个收费软件。而在Linux下，使用到一些组合来实现编译和烧录

1. sdcc 开源的编译器，类似gcc
2. stcflash github上的开发者开发的烧录脚本

sdcc 在Debian有包可以直接安装

1

# apt install sdcc

再 clone github的代码到本地，需要使用root权限执行烧录。而我执行是发现缺少python serial包，要全局安装就使用apt命令

1

# apt install python3-serial

这样环境就搭建好了

编写代码

用c语言开发时要引入比较的定义头文件，我的单片机是好多年前买的国产stc 89C52RC， 是基于51的拓展版本，于是用了sdcc的8052.h头，路径在

1
2
3
4
5
6
7
8
9

// /usr/share/sdcc/include/mcs51/8052.h
#ifndef REG8052_H
#define REG8052_H
  
#include <8051.h>     /* load definitions for the 8051 core */
  
#ifdef REG8051_H
#undef REG8051_H
#endif

不过不需要我们指定路径，sdcc会自动引入。窥视其内容可以发现它包含了8051的东西，所以说52是基于51的

回顾一下51单片机知识

1. 单片机的寄存器初始是0, 而引脚初始都是高点位
2. 定时器和计数器的触发事件都是靠中断，中断执行当前（main）中的函数而执行中断响应函数，这跟Unix内核是一样的。 单片机还具有多个优先级的中断，可以嵌套
3. 中断的触发靠计数寄存器（TLx和THx）溢出，这两个都是8位寄存器，所以同时使用时，在2^16时溢出。但也有只用其中一个寄存器的时候，这由TMOD寄存器控制

TMOD寄存器

TMOD是不可按位访问的寄存器，意思是只能一次性赋值所有位。 TMOD控制着两个定时器/计数器0和1

• TMOD高四位用于设置定时器/计数器1，低四位用于设置定时器/计数器0；
• GATE寄存器决定是否使用外部INTx控制，即软件自动启动，还是外部启动，这里赋值0
  • GATE=1时，“与门”的输出信号K由INTx输入电平和TRx位的状态一起决定(即此时K=TRx·INTx)，当且仅当TRx=1,INTx=1(高电平)时，计数启动；否则，计数停止。当INT0引脚为高平时且TR0置位，TR0=1；启动定时器T0
  • GATE=0时，“A”输出恒为1，“B”的值由TRx决定，当TR0=1,启动定时器/计数器T0，当TR1=1，启动定时器/计数器T1
• CT位为1时选择计数器模式，为0时选择定时器模式
• M1,M0用于选择工作方式，当M0=1,M1=0时，使用TL0和TH0的16位来计数

TCON寄存器

定时器初始化

这里使用定时器0

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void Timer0Init(void) // 1毫秒@12.000MHz
{
    TMOD = 0x01; //设置定时器模式 0000 0001
    // TCON
    TF0 = 0; //初始化溢出标志
    TR0 = 1; //定时器0开始计时
    // 计数器初始值，再触发一次就溢出了
    TH0 = 0xFF; //设置定时初值
    TL0 = 0xFE; //设置定时初值
    // 中断通路
    EA = 1; 
    ET0 = 1;
    PT0 = 0;
}

计数器模式

这里使用计数器0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void Count0Init(void) // 1毫秒@12.000MHz
{ 
    TMOD = 0x05; //设置计数器模式 0000 0101

    // TCON
    TF0 = 0; 
    TR0 = 1; //定时器0开始计时

    // 计数器初始值，再触发一次就溢出了
    TH0 = 0xFF;  //设置定时初值
    TL0 = 0xFE;  //设置定时初值

    // 中断通路
    EA = 1;
    ET0 = 1;
    PT0 = 0;
}

中断响应函数

sdcc和keil有一些区别，中断标志符使用__interrupt

1
2
3
4
5
6
7
8
9
10

static unsigned int T0Count = 0;
void timer0_routine() __interrupt (1) {
  T0Count++;
  TH0 = 0xFF; //设置定时初值
  TL0 = 0xFE; //设置定时初值
  if (T0Count == 3) {
    T0Count = 0;
    P1_1 = 0;  // 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
28
29
30
31
32

// main.c
#include "8052.h"

void Timer0Init(void) // 1毫秒@12.000MHz
{
  TMOD = 0x01;
  TF0 = 0;
  TR0 = 1;
  TH0 = 0xFF;
  TL0 = 0xFE;
  EA = 1;
  ET0 = 1;
  PT0 = 0;
}

void main(void) {

  Timer1Init();
  while (1)
    ;
}

unsigned int T0Count = 0;
void timer0_routine() __interrupt(1) {
  T0Count++;
  TH0 = 0xFF;
  TL0 = 0xFE;
  if (T0Count == 3) {
    T0Count = 0;
    P1_1 = 0;
  }
}

编译和烧录

代码保存为main.c

1
2
3
4

# 使用sdcc编译
sdcc main.c
将sdcc生成的ihx文件转为hex文件
packihx main.ihx  > main.hex

烧录到单片机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

sudo python ~/github/stcflash/stcflash.py main.hex
Connect to /dev/ttyUSB0 at baudrate 2400
Detecting target... done
 FOSC: 11.955MHz
 Model: STC89C52RC (ver4.3C) 
 ROM: 8KB
 [X] Reset stops watchdog
 [X] Internal XRAM
 [X] Normal ALE pin
 [X] Full gain oscillator
 [X] Not erase data EEPROM
 [X] Download regardless of P1
 [X] 12T mode
Baudrate: 38400
Erasing target... done
Size of the binary: 147
Programming: #################### done
Setting options... done

数据库优化总结

这里总结了从数据库设计和sql结构两个方面的优化

数据库设计范式 Normal Form

范式是在数据库的设计时总结出来的一套规范，通常满足3范式就足够了。但由于3范式也存在问题，所以有了3.5范式

范式从1到3是越来越严格，所以满足1NF不一定满足2NF，但满足2NF就肯定满足1NF

满足所有范式的表没有冗余数据，但也有问题，比如效率不高。这就有了反范式做法，即允许数据冗余，用空间换时间

1NF：原子化，单元格里的值不能被分割

可见，有条目的电话格里有两个号码，是可以分割的， 所以不满足1NF。应改为

当所有单元格都无法分割了，就满足了第一范式

2NF：属性不允许部分依赖（复合）主键

满足2NF前提要满足1NF, 范式2要求非主属性必须依赖完整复合主键或者主键。

下表Employee Id和Department Id组成复合主键
|Employee Id|Department Id |Office Location |
|—|—|—|
|1EDUO01 | ED-T1 | Pune |
|1EDUO02 | ED-S2 |Bengaluru |
|1EDUO03 | ED-M1 | Delhi |
|1EDUO04 | ED-T3 | Mumbai |
|1EDUO05 | ED-T1 | Pune |

但Office Location只依赖主键的Employee Id部分。或者说只需Department Id就能保证Office Location唯一， 所以是部分依赖。这样不满足2NF了，应改成两个表

3NF： 依赖不能传递

满足3NF前提要满足2NF, 还有非主属性必须依赖主键/复合主键，不能依赖其他非主属性

上表的Subject依赖非主属性Subject Id，而不是依赖Student Id， 这就不满足3NF了。应改成

不满足3范式的问题

不满足3范式的数据库会存在以下问题:

• 插入问题： 插入数据时，如果只有部分数据，可能导致插入失败（若某列为NOT NULL）。举例2NF里原来的表，若只有Department Id和Office Location，就无法插入
• 更新问题： 当更新某个字段时，需要更新其它列。举例2NF的表，当更新Pune时， 第1列和第4列都要更新
• 删除问题： 当删除某些属性时，其他属性也要删除， 举例3NF原来的表，当删除SQL课程时，学生Alex的信息也会丢失

3.5NF： BCNF

3.5范式用于解决3范式遗留问题
例如

说明：

• 一个学生可以登记多个科目
• 多个老师可以教授同一个科目
• 每个科目会有一个老师分配给一个学生

所以这个表满足3范式，因为Student Id和Subject组成了复合主键，决定了Professor。

但是不满足3.5NF，因为Student Id和Subject组成了复合主键，所以Subject是主属性， 而存在Professor依赖Subject， 虽然Subject是主属性，但Professor是非主属性，所以不满足BCNF。

此表应改成

反范式

没有冗余数据的设计未必是好设计，有时为了效率，必须降低范式标准，适当允许保留冗余数据，以达到用空间换时间的目的。

例如订单表存在商品，单价，数量，总价， 这里总价是冗余的，因为可以通过单价和数量来求得，但总价经常需要，所以冗余可以提高效率。

HAVING 和查询语句优先级

SQL查询字句类似C语言的运算符优先级， 虽然标准里没有定义优先级，但大致为以下

1

FROM > WHERE > SELECT > GROUP BY > HAVING > ORDER BY

这个顺序可以帮忙理解查询语句是如何执行的，比如因为SELECT优先级低于FROM, 所有只能在FROM中定义alais在SELECT中使用，而不能在SELECT中定义alias并在FROM中使用

HAVING指令通常和GROUP一起用，因为优先级比GROUP低，所以HAVING可以计算出GROUP的值并进行筛选。

1

SELECT Sno FROM Grade GROUP BY Sno HAVING COUNT(Cno) > 3;

这个语句筛选出相同Sno记录的个数>3的集合

VIEW和数据冗余

View是一种虚拟表，可以将多表的数据关联在一起，也可以做一些冗余数据，如计算平均值

1

CREATE VIEW Cl_avg_age AS SELECT Clno, AVG(Sage) AS avg_age FROM Student;

事物，存储过程和触发器

存储过程需要提前创建再使用。 因为存储过程中定义变量， 输入输出明确，所以让数据库操作更安全。

1

CREATE PROCEDURE ap_returncount @Sno char(7) AS DECLARE @count int SELECT @count = Number FROM Class WHERE Clno = (SELECT Clno FROM Student WHERE Sno = @Sno) RETURN @count;

触发器是当触发条件时自动执行的命令，如当插入和更新满足条件时自动执行事物回撤。这是基于事物机制的。
事物可以保证多个操作的原子性， 当莫个操作不满足条件则全部ROLLBACK，回撤所有的操作，例如典型的转账场景，必须要扣除和增加都成功时才能成功。

但事物导致效率比较低。

1

CREATE TRIGGER tri_ins_upd_student ON Student AFTER INSERT, UPDATE AS IF 40 < (SELECT Number FROM Class WHERE Clno = (SELECT Clno FROM inserted )) ROLLBACK TRANSACTION;

参考

https://www.edureka.co/blog/normalization-in-sql/

前言

记一次单元测试用例时失败，且出现奇怪的报错

1

tpp.c:63: __pthread_tpp_change_priority: Assertion `new_prio == -1 ||(new_prio >= __sched_fifo_min_prio && new_prio <=__sched_fifo_max_prio)' failed

原因

函数定义如下，原因是下面的第一个assert条件不成立，new_prio != -1。这个函数的注释说明了需要使用者确保调用前已初始化。

1
2
3
4
5
6
7
8
9
10

/* We only want to initialize __sched_fifo_min_prio and __sched_fifo_max_prio
   once.  The standard solution would be similar to pthread_once, but then
   readers would need to use an acquire fence.  In this specific case,
   initialization is comprised of just idempotent writes to two variables
   that have an initial value of -1.  Therefore, we can treat each variable as
   a separate, at-least-once initialized value.  This enables using just
   relaxed MO loads and stores, but requires that consumers check for
   initialization of each value that is to be used; see
   __pthread_tpp_change_priority for an example.
 */

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

int
__pthread_tpp_change_priority (int previous_prio, int new_prio)
{
  struct pthread *self = THREAD_SELF;
  struct priority_protection_data *tpp = THREAD_GETMEM (self, tpp);
  int fifo_min_prio = atomic_load_relaxed (&__sched_fifo_min_prio);
  int fifo_max_prio = atomic_load_relaxed (&__sched_fifo_max_prio);
  if (tpp == NULL)
    {
      /* See __init_sched_fifo_prio.  We need both the min and max prio,
         so need to check both, and run initialization if either one is
         not initialized.  The memory model's write-read coherence rule
         makes this work.  */
      if (fifo_min_prio == -1 || fifo_max_prio == -1)
        {
          __init_sched_fifo_prio ();
          fifo_min_prio = atomic_load_relaxed (&__sched_fifo_min_prio);
          fifo_max_prio = atomic_load_relaxed (&__sched_fifo_max_prio);
        }
      size_t size = sizeof *tpp;
      size += (fifo_max_prio - fifo_min_prio + 1)
              * sizeof (tpp->priomap[0]);
      tpp = calloc (size, 1);
      if (tpp == NULL)
        return ENOMEM;
      tpp->priomax = fifo_min_prio - 1;
      THREAD_SETMEM (self, tpp, tpp);
    }
  assert (new_prio == -1
          || (new_prio >= fifo_min_prio
              && new_prio <= fifo_max_prio));
  assert (previous_prio == -1
          || (previous_prio >= fifo_min_prio
              && previous_prio <= fifo_max_prio));

网上帖子的原因是给初始化mutex并设置RECURSIVE类型时，忘了对mutexattr进行初始化，导致使用了脏内存
即pthread_mutexattr_init(&mutexattr)

1
2
3
4
5
6
7
8
9
10

pthread_mutexattr_t mutexattr;

// Set the mutex as a recursive mutex
pthread_mutexattr_settype(&mutexattr, PTHREAD_MUTEX_RECURSIVE_NP);

// create the mutex with the attributes set
pthread_mutex_init(&CritSec, &mutexattr);

// After initializing the mutex, the thread attribute can be destroyed
pthread_mutexattr_destroy(&mutexattr);

总之，要在线程启动前初始化好mutex

其他问题

这个问题其实是c++代码抛出来的，多线程执行了下面的代码，导致了上面的问题。

AppCache中有个小粒度的锁，但这个锁还未初始化就被其他线程去lock了，导致出现问题。所以要mutex最好要在线程启动前初始化

1
2
3

AppCache{
std::mutex
}；

1
2
3
4
5
6

auto app = m_app_cache.find(app_path);
if (app == m_app_cache.end()) {
  // create a new monitor element
  m_app_cache.insert_or_assign(app_path, std::make_shared<AppCache>());
}
std::lock_guard<std::mutex> lk(app->second->cache_mutex);

引用

https://sourceware.org/legacy-ml/libc-help/2008-05/msg00072.html?utm_source=pocket_mylist

堆排序

堆排类似选择排序，只排序未排序的部分，但堆排比较方式不同，每次只比较log(n)次
最终的堆排时间复杂度为O(nlogn)

关键下标

堆一般用数组来表示，但是关系为

• 当以1为起点时，若父节点是n

• 左子节点=n*2

• 右子节点=n*2 + 1

• 若节点为n, 则其父节点为n/2

• 若元素为m个，则最后一个根节点（非叶节点）为m/2

• 当以0为起点时，若父节点是n

• 左子节点=(n+1)2-1 = n2 + 1

• 右子节点=(n+1)2+1 -1 = n2 + 2

• 若节点下标为n, 其父节点为(n+1)/2 - 1 = (n-1)/2

• 若元素为m个，则最后一个根节点（非叶节点）为(m+1)/2-1 = (m-1)/2

可见，若以1为起点，要简洁很多

建立堆

1. 从第一个非叶子节点开始，比较父子节点中找的最值，如果需要调整则交换父子节点再递归遍历下一层：

• 建立最小堆时，每次比较出最大值，一遍之后，堆顶为最大
• 建立最大堆时，每次比较出最小值，一遍之后，堆顶为最小

2. 比较到顶部节点时，完成第一次遍历，找到了顶部的最值
3. 将堆顶的最值与尾部交换，遍历范围-1，然后从堆顶开始比较
4. 重复3动作，直到范围为1

3的动作类似选择排序，只遍历未排序的部分

最大堆和最小堆

最小堆可以求得topK大的数，反过来最大堆可以求得topK小的数

topK

堆排序通常用来实现topK，适用于限制内存的情况。方法是建立一个堆大小为K： 先用头部K个数据建立最小堆，后续的数字与堆顶（最小）比，如果跟小则跳过，否则替换然后执行thiftdown。其时间复杂读为O)KlogK + NlogK), 只需要一次建堆，后续都是比较。空间复杂度为K。

也可以则使用分治法，将数据分为多组，每组求其top k。最后合并起来再排序，求最终的topK。 分治法可以配合线程一起使用加快速度。

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

// 使用最小堆来实现topK
void thiftdown(int *heap, int root, int size) {
  int m = root;
  int l = root * 2 + 1;
  int r = root * 2 + 2;

  if (l < size && heap[l] > heap[m]) {
    m = l;
  }
  if (r < size && heap[r] > heap[m]) {
    m = r;
  }

  if (m != root) {
    int tmp = heap[root];
    heap[root] = heap[m];
    heap[m] = tmp;

    thiftdown(heap, m, size);
  }
}

void adjust(int *heap, int root, int size) {
  int m = root;
  int l = root * 2 + 1;
  int r = root * 2 + 2;

  if (l < size && heap[l] < heap[m]) {
    m = l;
  }
  if (r < size && heap[r] < heap[m]) {
    m = r;
  }

  if (m != root) {
    int tmp = heap[root];
    heap[root] = heap[m];
    heap[m] = tmp;

    adjust(heap, m, size);
  }
}

void heapify(int *heap, int size) {
  for (int i = (size - 1) / 2; i >= 0; i--) {
    thiftdown(heap, i, size);
  }

  while (size > 0) {
    int tmp = heap[0];
    heap[0] = heap[size - 1];
    heap[size - 1] = tmp;
    size--;
    thiftdown(heap, 0, size);
  }
}

void add(int *heap, int val, int size) {
  if (heap[0] >= val) {
    return;
  }
  heap[0] = val;
  adjust(heap, 0, size);
}

使用方法

1
2
3
4
5

heapify(m, 5);
for (int i = 5; i < 49; i++) {
  add(m, n[i], 5);
}
return m[0];

海量数据求topK

常见问题类似：

1. 求许多重复整数中，重复第K多的正整数。
2. 求文本中重复出现的词语次数，重复第K多的”，
3. ip中访问最K多的”。

这些问题需要多一步统计，统计出现次数，然后再使用堆来查找topK。

1. 使用数组统计，如果目标都是正整数，如问题1
2. 使用map<target, int>统计，int表示出现次数，如果目标字符串，如问题2和问题3

统计完成后，将目标和计数放入结构体，再使用堆来找topK

1
2
3
4

{
  目标
  次数
}

总结

topK 问题除了堆排序以外，还常用快排来找。

DP 四板斧

以跳台阶的题目为例， 题目是以每次跳1层或2层的方式跳到n台阶， 问一共有多少种跳法
开始我觉得这是求路径个数，而通常dp算最大或最小值， 不适用。
但后来换个角度想，求最大最小必须得试过所有方法才得出来的， 而将所有的试过的方法计数，就是这题的解

写出递归

dp第一步要先写出递归来， 写递归得写收敛条件
这里的收敛条件是当传参小于0,则说明解法失败（多跳了），返回0。 当恰好为0则解法有效返回1

递归体就是跳1层和跳2层

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

static int jump(int number) {
  if (number < 0) {
    return 0;
  } else if (number == 0) {
    return 1;
  }
  return jump(number - 1) + jump(number - 2);
}
  
int jumpFloor(int number) { 
  return jump(number - 1) + jump(number - 2); 
}

用缓存来优化递归

递归显然会重复计算， 可以用缓存计算结果来避免， 当有缓存时使用缓存，否则才去计算， 最后将结果缓存

并且使用缓存时应该指定尾递归的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int jump(int number, int *cache) {
  if (number < 3) {
    return cache[number];
  }
  // 缓存没命中就计算
  int ret1 =
      cache[number - 1] != -1 ? cache[number - 1] : jump(number - 1, cache);
  int ret2 =
      cache[number - 2] != -1 ? cache[number - 2] : jump(number - 2, cache);
  cache[number] = ret1 + ret2;
  return cache[number];
}

int jumpFloor(int number) {
  int cache[number + 1];
  for (int i = 0; i < number + 1; i++) {
    cache[i] = -1;
  }

  cache[0] = 0;
  cache[1] = 1;
  cache[2] = 2;
  return jump(number, cache);
}

递归改for循环

递归的调用流程是自上而下，先计算(n)->计算(n -1)->再计算(n-2) … 0
现在要反过来， 先计算(0)->计算(1)->计算(2) … n
即自下而上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int jumpFloor(int number) {
  if (number < 3) {
    return number;
  }

  // 之前要初始化为了判断， 而现在显然下标大于2的值是要计算出来的，不需要读取  
  // 所以不需要初始化
  int cache[number + 1];
  cache[1] = 1;
  cache[2] = 2;

  for (int i = 3; i <= number; i++) {
    cache[i] = cache[i - 1] + cache[i - 2];
  }

  return cache[number];
}

缩小缓存大小

仔细看， 其实每次计算只涉及最大的三个数， 所以数组并不需要那么大，只用3个单元就足够，故直接写成3个变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int jumpFloorD(int number) {
  if (number < 3) {
    return number;
  }

  int total = 0;
  int minors2 = 1;
  int minors1 = 2;

  for (int i = 3; i <= number; i++) {
    total = minors1 + minors2;
    minors2 = minors1;
    minors1 = total;
  }

  return total;
}

这样DP解法就出来了， 这个套路是我从力扣上学到的， 非常有效简单

总结

从上可见，你需要训练如何发现递归关系，剩下的工作就是缓存递归调用的结果，最后是将从上到下的解决思路变为从下到上。这样我们就可以用O(N)的时间复杂度去遍历

参考

https://leetcode.com/discuss/study-guide/1490172/dynamic-programming-is-simple

浅谈内存管理

这里记录一下看书所得，应用程序的内存管理，即glibc的malloc和相关函数

内存管理的重要性

过去Linux通过默认的dlmalloc来申请内存，但不支持多线程，这导致的竞争和性能降低，而ptmalloc2支持多线程，也成为了Linux新的默认方式
ptmalloc2通过为每个线程单独维护一个帧，这样每个线程的申请和释放可以并行执行，但当线程过多时，线程也将共享帧。这种帧叫做per thread arena

主线程和线程的内存申请方式

主线程中使用brk来申请大块内存，其实brk不过是修改了寄存器的值。而且返回的大小通常要比malloc申请的多，如同测试中的在主线程中申请100个字节大小的内存，返回了132 KB。

1

55f7b402c000-55f7b404d000 rw-p 00000000 00:00 0                          [heap]

而在线程中，malloc使用mmap来申请内存，返回大小也比申请大小多，测试中的在线程中申请100字节，返回了64M的地址空间， 但只有8MB是可用的堆内存。

1
2

7fb738000000-7fb738021000 rw-p 00000000 00:00 0      
7fb738021000-7fb73c000000 ---p 00000000 00:00 0

主线程中申请的地址大于Data Section的地址，说明使用的brk，而后者申请时用了mmap，对比附录文档可以看出32位和64位区别比较大

arena

主线程和线程使用不同的arena，这样主线程和线程同时申请内存时不存在竞争。但不是所有的线程都独享一份arena, arena的个数限制如下

1
2
3
4

For 32 bit systems:
     Number of arena = 2 * number of cores.
For 64 bit systems:
     Number of arena = 8 * number of cores.

当线程个数太多时，会公用主线程的arena

main arena 和 per thread arena

main arena 指在主线程（main）中使用的，而后者是子线程中使用，两者有很大区别
主线程只有一块heap，所以没有heapinfo结构，而子线程有。主线程的Arena header是全局变量，所以存在于libc.so的Data Segment中

线程的arena含有多个heap, 每个heap都有heapinfo结构，多个heapinfo组成链表。线程的多个heap共享一个malloc_state 也称为Arena header

Arena header包含了bin、top chunk等信息

每个heap有多个chunk，每个chunk有个malloc_chunk结构，其管理chunk的状态和其在heap中的偏移大小，有以下几种状态

• Allocated chunk
• Free chunk
• Top chunk
• Last Remainder chunk

Top chunk 处于arena的顶部，在freelist没有合适大小的chunk时使用，如果Top chunk比申请的大，则又分为两部分（新Top chunk和用户申请的chunk）

Last Remainder chunk, 是当用户请求small chunk时，会先遍历small bin和Unsorted bin， 如果都无法满足，则遍历其他bin。
如果找到的chunk还有剩余，则这个chunk变为Last Remainder chunk，且将被加入到Unsorted bin
这样的好处是多次申请small chunk时，会先向Unsorted bin的Last Remainder chunk申请， 所以小内存块会集中分布在Last Remainder chunk，提高小块内存的局部性

bin

当malloc的内存被free后（仅仅是例子中的100字节chunk），并不会释放给内核，而是进入到glibc的bin中，也叫做freelist。
当下次申请内存时，会从bin中查找合适的chunk，而只有当没有合适的大小时，才向内核申请。

所以bin用来保存free过的chunk, 基于chunk的大小分为

• Fast bin
• Unsorted bin
• Small bin
• Large bin

但不同的bin都使用链表来管理这些chunk

测试方法

获取程序运行时的pid, 假设为949293, 那么通过以下命令可以获取程序的内存结构

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

cat /proc/949632/maps
# address           	  perms offset  dev    inode   			 pathname
55f7b378a000-55f7b378b000 r--p 00000000 103:02 4727634                   /tmp/a.out (deleted)
55f7b378b000-55f7b378c000 r-xp 00001000 103:02 4727634                   /tmp/a.out (deleted)
55f7b378c000-55f7b378d000 r--p 00002000 103:02 4727634                   /tmp/a.out (deleted)
55f7b378d000-55f7b378e000 r--p 00002000 103:02 4727634                   /tmp/a.out (deleted)
55f7b378e000-55f7b378f000 rw-p 00003000 103:02 4727634                   /tmp/a.out (deleted)
55f7b402c000-55f7b404d000 rw-p 00000000 00:00 0                          [heap]
7f4808000000-7f4808021000 rw-p 00000000 00:00 0 
7f4808021000-7f480c000000 ---p 00000000 00:00 0 
7f480ea3d000-7f480ea3e000 ---p 00000000 00:00 0 
7f480ea3e000-7f480f241000 rw-p 00000000 00:00 0 
...

• address 是起始地址-结束地址，差值为空间大小
• perm 是指权限，分为rwx[p,s], [p,s]指最后一位可以是private或者shared, 这些能通过mprotect命令修改(c中的const实现)
• offset 仅对mmap的区域有效，指映射偏移量
• pathname 如果此区域是映射的文件，则显示文件名。如果映射的是匿名映射则显示空白, 匿名映射包括线程通过mmap申请的堆内存，而[heap]是main函数的堆

所以通过计算address可以知道glibc申请的内存情况

malloc的返回值有意义吗

在我本机（gcc (Debian 10.2.1-6) 10.2.1 20210110 12GB）上测试了一段程序

1. 如果一次性申请13GB，malloc返回失败
2. 如果每次只申请2GB但不释放，第10次申请（20GB）malloc返回成功
3. 如果每次只申请2GB但不释放且访问，第三次申请（6GB）malloc返回成功，但访问时OOM

所以说，malloc的返回值是没有太大意义的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void foo(size_t large) {
  char *buffer = (char *)malloc(large);
  if (buffer == NULL) {
    printf("error!\n");
    exit(EXIT_FAILURE);
  }
  printf("Memory allocated\n");
  //  for (size_t i = 0; i < large; i += 4096) {
  //    buffer[i] = 0;
  //  }
  printf("Travalse done\n");
}
int main() {
  // size_t large = 1099511627776;
  size_t large = 13958643712;
  for (int i = 0; i < 100; i++) {
    foo(2147483648);
  }

  return EXIT_SUCCESS;
}

其他

内存管理不仅存在应用程序（或者说glibc）中，Linux内核也有内存管理。也不只有glibc的内存malloc一种实现，还有

• dlmalloc – General purpose allocator
• ptmalloc2 – glibc
• jemalloc – FreeBSD 的libc实现, 相比其他第三方，这个比较流行
• tcmalloc – Google 为多线程场景开发
• libumem – Solaris

malloc是glibc对ptmalloc2的包装，而ptmalloc2是dlmalloc的重构，区别很大

最后总结，glibc的malloc通过两个系统调用函数brk和mmap来向内核申请内存，但内存释放后不会归还内核，而是放到freelist等待再次被利用

引用

https://man7.org/linux/man-pages/man5/proc.5.html
https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/comment-page-1/
https://lemire.me/blog/2021/10/27/in-c-how-do-you-know-if-the-dynamic-allocation-succeeded/

spdlog

spdlog 支持多spdlog::logger, 适用与多个隔离模块的日志分别保存

而且logger含有多个sink的vector。sink与文件对应，如果想把日志输出到多个文件，就创建多个sink

1

std::vector<sink_ptr> sinks_;

logger和sink的级别独立

1
2
3
4
5
6
7
8

// logger级别的判断
template<typename... Args>
inline void spdlog::logger::log(source_loc source, level::level_enum lvl, const char *fmt, const Args &... args)
{
    if (!should_log(lvl))
    {
        return;
    }

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

// sink级别的判断
inline void spdlog::logger::sink_it_(details::log_msg &msg)
{
#if defined(SPDLOG_ENABLE_MESSAGE_COUNTER)
    incr_msg_counter_(msg);
#endif
    for (auto &sink : sinks_)
    {
        if (sink->should_log(msg.level))
        {
            sink->log(msg);
        }
    }

所以可以支持不同的级别到不同的文件，例如logger设置为trace级别， sink1 设置为info级别， sink2设置为trace级别，这样就能创建两个日志文件

1
2

info.log  # 只保存info级别
full.log  # 保存所有级别（logger级别或者sink2的级别）

爬虫

如何做一个最简单的爬虫？ 一条bash命令爬深圳7天天气

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

#获取7天的天气
wget -q http://www.weather.com.cn/weather/101280601.shtml -O - \
| grep 'class="wea"\|^<h1>'  | grep -o ">.*<" | sed 's/>//;s/<//' \
| awk 'ORS=NR%2==1?" ":"\n" {print}'  

7日（今天） 晴
8日（明天） 晴
9日（后天） 晴
10日（周五） 晴
11日（周六） 晴
12日（周日） 晴
13日（周一） 晴转小雨

这条命令如何写出来的

1. 定目标，想好要爬什么，如爬深圳天气
2. 先在浏览器访问天气网站，网址http://www.weather.com.cn/， 再找到深圳7天天气的网页链接为http://www.weather.com.cn/weather/101280601.shtml
3. 右键菜单里选择查看网页源码，搜索天气的内容所在位置
4. 找规律： 日期和天气的行有特定起始内容，日期这行以<h1>开头，天气这行包含class="wea"
5. 格式化： 清除不要的内容，使用sed和awk

拓展

只有这样没有意义， 不如自己在浏览器上看？ 但如果一次性查找武汉、北京、广州的天气，但网页只能查当天的，只有保存到硬盘的数据才能永远回头翻
或者如果想每天自动执行一遍呢？ 又或者如何自动发邮件提醒你带伞呢？ –都是可以的， 这需要更多耐心和学习

但因为bash处理网页比较麻烦，而且也不是今天的主题语言。

关键组件

• python
• scapy
• Beautiful Soup

python

python简单灵活的语法又有丰富的生态， 适合作为入门爬虫的编程语言

Beautiful Soup

早期使用python自带的request库， 就能简单地实现一个爬虫软件

主角scrapy

An open source and collaborative framework for extracting the data you need from websites. In a fast, simple, yet extensible way.

scrapy 是一套完整框架， 实现了爬取网站的许多细节工作，让我们不需要了解代码，就能爬网站。其开发商还提供爬虫托管服务， 可以将你的爬虫做成在线服务， 而bs只是一个库

简单介绍

• 目录结构
• 配置

scrapy选择器

选择器用来指定网页的位置，scrapy支持的选择器有两种：

• css
• xpath

自己先在源码上找规律，也可以简单地使用浏览器提供的复制选择器功能

先手动验证, 获取列表的所有详情页链接

1
2
3
4
5

scrapy shell "https://www.douban.com/group/search?cat=1013&q=深圳租房"  
# xpath方式
response.xpath('//td[has-class("td-subject")]//a/@href').getall()
# css方式
response.css('td.td-subject').css('a::attr(href)').getall()

先手动验证, 获得下一页

1
2
3
4

response.css('span.next').css('a::attr(href)').get()
# 控制台->‘Copy CSS Selector’
# .next > a:nth-child(2)
response.css('.next > a::attr(href)').get()

详细

数据处理

爬到的数据可能乱和重复， 可以加个清洗的步骤， 在爬到数据后对数据过滤，删除不要的数据

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

# 删除重复条目
class DuplicatesPipeline(object):

    def __init__(self):
        self.ids_seen = set()

    def process_item(self, item, spider):
        if item['title_digist'] in self.ids_seen:
            raise DropItem("Duplicate item found: %s" % item)
        else:
            self.ids_seen.add(item['title_digist'])
            return item

具体项目 爬豆瓣租房

使用爬虫清理百度搜索结果

百度搜索的有效结果只占少部分，其他是广告，视频和推荐词

用爬虫来提取有效结果

1
2
3
4

# 标题
response.css('#content_left > div.result').css('a:nth-child(1)::text').getall()
# 结果
response.css('#content_left > div.result').css('a:nth-child(1)::attr(href)').get()

部署成在线服务

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

pip install shub

shub login
Insert your Zyte Scrapy Cloud API Key: <API_KEY>

# Deploy the spider to Zyte Scrapy Cloud
shub deploy

# Schedule the spider for execution
shub schedule blogspider 
Spider blogspider scheduled, watch it running here:
https://app.zyte.com/p/26731/job/1/8

# Retrieve the scraped data
shub items 26731/1/8

其他问题

登录

不是所有页面都能像豆瓣这样简单直接访问，有的需要登陆，这时需要设置cookie
可将浏览器的访问的请求复制为curl请求，再将curl请求转换为scrapy请求, 有工具curl2scrapy

爬携程机票，但这样只能看最新或者最便宜的机票，无法自动订票

1

curl 'https://flights.ctrip.com/international/search/api/lowprice/calendar/getCalendarDetailList?v=0.4625948281116462' -H 'User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Firefox/78.0' -H 'Accept: application/json' -H 'Accept-Language: zh-CN,en-US;q=0.5' --compressed -H 'Content-Type: application/json;charset=utf-8' -H 'transactionID: 0feb04e3db5648acb409a9efaf68eb99' -H 'scope: d' -H 'Cache-Control: no-cache' -H 'Origin: https://flights.ctrip.com' -H 'Connection: keep-alive' -H 'Referer: https://flights.ctrip.com/online/list/oneway-wuh0-szx?_=1&depdate=2021-12-08&cabin=y_s&adult=1&searchid=j1043107111-1628648957090-97788Tk-0&containstax=1' -H 'Cookie: _bfa=1.1638949895953.3tfx42.1.1638949895953.1638949895953.1.2; _bfs=1.2; FlightIntl=Search=[%22WUH|%E6%AD%A6%E6%B1%89(%E5%A4%A9%E6%B2%B3%E5%9B%BD%E9%99%85%E6%9C%BA%E5%9C%BA)(WUH)|477|WUH|WUH|480%22%2C%22SZX|%E6%B7%B1%E5%9C%B3(SZX)|30|SZX|480%22%2C%222021-12-09%22]; _RF1=116.30.223.163; _RSG=mtaCn0GabiBpwk2uaRD22A; _RDG=28d46524d5c5f727d530fed50e21ed2094; _RGUID=bb259100-3132-4df0-a082-35b9380aeeb3; _bfaStatus=send; MKT_Pagesource=PC; _bfaStatusPVSend=1; _bfi=p1%3D10320673302%26p2%3D10320673302%26v1%3D2%26v2%3D1' -H 'Sec-GPC: 1' -H 'TE: Trailers' --data-raw '{"cabin":"Y_S","flightWay":"S","flightSegmentList":[{"arrivalCityCode":"SZX","departureCityCode":"WUH","departureDate":"2021-12-08"}]}'

代理ip

爬取的时候莫名其妙 IP 就被网站封掉了，毕竟各大网站也不想自己的数据被轻易地爬走。
对于爬虫来说，为了解决封禁 IP 的问题，一个有效的方式就是使用代理，使用代理之后可以让爬虫伪装自己的真实 IP，如果使用大量的随机的代理进行爬取，那么网站就不知道是我们的爬虫一直在爬取了，这样就有效地解决了反爬的问题。

阿布云

模拟用户代理useragent

User Agent中文名为用户代理，简称 UA，它是一个特殊字符串头，使得服务器能够识别客户使用的操作系统及版本、CPU 类型、浏览器及版本、浏览器渲染引擎、浏览器语言、浏览器插件等。

可以使用自己浏览器的UA，也可以用百度蜘蛛的UA列表
但目标网站是否允许就难说了， 需要多试一试

模拟浏览器

Selenium 是一个用于Web应用程序测试的工具。Selenium测试直接运行在浏览器中，就像真正的用户在操作一样。

1
2

cd ～/github/SeleniumLogin
python SeleniumLogin/core/taobao.py

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

def login(self, username, password, chromedriverpath, **kwargs):
    # 基本设置
    browser = webdriver.Chrome(options=self.chrome_opts)
    browser.get(self.login_url)
    driver_wait = WebDriverWait(browser, 60)
    # 点击'亲, 请登录', 进入登录界面
    button = driver_wait.until(EC.presence_of_element_located((By.CLASS_NAME, 'h')))
    button.click()
    # 输入用户名密码
    username_sender = driver_wait.until(EC.presence_of_element_located((By.ID, 'fm-login-id')))
    username_sender.send_keys(username)
    password_sender = driver_wait.until(EC.presence_of_element_located((By.ID, 'fm-login-password')))
    password_sender.send_keys(password)
    time.sleep(2)
    # 检查是否出现了滑动验证码
    try:
        slider = browser.find_element_by_xpath("//span[contains(@class, 'btn_slide')]")
        if slider.is_displayed():
            ActionChains(browser).click_and_hold(on_element=slider).perform()
            ActionChains(browser).move_by_offset(xoffset=258, yoffset=0).perform()
            ActionChains(browser).pause(0.5).release().perform()
    except:
        pass
    # 点击登录按钮
    #button = driver_wait.until(EC.presence_of_element_located((By.CLASS_NAME, 'password-login')))
    #button.click()
    # 返回必要的数据
    infos_return = {'username': username}
    return infos_return, browser

headless

Splash HTTP API

引用

http://c.biancheng.net/view/2011.html
https://github.com/CharlesPikachu/SeleniumLogin

容器技术

容器是利用’cgroup’和’namespace’ 实现软件级的虚拟化，产品有lxc和docker。不同与全虚拟化和半虚拟化，这些是硬件辅助的半虚拟化Zen(Zen也有全虚拟化)和全虚拟化kvm
因为容器使用主机内核，不存在特权指令翻译，所以从性能上比较，容器是最高效的，其次是kvm, Zen

cgroup和namespace

这两个是容器技术的根基，包括Docker, lxc。实际上docker开始用的lxc，后来用go重新写了libcontainer来实现控制这两个东西
简单来说，cgroup实现对进程组的资源的限制和监控，而namespace如同c++里面类似，实现了进程组之间的隔离

但除此之外, 虚拟化系统时则还需要rootfs支持

LXC和Docker

lxc代码合入了内核，其原理和Docker非常类似, 不过Docker有比较丰富的全套工具和方便的api

nsenter命令的使用

容器技术都使用到了namespace, 而nsenter可以操作namespace, 进入容器内部，以下都一docker容器为例

使用命令, 获取到容器的首进程pid

1
2

docker inspect --format '{{.State.Pid}}' containername
3015

然后可以使用nsenter来进入容器，如同docker exec 一样

1
2
3
4

$ pwd
/home/user
$ sudo nsenter -t 3015 -m  pwd
/

-m表示挂载命名空间，这样就能访问docker里的进程的文件系统，所以能正确打印出容器进程的当前目录
-t表示目标进程，nsenter可以获取以下命名空间。 跟通过执行ls /proc/self/ns所看到的差不多，这里self是命令本身pid

1
2
3
4
5
6
7
8
9
10

/proc/pid/ns/mnt    the mount namespace
/proc/pid/ns/uts    the UTS namespace
/proc/pid/ns/ipc    the IPC namespace
/proc/pid/ns/net    the network namespace
/proc/pid/ns/pid    the PID namespace
/proc/pid/ns/user   the user namespace
/proc/pid/ns/cgroup the cgroup namespace
/proc/pid/ns/time   the time namespace
/proc/pid/root      the root directory
/proc/pid/cwd       the working directory respectively

上面的每项都有对应的参数，而’-a’表示进入上面的所有命名空间