计算直方图的一般步骤如下。

（1）计算数据的最大值和最小值，得到极差，即数据的最大值减去最小值。

（2）确定直方图的组数，然后以此组数去除极差，可得到直方图每组的宽度，即组距。

（3）确定各组的界限值，分组时应把所有的数据表都包括在内。

（4）统计各组的频数。

当数据量比较小时，每次执行计算的时间很短，用户可以连续变换显示粒度，切换到感兴趣的区间，而没有明显的停顿感觉，但数据量增大，计算时间变长，使用体验就会下降。对于存在分布式存储系统的大数据，每次计算需要用几分钟才能看到新的直方图结果。

对于大数据，能否用最少的数据读取量给用户流畅的直方图查看功能？答案是肯定的，而且数据仅读取一次！

新算法的核心思想是：计算一个粒度非常小的直方图（称为基本直方图），每次用户的直方图计算请求都会变成将基本直方图的若干相邻区间合并为一个新的显示区间。

新算法分如下两个部分。

通过自适应的方式读取一遍数据，得到基本直方图。

由基本直方图计算不同区间和不同粒度的直方图。

下面将详细介绍这两部分内容。

1．计算基本直方图

在计算基本直方图时，首先要确定基本直方图的建议组数，建议组数并不是要求计算出来的基本直方图的组数与其完全相等，而是希望在一个量级上。实际的计算中，建议组数常取10000，得到的基本直方图的分组数会在10000和100000之间。

然后关注另一个重要问题：数据只读取一遍。在一般的直方图算法中，需要统计读取一遍数据，得到极差（最大值减去最小值），才能确定数据范围和组距，然后需要再读取一遍数据，得到结果。若数据只能一次读取，需要去掉事先计算数据范围和组距这一步，通过当前已读取的数据，确定当前的数据范围和组距，在增加新数据时，自适应地调整数据范围和组距。

若要做到自适应，组距的选取很关键。不断新增数据时，数据范围也会不断变大，组数会超过我们可以处理的个数，这时就要通过增大组距的方式，将组数降下来。这个增大的新组距一定要是原来组距的整数倍，这样，某个新分组的数据个数是若干个小分组的数据个数的加和；新组距还要考虑到分组边界为比较整齐的数，例如：0.1、0.002、1、100等，这样符合用户一般的习惯。对数值型的数据，我们选取基本组距为10𝑘，其中的k为整数，新的组距一定为原组距的10𝑚倍，其中的𝑚为正整数。

自适应基本直方图计算的步骤如下。

（1）设定建议组数𝑁。

（2）读取一个或若干个数据，建立一个初始分组。

（3）读取新的数据（一个或多个）。

（4）如果现在的区间划分不能包含全部的新数据，则需要按如下步骤进行调整。

1）组距不变，增加分组个数，使之能包含全部新的数据。

2）若分组个数超过10𝑁，则需对组距升级（乘以10、100、1000…），同时也要调整区间划分的左边界，使之为新组距的倍数，最终得到的新区间划分要满足：分组个数大于或等于𝑁，且小于10𝑁，并确定每个新分组的频数。

（5）判断每个新数据所属的分组，增加相应分组的频数。

（6）若还有数据需要处理，则回到第（3）步。

（7）得到基本直方图的区间划分和频数。

注：可以使每次获取的新的数据量多一些，从而减少区间划分调整的次数，提高运行效率。
举例：对于分组[10,10.1),[10.1,10.2),[10.2,10.3),⋯,[99.9,100)，相应的频数为{2,2,2,⋯,2}，建议组数N=10。下面我们读取新的数据，并相应地调整分组和频数。

（1）读到一个新数据10.15，因为它属于已有的区间[10.1,10.2)，则分组不变，相应的频数为{2,3,2,⋯,2}。

（2）再读到一个新数据9.85，则分组需要增加[9.8,9.9)和[9.9,10)，其中，[9.9,10)是因为直方图的区间是连续的，而增加的空区间最终的分组为[9.8,9.9),[9.9,10),[10,10.1),[10.1,10.2),[10.2,10.3),⋯,[99.9,100)，相应的频数为{1,0,2,3,2,⋯,2}。

（3）再读到一个新数据-1.0，则分组需要按102升级为[0,10)[10,20)[20,30)⋯[90,100)，相应的频数为{1,201,200,⋯,200}；然后增加[−10,0)，最终的分组为［−10,0）,［0,10）,［10,20）［20,30）,…,［90,100），相应的频数为{1,1,201,200,⋯,200}。

对于分布式计算，每个计算节点都会负责处理一部分数据，可执行上面的自适应算法得到各部分数据的基本直方图划分，然后，我们需要一个汇总过程，得到对于全部数据的基本直方图划分，计算步骤如下。

（1）获取各部分数据基本直方图划分的左右边界，比较得出左边界的最小值和右边界的最大值，将它们作为全部数据的取值范围。

（2）根据此全部数据的取值范围，及建议组数𝑁，计算出针对全部数据的组距，从而得到对于全部数据的区间划分。

（3）对每部分的数据基本直方图划分，将其每个分组位置和频数汇总加入到全部数据区间划分中的对应分组。

（4）经过上面三步，得到全部数据基本直方图的区间划分和频数。

2．按需要的区间和粒度生成直方图

在实际计算中，我们通常选取建议的组数为10000，计算出的基本直方图会有几万个分组，用户无法直接从中获得信息，还需以直方图的方式展示出来，展示的内容如下。

用户可以选择一个感兴趣的数据范围，默认为全体数据。

默认的显示一般是显示十几个区间，每个区间包含的基本区间个数要尽量相等。

在当前绘图的精度下，最细粒度的显示。

可以进行更细粒度或更粗粒度的显示，即放大（zoom in）和缩小（zoom out）效果。

按用户输入的粒度进行展示。

对于长尾类型的，可以选择不显示某些区间，便于查看那些频数小的区间。

显示的每个区间所包含的频数，及在当前显示范围内所占总频数的百分比。

上面的各种操作最终都会转化为这样一个问题：对于一个建议左边界值、建议右边界值和建议步长，求显示直方图。

具体计算步骤如下。

（1）计算显示步长，它需要满足两个条件：是基本直方图的组距的正整数倍，等于或接近建议步长。

（2）计算显示左边界，同样要满足两个条件：是显示步长的整数倍，等于或小于建议左边界值。

（3）计算显示右边界，同样要满足两个条件：是显示步长的整数倍，等于或大于建议右边界值。

（4）由显示步长、显示左边界和显示右边界，得到显示区间划分。

（5）对每个显示区间，计算属于该区间的基本直方图分组的频数和，作为该显示区间的频数。

（6）输出整个显示区间划分和频数。