一、位图算法

概念：所谓的 BitMap 算法就是用一个 bit 位来标记某个元素所对应的 value；

举例：

现有 40 亿个整数，当给定一个新的整数时，判断新的整数在这40亿个数字中是否存在，假设该架构下整形为4个字节；

其实这个问题的性能点有两方面：

1. I/O 时间消耗；
2. 计算消耗（对比是否相等）；

假设 40E 个整数存储在磁盘中，也就是 40亿*4字节，约等于16GB。

1. 最常规的方法：

假设系统运行内存为2GB，每次新来一个数字就循环加载 16GB 进入系统，和新的整数进行对比。

这种方法每次来一个新的数字进行判断时，因为内存不够用，每次都需要 8 次 i/O 操作，且数据量巨大（2GB），时间上会达到小时级别；

最久时间消耗：8次I/O + 40E次对比运算；

2. 针对 I/O 进行优化之后的方法：

改进方法1，使用 8 个 2GB 运行内存的电脑加载 16GB 的数据，这样只需要并行加载，相当于只加载一次的时间，然后 8 台计算机对比新的整数，最后对结果进行汇总；

此时，因为 40E 个整数都已经被加载进入了内存，每来一个新的数字进行对比时，不需要再进行 I/O 操作，只需要在 8 台机器中并行对比即可；

最久时间消耗：1次I/O（一次性） + 40E/8 次对比运算；

上述两种方法的计算消耗比较高，接下来可以使用位图算法来针对计算消耗进行优化。

3. 位图算法：

int 为 4 个字节，范围为：-2147483648 ~ 2147483647，也就是4294967296个数字。使用一个 bit 也就是一个二进制位来代表一个数字，那么需要 4294967296 / 8 /1024 / 1024 / 1024 约等于 0.5 GB(bit->byte->kb->m->gb)。

也就是说，如果使用内存中一个二进制位来代表一个数字，那么只需要开辟 0.5G 的内存就可以表示所有的整数，此时将 int 类型的内存消耗转化成了 BOOL 类型的内存消耗，所以内存消耗缩小了 32 倍。

I/O 消耗仍然无法避免，但是一个整数在内存中的占用小了 32 倍，只需要一台机器，且不用循环 I/O 了。在内存中开辟 0.5G 内存之后，只需要循环读取 40亿 个数字，然后再内存中对应的 bit 位进行标记，也就是标记为 1，最后根据指定的整数，取出内存中偏移地址的比特位的值，如果为 1 则表示存在，否则反之。此时，计算消耗为 1 次；

最久耗时：1次I/O（一次性） + 1次位运算；

需要注意的是，加载 40E 个整数的 PageFault 和 I/O 之类的耗时都是无法避免的，同样数量和配置的机器下都是一样的。只不过使用位图的方式，计算量从 40E 次相等判断变成了一次位运算，而且对着 40E 个整数的内存存储从 16G 变成了 0.5G，这才是重点。不要想着 I/O 、存储 40E 个整数的文件在 I/O 是否支持并发读取，这样就想复杂了，这些不是重点；

二、绘图中的位图

1. 概念

用特定大小的内存空间来表示单个像素的色值，以逐行扫描的方式来来表示整张图片中所有的像素的色值；

在《计算机图形学基础第四版》中对 bitmap 的描述如下：

image.png

bitmap

总结一下其观点，针对帧缓存（Frame Buffer）而言：

1. 如果使用 1 个 bit 位来表示一个像素的色值，则此时帧缓存为位图；
2. 如果使用多个 bit 位来表示一个像素的色值，则此时帧缓存为像素图；

个人理解：其实，位图的概念已经没有那么拘泥于是否一定要使用 1 个比特位了。bitmap 的概念就是使用矩阵的方式来表示整体数据，以此来减少数据大小（算法）或则是实现某一目的（raster）。当然，严谨一点更好，所以 Frame Buffer 最好描述为 pixmap（像素图）；

2. 来历

从纯数学的角度，任何一个面都由无数个点组成。但从生理角度而言，人类的肉眼无法区分很小的点。所以在实际应用中，我们没有必要用无数个点来表示一张图片，甚至都没有必要使用足够多的点，只需要让点的个数和大小在人眼能区分的极限之上一点点就好了，如此就能在清晰度和节约内存之间达到平衡。

其一，是因为太多点，人眼也看不出来差别，这就是很多人觉得 2k、4k 好像和 1024*768 并没有太大差别的原因。

其二，使用无数点来表示一张图片是不可能的，使用很大数量的点是极其耗费资源的，性价比很低。

最终决定使用一定数量的点来表示一张图片，而这个点就是像素。而视频本质上时无数图片的连贯播放，因此像素成了图形科学的基础单位；

3. 显示器成像

显示器成像基本上是逐行扫描，如图所示：

逐行扫描

再根据上述的位图原理，位图算法可以极大节省空间或者是减少运算量。而像素的数量较多，假设有 1024*768 个像素点，像素点使用我们最常用的16 进制 RGB 来表示颜色，一个像素点有 256 * 256 * 256 种可能。假设一个 Int 类型占 4 字节，也就是 32 bit，那么一个像素点占用的内存空间就是：32 bit。而采用位图之后单个像素占用的存储空间为：8bit * 3 = 24 bit，节省的空间就是 24bit * 像素个数。

上述计算看上去节省的空间不大，甚至如果是 ARGB 的颜色，那么同样也是 32bit ，相比于使用 4 字节的 int 来存储，好像并没有太大优化，但是这里涉及到几个问题：

• 1. 透明度是否需要？
     大部分情况下的图片是不需要透明度的；
• 2. 颜色色值是否需要 256 * 256 * 256 种？
     除了 #FFFFFFFF 这种 32bit 带透明度的色值之外，其实还有很多色值，比如 RGB_888、ARGB_4444、RGB_655、灰度颜色等，这些色值占用的内存都是少于
• 3. 后期出现的 128bit 色值如何存储
     四个字节的 int 表示 24bit 色值就会存在空间浪费的情况，当色值进化到 128bit 时，采用更高的单位去存储色值也永远会存在这种浪费的情况，况且如果是 float 类型呢？所以这不是最终的解决办法。

综上，所以最终采用位图的方式来表示像素点。

多说几句废话加深理解：虽然屏幕成像是逐行扫描，但是色值在内存空间中的存储仍然是连续的。bitmap 中不仅存储像素，还会存储像素的基本信息，比如色域、图片宽高(也就是上文中所说的 1024 和 768)、压缩方式。通过这些信息就可以知道连续的内存地址上具体像素的位置。如 1024 * 768的 RGB 24bit 的图片，第二行的第一个像素的色值就大概存储在：第一个像素内存起始位置 + 1024 * 24bit 。这只是大概，其中还会有压缩、头信息的处理等等，这些就是 GPU 变成相关的了，不具体展开。

色域和色深

• 色域：色域表示可展示的颜色的范围，具体不展开，自行百度；

• 色深：图片未被压缩之前，每个像素点占多少位(bit)

• 位深：图片被压缩之后，每个像素占多少位(bit)；

压缩会在后文中讨论，这里从色深就可以很直观的知道，8bit 的图片必定没有 32bit 的图片颜色丰富。

还需要补充一个概念：通道

一般 ARGB 颜色就是 4个通道，分别是 透明度、R、G、B，每个通道都使用一定的位数来表示，比如 ARGB_8888 就是 4 通道，每条通道 8 bit。比如 8bit 的灰度颜色，只有黑白，属于单通道。

安卓和iOS中的色值

安卓中，使用 Config 表示每个像素点对 ARGB 通道值的存储方案：

ARGB_8888：每个通道值采8bit来表示，每个像素点需要4字节的内存空间来存储数据。该方案图片质量是最高的，但是占用的内存也是最大的；

ARGB_4444：每个通道都是4位，每个像素占用2个字节，图片的失真比较严重。一般不用这种方案。

RGB_565：这种方案RGB通道值分别占5、6、5位，但是没有存储A通道值，所以不支持透明度。每个像素点占用2字节，是ARGB_8888方案的一半。

ALPHA_8：这种方案不支持颜色值，只存储透明度A通道值，使用场景特殊，比如设置遮盖效果等。

比较分析：一般我们在ARGB_8888方式和RGB_565方式中进行选取：不需要设置透明度时，比如拍摄的照片等，RGB_565是个节省内存空间的不错的选择；既要设置透明度，对图片质量要求又高，就用ARGB_8888；

iOS 中常见的颜色为三种：

• 灰度
• RGB
• CMYK

iOS中的三种颜色

上述三种颜色，在设置 bitmap context 中的颜色时，又分为不同参数设置：

cs：color space
bpp：bit per pixel
bpc：bit per component

iOS颜色

iOS 中，因为 bitmap context 的坐标系和 view 的坐标系不通用，需要通过仿射变换来统一，所以系统不建议使用 bitmap context；一定要使用的话，会存在代码无法复用、性能问题、代码复杂度问题；所以 iOS 中如果需要画 bitmap，直接使用 startImage 相关的函数即可。另外，CALayer 本质也是画 bitmap，只不过系统使用了离屏渲染、缓存、复用机制；

常量的含义：

image.png

颜色布局：

颜色布局

压缩

图片的存储一般有两种形式：未加载进内存和加载进内存后；内存中都是以 bitmap 方式表达，非内存中，可以是 bitmap，也可以是各种压缩格式。其中，在内存中的 bitmap 格式称为实际大小；

• 有损压缩：删除颜色附近相近的颜色

特点：

1. 本质是删除，实际大小和存储大小都会减少，也就是存储在硬盘中的大小会减小，加载进内存之后的大小也会减小；
2. 压缩率过高时，图片失真会很严重；

• 无损压缩：同色值只存储一次，加载进内存后还原 bitmap；

特点：

1. 本质是存储优化，相当于有一个 map 表，记录该色值下所有像素的位置；
2. 存储大小会消减，但是加载进内存后的 bitmap 维持原大小；
3. 图片不会失真，但是节省的存储空间有限；

格式

图片格式一般有几种：

1. bitmap：保留最原本的像素信息，但是占用空间比较大；
2. JPEG/JPG：有损压缩；
3. PNG：无损压缩；
4. GIF：无损压缩，但是颜色范围只有 256 种，也就是色深是 8bit；
5. WBP：集大成者，支持无损和有损也支持 gif，且压缩之后的体积更小，但是压缩时间会变长；

JPEG 和 JPG 没有区别，全名、正式扩展名是JPEG。但因DOS、Windows 95等早期系统采用的8.3命名规则只支持最长3字符的扩展名，为了兼容采用了.jpg。

bitmap 的大小为：
size = width * height * bpp(bit per pixel)

平常我们见到的图片都是被压缩过后的图片，所以其大小会比 bitmap 格式的图片大小小很多；但是 PNG 格式的图片被加载进内存之后会被还原成全量 bitmap ，所以这也是很多重度使用图片的 app 的一个优化方向；

图元和位图的关系

图元文件并不是矢量图，因为它存储的并不是矢量信息。
它存储的是你在绘图的时候调用了哪些操作。
如果是位图文件记录了你的画布上每一点的颜色的话，
图元文件就是纪录的你如何下笔的。

bitmap 最终数据，被加载到 frame buffer (显存)后，直接由显示器加载数据并最终显示到屏幕上；