跳转至

Welcome

FakeIt

FakeIt是一个单元测试工具,类比gmock, 但是比gmock更modern和轻量,因为它支持c++11和header-only

使用方法

FakeIt和gmock都提供Mock和调用计数功能,Mock通常用于接口类,用来定义并实例化接口类对象。gmock和FakeIt都能对调用参数进行校验,但FakeIt的Verify函数还提供在校验失败时打印参数值,这是gmock不具备的

struct IAppManager {
  // inotify calls when new event
  virtual void notify_add_event(EventType event_type,
                                const std::string& filepath) = 0;
  virtual void notify_rename_event(EventType event_type,
                                   const std::string& filepath,
                                   const std::string& filepath_new) = 0;

  virtual ~IAppManager() = default;
};

TEST_CASE("Test Inotify") {
  Mock<IAppManager> appmanager_mock;
  Fake(Dtor(appmanager_mock));
  Fake(Method(appmanager_mock, notify_add_event));
  Fake(Method(appmanager_mock, notify_rename_event));

  auto& app_manager = appmanager_mock.get();
  SECTION("test add") {
    std::thread t1([&app_manager](){
      app_manager.notify_add_event(EventType::File, "filename");
      app_manager.notify_add_event(EventType::File, "filename");
      app_manager.notify_add_event(EventType::File, "filename");
    });
    t1.join();
    Verify(Method(appmanager_mock, notify_add_event)).Exactly(2);
  }
}

这里没有对调用参数校验,而仅对调用次数验证,可以预见,结果失败,因为调用了3次。

问题

上面的测试用例会失败,因为次数不匹配。而这时FakeIt会打印所有调用的参数值,但参数由于是个引用,而且引用在线程退出时被释放,打印一个无效引用导致会抛异常

due to a fatal error condition:                                                                 
  SIGSEGV - Segmentation violation signal 

解决办法

对于本测试而言,解决办法就是将传参所引用的对象duration改大,如全局变量或者static,或者在线程外定义它

TEST_CASE("Test Inotify") {
  Mock<IAppManager> appmanager_mock;
  Fake(Dtor(appmanager_mock));
  Fake(Method(appmanager_mock, notify_add_event));
  Fake(Method(appmanager_mock, notify_rename_event));

  auto& app_manager = appmanager_mock.get();
  SECTION("test add") {
    std::string filename = "asd";
    std::thread t1([&app_manager, &filename](){
      app_manager.notify_add_event(EventType::File, filename);
      app_manager.notify_add_event(EventType::File, filename);
      app_manager.notify_add_event(EventType::File, filename);
    });
    t1.join();
    Verify(Method(appmanager_mock, notify_add_event)).Exactly(2);
  }
}
修改之后,不会触发SIGSEGV异常, 而是能正确打印出调用参数

  Expected pattern: appmanager_mock.notify_add_event( Any arguments )
  Expected matches: exactly 2
  Actual matches  : 3
  Actual sequence : total of 3 actual invocations:                             
    appmanager_mock.notify_add_event(?, asd)
    appmanager_mock.notify_add_event(?, asd)
    appmanager_mock.notify_add_event(?, asd) 

但对于间接调用的接口,且在单元测试里无法控制变量类型,则没有什么办法,只能保证Extractly准确而不用打印参数值

gmock的方式

gmock使用预先设定调用参数,在调用时再判断,所以不会出现无效引用的问题

在c语言中打印支持不同类型变量

in this doc, i'll introduce how to print(stringify) variable of different types, typeof is a GCC extension, and _Generic is part of C11. typeof is disabled by option '-std=*' or '-ansi, so usetypeof` instead.

c11 _Generic

#include <stdio.h>

#define PRINT_VAR(var)        \
    _Generic((var),           \
        int: print_int,       \
        float: print_float,   \
        double: print_double, \
        char: print_char      \
    )(#var, (var))

// Type-specific print functions
void print_int(const char* name, int value) {
    printf("%s = %d\n", name, value);
}

void print_float(const char* name, float value) {
    printf("%s = %.2f\n", name, value);
}

void print_double(const char* name, double value) {
    printf("%s = %.2f\n", name, value);
}

void print_char(const char* name, char value) {
    printf("%s = %c\n", name, value);
}

int main() {
    int x = 10;
    float y = 3.14f;
    double z = 3.14159;
    char c = 'A';

    PRINT_VAR(x);  // Prints: x = 10
    PRINT_VAR(y);  // Prints: y = 3.14
    PRINT_VAR(z);  // Prints: z = 3.14
    PRINT_VAR(c);  // Prints: c = A

    return 0;
}

simpler way

linter raise warnings if place printf directly in _Generic.

#define DECLARE_PRINT_FUNC(value)                                              \
  do {                                                                         \
    printf("%s = ", #value);                                                   \
    char *format = NULL;                                                       \
    _Generic((value),                                                          \
        int: format = "%d\n",                                                  \
        long unsigned int: format = "%lu\n",                                   \
        long: format = "%ld\n",                                                \
        float: format = "%.2f\n",                                              \
        double: format = "%.2f\n",                                             \
        char: format = "%c\n",                                                 \
        default: format = NULL);                                               \
    format != NULL ? printf(format, (value)):                                  \
    printf("Unknown type\n");                                                  \
  } while (0)

using GCC build-in typeof instead of _Generic

#include <stdio.h>

#define PRINT_VAR_TYPEOF(var)                                                  \
  do {                                                                         \
    printf("%s = ", #var);                                                     \
    char *format = NULL;                                                       \
    __typeof__(var) _v = (var);                                                \
    if (__builtin_types_compatible_p(__typeof__(_v), int))                     \
      format = "%d\n";                                                         \
    else if (__builtin_types_compatible_p(__typeof__(_v), float))              \
      format = "%.2f\n";                                                       \
    else if (__builtin_types_compatible_p(__typeof__(_v), double))             \
      format = "%.2f\n";                                                       \
    else if (__builtin_types_compatible_p(__typeof__(_v), char))               \
      format = "%c\n";                                                         \
    printf(format, (var));                                                     \
  } while (0)

单向链表翻转算法

三指针法翻转单向链表

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

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;
}
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

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有包可以直接安装

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

# apt install python3-serial

这样环境就搭建好了

编写代码

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

// /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

timer.png

  • 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寄存器

TCON.png

定时器初始化

这里使用定时器0

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

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

static unsigned int T0Count = 0;
void timer0_routine() __interrupt (1) {
  T0Count++;
  TH0 = 0xFF; //设置定时初值
  TL0 = 0xFE; //设置定时初值
  if (T0Count == 3) {
    T0Count = 0;
    P1_1 = 0;  // 0输出低电平,灯泡亮
  }
}

完整代码

// 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

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

烧录到单片机

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:原子化,单元格里的值不能被分割

Employee Id Employee Name Phone Number Salary
1EDU001 Alex +91 85532065
+91 85532066
60,131
1EDU002 Alex +91 85532066 75,331
1EDU003 Alex +91 85532068 63,231
1EDU004 Alex +91 85532069 70,231
1EDU005 Alex +91 85543065
+91 85543075
60,531

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

Employee Id Employee Name Phone Number Salary
1EDU001 Alex +91 85532065 60,131
1EDU001 Alex +91 85532066 60,131
1EDU002 Alex +91 85532066 75,331
1EDU003 Alex +91 85532068 63,231
1EDU004 Alex +91 85532069 70,231
1EDU005 Alex +91 85543065 60,531
1EDU005 Alex +91 85543075 60,531

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

2NF:属性不允许部分依赖(复合)主键

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

下表Employee IdDepartment 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了,应改成两个表

Employee Id Department Id
1EDUO01 ED-T1
1EDUO02 ED-S2
1EDUO03 ED-M1
1EDUO04 ED-T3
1EDUO05 ED-T1
Department Id Office Location
ED-T1 Pune
ED-S2 Bengaluru
ED-M1 Delhi
ED-T3 Mumbai

3NF: 依赖不能传递

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

Student Id Student name Subject Id Subject Adress
1DT1SENGO1 Alex 15CS11 SQL Goa
1DT1SENGO2 Barry 15CS13 JAVA Bengaluru
1DT15ENGO3 Clair 15CS12 C++ Delhi
1DT15ENG04 DavId 15CS13 JAVA Kochi

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

Student Id Student name Subject Id
1DT1SENGO1 Alex 15CS11
1DT1SENGO2 Barry 15CS13
1DT15ENGO3 Clair 15CS12
1DT15ENG04 DavId 15CS13
Subject Id Subject Adress
15CS11 SQL Goa
15CS13 JAVA Bengaluru
15CS12 C++ Delhi
15CS13 JAVA Kochi
不满足3范式的问题

不满足3范式的数据库会存在以下问题: * 插入问题: 插入数据时,如果只有部分数据,可能导致插入失败(若某列为NOT NULL)。举例2NF里原来的表,若只有Department IdOffice Location,就无法插入 * 更新问题: 当更新某个字段时,需要更新其它列。举例2NF的表,当更新Pune时, 第1列和第4列都要更新 * 删除问题: 当删除某些属性时,其他属性也要删除, 举例3NF原来的表,当删除SQL课程时,学生Alex的信息也会丢失

3.5NF: BCNF

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

Student Id Subject Professor
1DT15ENG01 SQL Prof. Mishra
1DT15ENG02 JAVA Prof. Anand
1DT15ENG02 C++ Prof. Kanthi
1DT15ENG03 JAVA Prof. Anand
1DT15ENG04 DBMS Prof. Lokesh

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

所以这个表满足3范式,因为Student IdSubject组成了复合主键,决定了Professor

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

此表应改成

Student Id Professor Id
1DT15ENG01 1DTPF01
1DT15ENG02 1DTPF02
1DT15ENG02 1DTPF03
Professor ID Professor Subject
1DTPF01 Prof. Mishra SQL
1DTPF02 Prof. Anand JAVA
1DTPF03 Prof. Kanthi C++

反范式

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

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

HAVING 和查询语句优先级

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

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

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

SELECT Sno FROM Grade GROUP BY Sno HAVING COUNT(Cno) > 3;
这个语句筛选出相同Sno记录的个数>3的集合

VIEW和数据冗余

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

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

事物,存储过程和触发器

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

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,回撤所有的操作,例如典型的转账场景,必须要扣除和增加都成功时才能成功。

但事物导致效率比较低。

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/

编程语言中小数精度问题

计算机使用2进制存储数据,而2进制可以表示所有的10进制整数,这样在整数范围内不存在问题,但导致小数的精度不够。

例如表示整数时,二进制不存在问题: |十进制|二进制| |--|--| |0| 0| |1|2^0| |2|2^1| |3|2^2 + 2^1|

而表示小数时,二进制只能有0.5, 0.25, 0.125...。 |二进制|十进制| |--|--| |2^-1| 0.5| |2^-2|0.25| |2^-3|0.125|

所以二进制表示10进制的小数颗粒比较大,若想表示0.6: 就要使用二进制小数 * 2^n来表示,有些数始终无法相等

浮点型和双精度

计算机显然没有无穷大的位置来存储”高阶的X“,只能折衷一下。故在c/c++中,有两种类型来表示小数,对应不同精度:
内存分布,两种类型的内存分布都为: 符号位(sign)+偏移位(exponent)+尾数位(mantissa), 其值则为 (-1)^sign * mantissa * 2^exponent

float: 浮点类型

占用4字节(32位),精度为10^-6, 即第7位小数开始可能四舍五入或者直接忽略

内存分布: 第一位是符号位,后8位为偏移位,最后23位为尾数位,则有23+1位来表示小数,10^7 < 2^23+1 < 10^8,所以可以精确到第7位, 但最后以为可能会4四舍五入,精确到第6位

double: 双精度类型

占用8字节(64位),精度为10^-15, 即第16位小数开始可能四舍五入或者直接忽略

内存分布: 第一位是符号位,后11位为偏移位,最后52位为尾数位,则有52+1位来表示小数,10^16 < 2^52+1 < 10^17,所以可以精确到第16位, 但最后以为可能会4四舍五入,精确到第15位

计算问题

由于精度问题,精度之外的小数就会被忽略掉,导致出现下面的相等

double i = 0.1;
double j = 0.2;
i+j == 0.3 + 4e-17;// 后面的数被忽略了
注意如果要使用float类型,需要显式使用'0.1f', 因为默认以double处理

如何比较两个浮点数

浮点数比较不可能100%正确,但下面都是错的

float a = 0.15 + 0.15
float b = 0.1 + 0.2
if(a == b) // can be false!
if(a >= b) // can also be false!
if( Math.abs(a-b) < 0.00001) // wrong - don't do this
if( Math.abs((a-b)/b) < 0.00001 ) // still not right!

下面的才是大部分正确

float absA = fabs(a);
float absB = fabs(b);
float diff = fabs(a - b);
if (a == b) { // shortcut, handles infinities
    return true;
} else if (a == 0 || b == 0 || (absA + absB < 1e-16)) {
            // a or b is zero or both are extremely close to it
            // relative error is less meaningful here
    return diff < (epsilon * Float.MIN_NORMAL);
} else { // use relative error
    return diff / Math.min((absA + absB), Float.MAX_VALUE) < epsilon;
}

但如果知道精度,直接将其乘以10^n变成整数来比较是最佳的方法

CPP原子操作

无锁队列

atomic

      void
      store(__pointer_type __p,
        memory_order __m = memory_order_seq_cst) noexcept
      { return _M_b.store(__p, __m); }

      void
      store(__pointer_type __p,
        memory_order __m = memory_order_seq_cst) volatile noexcept
      { return _M_b.store(__p, __m); }

      __pointer_type
      load(memory_order __m = memory_order_seq_cst) const noexcept
      { return _M_b.load(__m); }

      __pointer_type
      load(memory_order __m = memory_order_seq_cst) const volatile noexcept
      { return _M_b.load(__m); }

      __pointer_type
      exchange(__pointer_type __p,
           memory_order __m = memory_order_seq_cst) noexcept
      { return _M_b.exchange(__p, __m); }

cpp实现

atomic::compare_exchange_weak

memory_order

  • memory_order_relaxed
  • memory_order_seq_cst

cmake预处理头文件

预处理头文件是cmake 3.16添加的新功能,可以将头文件先

Precompiling header files can speed up compilation by creating a partially processed version of some header files, and then using that version during compilations rather than repeatedly parsing the original headers.

mutex error

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

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。这个函数的注释说明了需要使用者确保调用前已初始化。

/* 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.
 */
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)

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最好要在线程启动前初始化

AppCache{
std::mutex
};
  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. 建立最大堆时,每次比较出最小值,一遍之后,堆顶为最小
  4. 比较到顶部节点时,完成第一次遍历,找到了顶部的最值
  5. 将堆顶的最值与尾部交换,遍历范围-1,然后从堆顶开始比较
  6. 重复3动作,直到范围为1

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

最大堆和最小堆

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

topK

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

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

// 使用最小堆来实现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);
}

使用方法

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统计,int表示出现次数,如果目标字符串,如问题2和问题3

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

{
  目标
  次数
}

总结

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