Halt in Air

Lay burdens down and travel light!

二维凸包检测

Graham扫描法与Jarvis步进法

1. 定义 在一个实数向量空间 V 中，对于给定集合 X，所有包含X的凸集的交集 S 被称为 X 的凸包（Convex Hull）。 2. 算法 2.1 蛮力法 时间复杂度 ：O(n³） 思路 1. 将点集里面的所有点两两配对，组成 n(n-1)/2 条直线。 2. 对于每条直线，再检查剩余的 (n-2) 个点，若都在直线的同一侧，则这两个点是凸包上的点 给定 $P_1(x...

Posted by Max on June 22, 2017

初识红黑树

basic knowledge of Red-Black tree

阅读笔记。原文传送门 1. 概念 1.1 二叉查找树 红黑树本质上就是一棵二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree），排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若任意结点的右子树不空，则右子...

Posted by Max on May 30, 2017

NBSP是什么

What is NBSP?

问题描述 一个 C 程序在 ini 格式配置文件解析过程中出现问题，添加的配置项不生效。而配置文件看起来并无异常（配置从 pdf 文档中粘贴而来）。 根源探究 调试发现，程序在空格处理上出现问题。将配置文件转换为二进制格式后，终于发现问题所在。 Dec Hex Char Octal Raw encoding...

Posted by Max on April 24, 2017

linux内核PID管理

management of PID in linux kernel

1. 概念 什么是 PID ？ PID 是内核内部对进程的一个标识符，用来唯一标识一个进程（task）、进程组（process group）、会话（session）。PID 及其对应进程存储在一个哈希表中，方便依据 PID 快速访问进程 task_struct。 因此Linux 内核在设计管理ID的数据结构时，要充分考虑以下因素： 如何快速地根据进程的 task_struct、...

Posted by Max on March 22, 2017

算法设计技术基础

分治、动态规划、贪心、回溯 归纳笔记

前一段时间回顾了算法设计与分析， 现对分治、动态规划、贪心、回溯四种基础算法设计技术做一个归纳。 1. 分治策略 1.1 适用条件 原问题能够规约为独立求解的子问题。 1.2 主要步骤 将原问题规约为独立求解的子问题。注意子问题要划分均衡，且与原问题性质相同。 计算初始子问题。 综合子问题的解，得到原问题的解。 1.3 简单实例 快速排序是分治策略的典型应用。 ...

Posted by Max on February 2, 2017

C++内存分配之堆栈

记一次栈越界错误

问题描述 使用bitset时碰到一个问题，进程在bitset构造那里core dumped。源码如下： #include <bitset> int main () { std::bitset<0xffffffff> foo; foo.reset(); return 0; } 使用dmesg查询，得到信息如下： a.out[21521...

Posted by Max on January 24, 2017

do_fork浅析

do_fork浅析 一般创建一个进程我们需要调用fork函数，fork其实又是调用了clone函数来实现的，而clone函数中最关键的函数就是do_fork函数。 1. do_fork() do_fork定义在kernel/fork.c文件中，一言不合上代码—— /* * Ok, this is the main fork-routine. * * It copies the ...

Posted by Max on November 21, 2016

进程描述符

进程描述符 若要理解进程如何被内核创建，需要先知道进程在内核中被抽象成了什么——进程描述符（task_struct）。 Linux内核通过task_struct结构体来管理进程，这个结构体包含了一个进程所需的所有信息，是一个相当复杂的数据结构。它定义在include/linux/sched.h文件中。 此处挑选一些常用信息进行说明。 1. 进程状态 volatile long ...

Posted by Max on October 21, 2016

进程和线程

进程和线程 1 差异 进程（process）和线程（thread）是操作系统的基本概念。书面的讲，进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的一个独立单位，具有资源独立、主从分明的特点；而线程是进程的一个实体，是CPU调度和分派的基本单位，是比进程更小的能独立运行的基本单位。线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源(如程...

Posted by Max on October 7, 2016

FEATURED TAGS
design patterns protocol linux algorithms
Search
    ABOUT ME

    世界那么大，我想多看看。