Luyu Huang's Tech Blog

我最近做到一道比较难的 Hard 题目. 这道题综合性比较高, 也比较抽象, 但是越琢磨越觉得有意思, 值得分享一下. 涉及到的知识点有图论基础, 拓扑排序, 并查集等, 本文假设你已经比较熟悉它们. 问题来自 LeetCode 1632 题. 给定一个 M * N 的矩阵 matrix, 返回一个新的矩阵 ans, 其中 ans[i][j] 是 matrix[i][j] 的秩(rank). 这里的秩不同于线性代数中的秩. 每个元素的秩是一个整数, 表示它与其它元素之间的关系. 它是这样计算的: 秩是从 1 开始的一个整数. 如果两个元素 p 和 q 处于同一行或同一列, 那么 如果 p < q, 那么 rank(p) < rank(q...

2022 is a bit tough for many of us. The pandemic disturbed many people's life. The Chinese internet industry is not that prosperous in the year: many companies layoffs and many people are unemployed, many game projects were aborted due to suspended issued publishing licenses, many companies' share prices fell, and so on. I was infected with COVI...

tcpdump 是一个很实用的抓包工具. 一直以来我都只是复制网上的常用命令, 对其使用逻辑缺乏理解. 最近我仔细阅读了它的 manual, 总结一下 tcpdump 的用法. 命令格式 如果使用 tcpdump --help 查看它的使用方法, 总是会得到一大堆参数选项, 至于如何使用还是一头雾水. tcpdump 的用法实际是这样的: $ tcpdump [选项] [表达式] tcpdump 会读取网络中的数据, 解析协议, 然后与表达式相匹配. 如果能匹配上, 则用指定的方式输出数据包的内容. 选项则用于指定如何从网络中读取数据 (如指定网络接口) 以及如何输出抓取到的数据. 在深入了解选项和表达式语法前, 先看个简单的例子. 选项 -A 表示用 ASCII 以文本的...

前一篇文章中我们讨论了 C++ 中原子变量的内存顺序, 现在我们来看看原子变量和内存顺序的应用 – 无锁队列. 本文介绍单写单读和多写多读的无锁队列的简单实现, 从中可以看到无锁数据结构设计的一些基本思路. 何谓无锁 为了实现一个线程安全的数据结构, 最简单的方法就是加锁. 对于队列来说, 应该对入队和出队操作加锁. template <typename T> void queue::push(const T &val) { std::lock_guard<std::mutex> guard(m_lock); auto node = new node(val); ... } template <typename T&...

C++11 将多线程纳入了标准. 一旦涉及到多线程, 就需要考虑并发, 数据竞争 (date race), 线程同步等问题, 为此 C++ 提供了互斥锁 std::mutex, 原子变量 std::atomic 等标准库. 对于原子变量的操作, 有一个很重要的概念就是内存顺序 (memory order), 其中涉及到的概念很多, 理解起来可能会有些困难. 本文我们来谈谈这个话题. 本文可能有些长, 涉及到的概念有些多. 其中 3.4 节和 3.5 节标注了星号, 它们的实际应用较少, 不感兴趣的同学可以先跳过, 或者读完全文后再阅读. 1. 原子变量 我们不能在两个线程中同时访问修改一个变量, 这会导致数据竞争的问题. 程序的结果是未定义的. 从实现上来说, 我们不能保证读写操...

C++ 用关键字 const 标识一个类型不可变. 这其实很容易理解. 不过, 对于 C++ 而言, 简单的概念也有很多可以讨论的. 我们来看一个问题. 问题 我们知道 const 可以用于修饰成员函数, 标识这个函数不能修改这个类的数据. 假设一个类有一个指针类型的成员 T *p, 我们希望通过 get() 方法获取 p 所指向的对象的引用. 如果 get() 被 const 修饰, 它应该返回什么类型, 是 T& 还是 const T& 呢? class C { public: ??? get() const { return *p; } private: T *p; }; 可能很多同学很自然地认为应该返回 const T&, 因为...

动态规划规划是一种很常见的算法. 它的思路基本上是将大问题转化成小问题, 大问题依赖小问题的结果. 常见的动态规划有一维动态规划, x = N 的问题可能依赖 x = N - 1 的问题 这样只要我们知道 x = 0 的问题的解, 就能逐步推出 x = N 的问题的解. 或者有二维动态规划, x = N, y = M 的问题可能依赖 x = N - 1, y = M 和 x = N, y = M - 1 的问题. 这样我们也可以从 x = 0, y = 0 的问题的解逐步推出 x = N, Y = M 的问题的解. 但有一类特殊的动态规划, 子问题之间的依赖关系是网状的 如果把子问题看作节点, 依赖关系看作边, 整个问题就可以看作一个无向图. 如果这个图没有环路, 那...

gperftools 是谷歌推出的一套非常强大的性能分析工具集. 它主要有这三个功能: 分析 CPU 性能, 能够统计出一段时间内各个函数的执行时间, 帮助我们找出耗时的代码; 分析内存占用情况, 能够统计出某一时刻各个函数分配的内存大小, 帮助我们找出内存占用高的代码, 也能帮助我们定位内存泄露; 自动检查内存泄露. gperftools 还包含一个高性能内存分配器 tcmalloc, 我们可以用它代替 glibc 的 ptmalloc. tcmalloc 自带统计功能, 内存分析和检查内存泄露就靠它. 本文介绍 gperftools 在 Linux 下的一些常见的用法. 如果你需要使用 gperftools 分析 Linux (服务器) 程序, 这篇文章可以当...