[译]All About Thread-Local Storage

线程本地存储(TLS)提供了一种为不同线程分配不同对象的机制。它是GCC扩展__thread、C11 _Thread_local和C++11 thread_local的通常实现,它们允许使用声明的名称来指代与当前线程相关的实体。本文将详细描述ELF平台上的线程本地存储,并触及其他相关话题,如:线程特定数据键和Windows/MacOS TLS。

阅读更多

冒号课堂笔记

编程语言与编程范式

范式译自英文的paradigm,也有译作典范、范型、范例的。所谓编程范式(programming paradigm),指的是计算机编程的基本风格或典范模式,是编程者在其所创造的虚拟世界中不自觉采用的世界观和方法论。每种范式都引导人们带着特有的倾向和思路去分析和解决问题。OOP就是一种范式。

阅读更多

贪心算法基础-2

本文继续介绍重要的贪心算法,比如哈夫曼编码、最小生成树等算法。

最优前缀码及哈夫曼编码

二元前缀码

二元前缀码:用0-1字符串作为代码表示字符,要求任何字符的代码都不能作为其它字符代码的前缀。

非前缀码的例子

a: 001, b: 00, c: 010, d: 01

解码的歧义,例如字符串0100001

  • 解码1:01,00,001     \implies d,b,a

  • 解码2:010,00,01     \implies c,b,d

阅读更多

先进的数据结构—持久性数据结构

Temporal data structures:

  • persistent data structures

    保存过去状态的全部信息。

  • retroactive data structures

The Pointer Machine Model

A pointer machine is an “atomistic” abstract computational computational machine model akin to the random-access machine.

阅读更多

贪心算法基础

本文开始记录贪心算法的学习。

贪心算法的例子——活动选择问题

输入:S={1,2,...,n}S=\{1,2,...,n\}nn项活动的集合,sis_ifif_i分别为活动ii的开始和结束时间。

活动iijj相容     sifj\iff s_i \ge f_jsjfis_j \ge f_i

求:最大的两两相容的活动集AA

阅读更多

线程

与进程近似,线程是允许应用程序并发执行多个任务的一种机制。如下图所示,一个进程可以包含多个线程。同一个程序的所有线程均会独立地执行相同的程序,且会共享统一份全局内存区域,包括初始化数据段(initialized data)、未初始化数据段(uninitialized data)以及堆内存段(heap segment)。

阅读更多

分治策略-卷积

卷积及其应用

向量计算

给定向量:

  • a=(a0,a1,...,an1)a=(a_0, a_1, ..., a_{n-1})

  • b=(b0,b1,...,an1)b=(b_0, b_1, ..., a_{n-1})

向量和: a+b=(a0+b0,a1+b1,...,an1+bn1a+b=(a_0+b_0,a_1+b_1,...,a_{n-1}+b_{n-1}

阅读更多

堆与栈

进程内存布局

如下图所示,对于每个程序所分配的内存由很多部分组成,通常称之为“段”(segment)。

  • 文本段(text)包括进程运行的程序机器语言指令。文本段具有只读属性,以防止进程通过错误指针意外修改自身指令。

  • 初始化数据段(BSS)包括为未进行显式初始化的全局变量和静态变量。

    对于初始化和未初始化数据段即用户初始化数据段(user-initialized data segment)和零初始化数据段(zero-initialized data segment)。

  • 栈(stack)是一个动态增长和收缩的段,由栈帧(stack frames)组成。系统会为每个当前调用的函数分配一个栈帧。栈帧中存储了函数的局部变量(所谓自动变量)、实参和返回值。

  • 堆(heap)是可在运行时(变量)动态进行内存分配的一块区域。堆顶端成为program break。

阅读更多