[toc]

红黑树

什么是红黑树

set/multiset 实现最大堆

在 STL 中，set 和 multiset 是基于红黑树实现的。

• Sets are usually implemented as red-black trees.
• Sorting is done using the key comparison function Compare. Search, removal, and insertion operations have logarithmic complexity.

Code 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
35
36
37
38
39
40
41
42
43
44
45
46

#include <iostream>
#include <ostream>
#include <set>

int main() {
  // Initialize a set.
  // Compare parameter is default to std::less<Key>.
  std::set<int> min_s;
  min_s.insert(1);
  min_s.insert(3);
  min_s.insert(2);
  min_s.insert(5);
  min_s.insert(4);
  min_s.insert(-1);

  std::cout << "min value of set container is " << *min_s.begin() << std::endl;
  std::cout << "max value of set container is " << *min_s.rbegin() << std::endl;

  // Compare parameter is default to std::greater<Key>.
  std::set<int, std::greater<int>> max_s;
  max_s.insert(1);
  max_s.insert(3);
  max_s.insert(2);
  max_s.insert(5);
  max_s.insert(4);
  max_s.insert(-1);

  std::cout << "max value of set container is " << *max_s.begin() << std::endl;
  std::cout << "min value of set container is " << *max_s.rbegin() << std::endl;

  // Initialize a multiset.
  std::multiset<int, std::greater<int>> max_ms;
  max_ms.insert(1);
  max_ms.insert(3);
  max_ms.insert(2);
  max_ms.insert(5);
  max_ms.insert(4);
  max_ms.insert(-1);

  std::cout << "max value of multiset container is " << *max_ms.begin()
            << std::endl;
  std::cout << "min value of multiset container is " << *max_ms.rbegin()
            << std::endl;

  return 0;
}

输出结果如下

1
2
3
4
5
6

min value of set container is -1
max value of set container is 5
max value of set container is 5
min value of set container is -1
max value of multiset container is 5
min value of multiset container is -1

参考 <剑指 offer> 面试题 40 — 最小的 k 个数

基于 STL 的函数 push_heap、pop_heap 和 vector 实现堆

参考 <剑指 offer> 面试题 41 — 数据流中的中位数

更改记录

2023.04.02 搭建架子，写出 set 版本。

[toc]

• The Python Standard Library
  • keep this under your pillow

[toc]

2023 年元旦假期，新冠疫情刚刚肆虐过，疫情的恐惧还没有消散。

作为率先走出家门的人，我们在西安逗游三天。我们去西安的初衷，是希望可以尽可能多地了解华夏五千年的历史，所以我们整个旅行的侧重点是历史遗迹和文物欣赏。

[toc]

2022 年 11 月末，北京疫情变得严重起来，我开始居家办公。这段时间省下来数个小时的通勤时间，使得自己能够利用晚上的时间，捧起《如何阅读一本书》。我的初步想法是希望阅读这本书可以教会自己如何更加高效读书，如何更好地理解和整理一本书，以及纠正自己阅读的一些坏习惯。

[toc]

ETF 简介

什么是 ETF ？

ETF 是英文 “Exchange Traded Funds” 的简称，常被译为 “交易所交易基金”。ETF 是一种在交易所上市交易的、基金份额可变的基金。ETF 结合了封闭式基金与开放式基金的运作特点，一方面，基金份额可以像封闭式基金一样在交易所二级市场进行买卖；另一方面，可以像开放式基金一样申购、赎回。 ETF 通常是以某一选定的指数所包含的成分证券为投资对象，依据构成指数的证券种类和比例，采用完全复制或抽样复制的方法进行被动投资的指数型基金。

这是一本 Kindle 上偏游记的快消书，我已经不记得阅读动机了。作者的辞藻华丽，文字优美，但是言语中透漏出年轻人固有的阅历尚浅，对生活的体验不深刻，仅仅是城市的过客。

自动驾驶是一个大工程，概念定义繁多，这篇文章做一下收集和整理。文中部分概念摘录自百度 Apollo 系统公众号，并以 Apollo 系统为例进行概念讲解。

背景

在 Linux 系统上编译大型程序时，可能遇到如下编译错误：

1
2

c++: internal compiler error: Killed (program cc1plus)
Please submit a full bug report

经过查资料，大概率是编译时内存不够导致的，除了增加物理内存外 (花银子)，短期可以通过增加交换分区 swap 来解决 (时间换空间)。

[toc]

挂载点与设备的关系

linux 下面所有的文件、目录、设备都有一个路径，这个路径永远以 / 开头，用 / 分隔。

通过 mount，可以设置当前的路径与设备的对应关系。每个设备会设置一个挂载点，挂载点是一个空目录。一般来说必须有一个设备挂载在 / 这个根路径下面，叫做 rootfs。其他挂载点可以是 /tmp，/boot，/dev 等等，通过在 rootfs 上面创建一个空目录，然后用 mount 命令就可以将设备挂载到这个目录上。挂载之后，这个目录下的子路径，就会映射到被挂载的设备里面。同一个设备可以有多个挂载点，同一个挂载点同时只能加载一个设备。

文件系统挂载时有覆盖（/ 遮盖）关系，如果你所要挂载的挂载点（/ 目录）下面有文件或已挂载的文件系统，那么新挂载的文件系统会遮盖其下面的内容。这也就是挂载点为什么必须是空目录的原因了。

设备挂载

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

# 查询磁盘信息
# fdisk: Display or manipulate a disk partition table
sudo fdisk -l
# 创建挂载点
cd /home/用户名
mkdir 文件夹名称
# 查询挂载硬盘(以 /dev/sda 为例，后面的 /dev/sda 均指想挂载的硬盘)的 UUID、type 等信息
sudo blkid /dev/sda
  # 通常返回如下格式
    /dev/sda: UUID="8e33e89c-xxx-7a3f08ed0db6" TYPE="ext4"
  # 如果在使用 blkid 没有返回结果，或者未显示 TYPE="ext4"，表示这个硬盘还没有分区或者没有格式化
# 如果未格式化需要先格式化分区（使用ext4文件系统，mkfs.exe4 的命令对分区进行格式化）
sudo mkfs.ext4 /dev/sda
# 修改开机挂载硬盘文件
sudo vi /etc/fstab
# 在 /etc/fstab 文件最后新增：
# 第一列为 UUID, 第二列为挂载目录（该目录必须为一个空白目录），第三列为文件系统类型，第四列为参数，第五列0表示不备份，最后一列必须为２或0(除非引导分区为1)
UUID="f652d9d2e-02"（上面查询的UUID） /home/用户名/文件夹名称(上面创建的挂载点) ext4 defaults 0 2
# 执行命令进行挂载
sudo mount -a
# 查看硬盘是否正常挂载。
df -h

异常情况

如果挂载硬盘后，重启系统后异常，比如在登录界面循环登录，无法进入可视化界面；这可能是 /etc/fstab 文件配置错误，删除刚才添加的内容可以恢复正常。

• shift+alt+F2 可以进入 tty2 命令行界面，通过命令行方式操作。

[toc]

本文是香港科技大学的研究结果，发表于 ICRA 2020。

作为一个自动驾驶的研发人员，通篇读下来认为这篇论文研究在实际工程应用中价值比较低。如果非学术原因，不建议深度研究。

其一，文章的亮点是自车策略选择，现在比较成熟的技术路线是 spatial-temporal planner 方案；

其二，原本吸引我的 POMDP 和 多物体交互，在文章中却被略写，没有深度。周围车辆的意图是受到自车未来行为决策影响的，所以存在一定的不确定性，如何评估这部分不确定性，如何判断对方车是否有合作意图，这部分难点问题也没有深入研究。

因为后续的精力有限，自己不会再对阅读的论文进行整理，但是我会逐渐整理并分享一个自动驾驶进阶学习资料。