给楼主点赞

https://forums.huaren.us/showtopic.html?topicid=2573159&fid=398&page=30

从这里开始。Leetcode读书笔记。

本来是发chats；不过，有点不合适。放这里吧。

友情支持

谢潮水。军功章有你的一半

你在原帖的评论我会汇总加过来。现在正在和concurrency的leetcode奋斗，tree的搞定，这个周末写notes。

我的第二份工作，是在Linux kernel mode device driver。大系统里面，16 computing blades，每个blades上面4个CPU complex，每个CPU若干个core，还有hyper thread。每个thread齐头并进，有时候需要lock。一个CPU里面的lock，用semephore/mutex可以解决；不同blades之间的lock，必须靠硬件支持的atomic transaction。这个特殊硬件需要的device driver，就是我们小组负责。

今天的leetcode，随便看了concurrency的topic，做了几个题目；refresh memory也学新东西。潮水说的，c++17。那就从这几个lock开始吧。（有的是c++11）。说错了由潮水老师补充（）

1. lock_handle
2. unique_lock
3. scope_lock

lock_handle(mutex): 一直blocking，直到mutex available。不需要unlock。从当前程序/section{} 退出的时候，自动release。工作中，我一般用这个。

unique_lock（）：支持unlock。比lock_handle 灵活。用condition_variable的时候，必须用它。condition_variable（unique_handle, condition）相当于”only when condition is true, do we try to lock"。这样可以直接把checking写入lock。当程序从这里退出，condition is true，plus the lock is obtained. 当然必须记住：需要unlock later。

scope_lock: 属于c++17。对于多个mutex一起lock。如果用以前的stand_lock，需要考虑multi-lock的顺序，极其容易deadlock。这个scope_lock很方便。

常见的用法，当然是multi-thread 情况了。

https://en.cppreference.com/w/cpp/thread/scoped_lock

几个points：

1. lock_guard wrapped in {}, only effective inside this code section.
2. scoped_lock works with multiple locks, grabbing them atomically.
3. threads use emplace_back rather than push_back. This is a performance improvement, reduced from construction & copy into in-place construction.

Graph Theory

常见的Tree，属于Graph的一个特殊分类。Tree在leetcode里面有tag，可以专门挑tree类的题目做。

Grid，尤其是2D grid，也是Graph的一个表达方式。扫地机器人的navigation，一般用Grid形式表达map。

Navigation算法里面，A*（和它的变种，Dixxxx）是weighted navigation的普遍算法。无人驾驶的navigation，或者circuit自动连线的算法，都是A*。A* 是 Dijkastra 的加速版，加上 heuristic cost。

Robotics 里很多是用 hybrid A*，因为 quasi continuously differentiable 的要求，law of physics。

Mapping算法里面，RRT是Robotics领域经常用的。RPM（PRM？）用的也多。

我工作的方向是这个，所以我以为我对graph theory和里面的题目应该没有问题；结果，，，我错了！

加上一个Youtube link，里面的解释不错。

[url]https://www.youtube.com/watch?v=DgXR2OWQnLc&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P[/url]

如果要去control 组，A*只怕是必考；去network组，minmax flow估计是必考；去path planning，那就是TSP，traveling of a salesman.

潮水如果以后想走Robotics，告诉你，Jacobian Matrix那就是必考必考题！还有，空间旋转的4个表达方式。

leetcode pace, 差不多20个easy 一天，10个medium勉强。

Summary 算法的用途 scenarios：

1. DFS 的用处，是finding connection。例如，find center (the nodes with the most levels); find weakest link (same as finding isolated islands).
2. BFS: is about to find path.

潮水哥说： BFS / DFS / Best-First-Search 其实可以用同一种写法，差别只是 DFS 用 LIFO ，BFS 用 FIFO，Best-First-Search 用 cost-based-heap (priority queue) 。。。 其它部分写法一样一招鲜吃遍天。

不过工业界里，大尺寸或者 High performance low latency 的 DFS，一般也避免写成递归函数，因为避免递归的 overhead 以及系统栈的尺寸限制。

Common data structures for Graph representation:

1. unordered_map<int, vector<int>>: the benefit is the key part can be used directly as index to the map
2. vector<vector<int>>: representing individual edge, typically requiring to translate this into unordered_map
3. vector<vector<int>> as a matrix[n.m]: huge waste of memory, but typically used for grid situation.
4. TreeNode/left/right: most commonly used in leetcode

潮水哥又说： std::push_heap() 是 O(log(N))

std::sort() 是 O(N*log(N))

除非 problem size 很小，或者 implementation 有问题，否则 heap (priority queue 的底层实现) 应该更快。

你如果做工业界的 high-performance / low-latency programming, 看具体应用，有些应用要避免用 std::priority_queue，考虑直接用 std::push_heap() / std::pop_heap() 在 std::vector 上，因为这样可以事前 std::vector::reserve() 以及避免 vector realloc ... 还有就是可以保持 std::vector allocated space persistent 来避免 loading time.

另外 std:: priority_queue 的底层也可以是 std::deque。。。但 std::deque 对于大尺度问题，RandomAccessIterator 会有附加 overhead 。

对于 pre-sorted but algorithm do not know it is pre-sorted，std::sort() 会快一些，但咋都比不过 std::push_heap() 否则香浓的 paper 药丸 。。。

当然 heap 的最大价值在于 std::push_heap() 和 std::pop_heap() 对称美 。。。 如果你的应用都是 batch push 一次给我来一百打然后我一个一个 pop 的这种比较极端情况，另说。