火龙果软件-海量数据处理小结

第一篇：火龙果软件-海量数据处理小结

火龙果整理 uml.org.cn

海量的数据处理问题，对其进行处理是一项艰巨而复杂的任务。原因有以下几个方面：

一、数据量过大，数据中什么情况都可能存在。如果说有10条数据，那么大不了每条去逐一检查，人为处理，如果有上百条数据，也可以考虑，如果数据上到千万级别，甚至过亿，那不是手工能解决的了，必须通过工具或者程序进行处理，尤其海量的数据中，什么情况都可能存在，例如，数据中某处格式出了问题，尤其在程序处理时，前面还能正常处理，突然到了某个地方问题出现了，程序终止了。

二、软硬件要求高，系统资源占用率高。对海量的数据进行处理，除了好的方法，最重要的就是合理使用工具，合理分配系统资源。一般情况，如果处理的数据过TB级，小型机是要考虑的，普通的机子如果有好的方法可以考虑，不过也必须加大CPU和内存，就象面对着千军万马，光有勇气没有一兵一卒是很难取胜的。

三、要求很高的处理方法和技巧。这也是本文的写作目的所在，好的处理方法是一位工程师长期工作经验的积累，也是个人的经验的总结。没有通用的处理方法，但有通用的原理和规则。那么处理海量数据有哪些经验和技巧呢，我把我所知道的罗列一下，以供大家参考：

一、选用优秀的数据库工具现在的数据库工具厂家比较多，对海量数据的处理对所使用的数据库工具要求比较高，一般使用Oracle或者DB2，微软公司最近发布的SQL Server 2005性能也不错。另外在BI领域：数据库，数据仓库，多维数据库，数据挖掘等相关工具也要进行选择，象好的ETL工具和好的OLAP工具都十分必要，例如Informatic，Eassbase等。笔者在实际数据分析项目中，对每天6000万条的日志数据进行处理，使用SQL Server 2000需要花费6小时，而使用SQL Server 2005则只需要花费3小时。

二、编写优良的程序代码处理数据离不开优秀的程序代码，尤其在进行复杂数据处理时，必须使用程序。好的程序代码对数据的处理至关重要，这不仅仅是数据处理准确度的问题，更是数据处理效率的问题。良好的程序代码应该包含好的算法，包含好的处理流程，包含好的效率，包含好的异常处理机制等。

三、对海量数据进行分区操作对海量数据进行分区操作十分必要，例如针对按年份存取的数据，我们可以按年进行分区，不同的数据库有不同的分区方式，不过处理机制大体相同。例如SQL Server的数据库分区是将不同的数据存于不同的文件组下，而不同的文件组存于不同的磁盘分区下，这样将数据分散开，减小磁盘I/O，减小了系统负荷，而且还可以将日志，索引等放于不同的分区下。

四、建立广泛的索引对海量的数据处理，对大表建立索引是必行的，建立索引要考虑到具体情况，例如针对大表的分组、排序等字段，都要建立相应索引，一般还可以建立复合索引，对经常插入的表则建立索引时要小心，笔者在处理数据时，曾经在一个ETL流程中，当插入表时，首先删除索引，然后插入完毕，建立索引，并实施聚合操作，聚合完成后，再次插入前还是删除索引，所以索引要用到好的时机，索引的填充因子和聚集、非聚集索引都要考虑。

五、建立缓存机制当数据量增加时，一般的处理工具都要考虑到缓存问题。缓存大小设置的好差也关系到数据处理的成败，例如，笔者在处理2亿条数据聚合操作时，缓存设置为100000条/Buffer，这对于这个级别的数据量是可行的。

六、加大虚拟内存如果系统资源有限，内存提示不足，则可以靠增加虚拟内存来解决。笔者在实际项目中曾经遇到针对18亿条的数据进行处理，内存为1GB，1个P4 2.4G的CPU，对这么大的数据量进行聚合操作是有问题的，提示内存不足，那么采用了加大虚拟内存的方法来解决，在6块磁盘分区上分别建立了6个4096M的磁盘分区，用于虚拟内存，这样虚拟的内存则增加为 4096*6 + 1024 = 25600 M，解决了数据处理中的内存不足问题。

七、分批处理 海量数据处理难因为数据量大，那么解决海量数据处理难的问题其中一个技巧是减少数据量。可以对海量数据分批处理，然后处理后的数据再进行合并操作，这样逐个击破，有利于小数据量的处理，不至于面对大数据量带来的问题，不过这种方法也要因时因势进行，如果不允许拆分数据，还需要另想办法。不过一般的数据按天、按月、按年等存储的，都可以采用先分后合的方法，对数据进行分开处理。

八、使用临时表和中间表数据量增加时，处理中要考虑提前汇总。这样做的目的是化整为零，大表变小表，分块处理完成后，再利用一定的规则进行合并，处理过程中的临时表的使用和中间结果的保存都非常重要，如果对于超海量的数据，大表处理不了，只能拆分为多个小表。如果处理过程中需要多步汇总操作，可按

火龙果整理 uml.org.cn

汇总步骤一步步来，不要一条语句完成，一口气吃掉一个胖子。

九、优化查询SQL语句在对海量数据进行查询处理过程中，查询的SQL语句的性能对查询效率的影响是非常大的，编写高效优良的SQL脚本和存储过程是数据库工作人员的职责，也是检验数据库工作人员水平的一个标准，在对SQL语句的编写过程中，例如减少关联，少用或不用游标，设计好高效的数据库表结构等都十分必要。笔者在工作中试着对1亿行的数据使用游标，运行3个小时没有出结果，这是一定要改用程序处理了。

十、使用文本格式进行处理对一般的数据处理可以使用数据库，如果对复杂的数据处理，必须借助程序，那么在程序操作数据库和程序操作文本之间选择，是一定要选择程序操作文本的，原因为：程序操作文本速度快；对文本进行处理不容易出错；文本的存储不受限制等。例如一般的海量的网络日志都是文本格式或者csv格式（文本格式），对它进行处理牵扯到数据清洗，是要利用程序进行处理的，而不建议导入数据库再做清洗。

十一、定制强大的清洗规则和出错处理机制海量数据中存在着不一致性，极有可能出现某处的瑕疵。例如，同样的数据中的时间字段，有的可能为非标准的时间，出现的原因可能为应用程序的错误，系统的错误等，这是在进行数据处理时，必须制定强大的数据清洗规则和出错处理机制。

十二、建立视图或者物化视图视图中的数据来源于基表，对海量数据的处理，可以将数据按一定的规则分散到各个基表中，查询或处理过程中可以基于视图进行，这样分散了磁盘I/O，正如10根绳子吊着一根柱子和一根吊着一根柱子的区别。

十三、避免使用32位机子（极端情况）目前的计算机很多都是32位的，那么编写的程序对内存的需要便受限制，而很多的海量数据处理是必须大量消耗内存的，这便要求更好性能的机子，其中对位数的限制也十分重要。

十四、考虑操作系统问题海量数据处理过程中，除了对数据库，处理程序等要求比较高以外，对操作系统的要求也放到了重要的位置，一般是必须使用服务器的，而且对系统的安全性和稳定性等要求也比较高。尤其对操作系统自身的缓存机制，临时空间的处理等问题都需要综合考虑。

十五、使用数据仓库和多维数据库存储数据量加大是一定要考虑OLAP的，传统的报表可能5、6个小时出来结果，而基于Cube的查询可能只需要几分钟，因此处理海量数据的利器是OLAP多维分析，即建立数据仓库，建立多维数据集，基于多维数据集进行报表展现和数据挖掘等。

十六、使用采样数据，进行数据挖掘基于海量数据的数据挖掘正在逐步兴起，面对着超海量的数据，一般的挖掘软件或算法往往采用数据抽样的方式进行处理，这样的误差不会很高，大大提高了处理效率和处理的成功率。一般采样时要注意数据的完整性和，防止过大的偏差。笔者曾经对1亿2千万行的表数据进行采样，抽取出400万行，经测试软件测试处理的误差为千分之五，客户可以接受。还有一些方法，需要在不同的情况和场合下运用，例如使用代理键等操作，这样的好处是加快了聚合时间，因为对数值型的聚合比对字符型的聚合快得多。类似的情况需要针对不同的需求进行处理。海量数据是发展趋势，对数据分析和挖掘也越来越重要，从海量数据中提取有用信息重要而紧迫，这便要求处理要准确，精度要高，而且处理时间要短，得到有价值信息要快，所以，对海量数据的研究很有前途，也很值得进行广泛深入的研究。

一般来说第7种方案是最常用的，有的主要就是使用第7种方案，选择的余地也非常的大，不只是俺月，日，年，也可以按周等等划分，灵活性较高

而面对大量数据的处理一般都是分批次处理，之前我做一个文本分类器，面对1g多的索引（索引1g多，但是分类时需要的数据就大得多了），40-50分钟就可以跑完所有分类：

一是分批操作。

二是给jvm回收内存的时间，比如每次20w的数据进行分类，完成之后睡眠一段时间，每睡眠一端时间就手动gc一次。

火龙果整理 uml.org.cn

通过这些方式取得了很明显得见效。

海量数据处理专题

（一）大数据量的问题是很多面试笔试中经常出现的问题，比如baidu google 腾讯 这样的一些涉及到海量数据的公司经常会问到。

下面的方法是我对海量数据的处理方法进行了一个一般性的总结，当然这些方法可能并不能完全覆盖所有的问题，但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目，方法不一定最优，如果你有更好的处理方法，欢迎与我讨论。

本贴从解决这类问题的方法入手，开辟一系列专题来解决海量数据问题。拟包含 以下几个方面。

1.Bloom Filter 2.Hash 3.Bit-Map 4.堆(Heap)5.双层桶划分 6.数据库索引

7.倒排索引（Inverted Index）8.外排序 9.Trie树 10.MapReduce

在这些解决方案之上，再借助一定的例子来剖析海量数据处理问题的解决方案。欢迎大家关注。

海量数据处理专题

（二）【什么是Bloom Filter】

Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。这里有一篇关于Bloom Filter的详细介绍，不太懂的博友可以看看。

【适用范围】

可以用来实现数据字典，进行数据的判重，或者集合求交集

【基本原理及要点】

火龙果整理 uml.org.cn

对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这 个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。

还有一个比较重要的问题，如 何根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况 下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应 该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。

举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。

注意这里m与n的单位不同，m是bit为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。

【扩展】

Bloom filter将集合中的元素映射到位数组中，用k（k为哈希函数个数）个映射位是否全1表示元素在不在这个集合中。Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter（SBF）将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

【问题实例】

给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？

根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿，n=50亿，如果按出错率0.01算需要的大概是650亿个 bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip，则大大简单了。

海量数据处理专题

（三）什么是Hash

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

火龙果整理 uml.org.cn

HASH主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值.也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系。数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：

左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

元素特征转变为数组下标的方法就是散列法。散列法当然不止一种，下面列出三种比较常用的。1，除法散列法

最直观的一种，上图使用的就是这种散列法，公式：

index = value % 16

学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫“除法散列法”。

2，平方散列法

求index是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的CPU来说，估计我们感觉不出

火龙果整理 uml.org.cn

来），所以我们考虑把除法换成乘法和一个位移操作。公式：

index =(value * value)>> 28

如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题，value如果很大，value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。

3，斐波那契（Fibonacci）散列法

平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数呢？答案是肯定的。

1，对于16位整数而言，这个乘数是40503 2，对于32位整数而言，这个乘数是2654435769

3，对于64位整数而言，这个乘数是***98485

这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，如果你还有兴趣，就到网上查找一下“斐波那契数列”等关键字，我数学水平有限，不知道怎么描述清楚为什么，另外斐波那契数列的值居然和太阳系八大行星的轨道半径的比例出奇吻合，很神奇，对么？

对我们常见的32位整数而言，公式：

i ndex =(value * 2654435769)>> 28

如果用这种斐波那契散列法的话，那我上面的图就变成这样了：

很明显，用斐波那契散列法调整之后要比原来的取摸散列法好很多。

火龙果整理 uml.org.cn

【适用范围】

快速查找，删除的基本数据结构，通常需要总数据量可以放入内存。【基本原理及要点】

hash函数选择，针对字符串，整数，排列，具体相应的hash方法。

碰撞处理，一种是open hashing，也称为拉链法；另一种就是closed hashing，也称开地址法，opened addressing。

【扩展】

d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key时，同 时用两个哈希函数进行计算，得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置，哪一个 位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key 存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。

【问题实例】

1).海量日志数据，提取出某日访问百度次数最多的那个IP。

IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。

海量数据处理专题

（四）【什么是Bit-map】

所谓的Bit-map就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

如果说了这么多还没明白什么是Bit-map，那么我们来看一个具体的例子，假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟1Byte 的空间，将这些空间的所有Bit位都置为0(如下图：)

火龙果整理 uml.org.cn

然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置为1（可以这样操作 p+(i/8)|(0x01<<(i%8))当然了这里的操作涉及到Big-ending和Little-ending的情况，这里默认为Big-ending）,因为是从零开始的，所以要把第五位置为一（如下图）：

然后再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态如下：

然后我们现在遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的。下面的代码给出了一个BitMap的用法：排序。//定义每个Byte中有8个Bit位 #include ＜memory.h＞ #define BYTESIZE 8 void SetBit(char *p, int posi){

}

void BitMapSortDemo(){

//BufferLen这个值是根据待排序的数据中最大值确定的 //待排序中的最大值是14，因此只需要2个Bytes(16个Bit)//为了简单起见，我们不考虑负数 int num[] = {3,5,2,10,6,12,8,14,9};*p = *p|(0x01＜＜(posi%BYTESIZE));//将该Bit位赋值1 return;for(int i=0;i ＜(posi/BYTESIZE);i++){ } p++;

火龙果整理 uml.org.cn

} //就可以了。

const int BufferLen = 2;char *pBuffer = new char[BufferLen];//要将所有的Bit位置为0，否则结果不可预知。memset(pBuffer,0,BufferLen);for(int i=0;i＜9;i++){

} //首先将相应Bit位上置为1 SetBit(pBuffer,num[i]);//输出排序结果

for(int i=0;i＜BufferLen;i++)//每次处理一个字节(Byte){

} for(int j=0;j＜BYTESIZE;j++)//处理该字节中的每个Bit位 {

} pBuffer++;

//判断该位上是否是1，进行输出，这里的判断比较笨。//首先得到该第j位的掩码（0x01＜＜j），将内存区中的 //位和此掩码作与操作。最后判断掩码是否和处理后的 //结果相同

if((*pBuffer&(0x01＜＜j))==(0x01＜＜j)){ }

printf(“%d ”,i*BYTESIZE + j);int _tmain(int argc, _TCHAR* argv[]){

} 【适用范围】 BitMapSortDemo();return 0;

火龙果整理 uml.org.cn

可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下 【基本原理及要点】

使用bit数组来表示某些元素是否存在，比如8位电话号码 【扩展】

Bloom filter可以看做是对bit-map的扩展 【问题实例】

1)已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。

8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。（可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit==1.2MBytes，这样，就用了小小的1.2M左右的内存表示了所有的8位数的电话）

2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上，在遍历这些数的时候，如果对应位置的值是0，则将其置为1；如果是1，将其置为2；如果是2，则保持不变。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个 2bit-map，都是一样的道理。

海量数据处理专题

（五）【什么是堆】

概念：堆是一种特殊的二叉树，具备以下两种性质

1）每个节点的值都大于（或者都小于，称为最小堆）其子节点的值

2）树是完全平衡的，并且最后一层的树叶都在最左边

这样就定义了一个最大堆。如下图用一个数组来表示堆：

火龙果整理 uml.org.cn

那么下面介绍二叉堆：二叉堆是一种完全二叉树，其任意子树的左右节点（如果有的话）的键值一定比根节点大，上图其实就是一个二叉堆。

你一定发觉了，最小的一个元素就是数组第一个元素，那么二叉堆这种有序队列如何入队呢？看图：

火龙果整理 uml.org.cn

假设要在这个二叉堆里入队一个单元，键值为2，那只需在数组末尾加入这个元素，然后尽可能把这个元素往上挪，直到挪不动，经过了这种复杂度为Ο(logn)的操作，二叉堆还是二叉堆。

那如何出队呢？也不难，看图：

火龙果整理 uml.org.cn

出队一定是出数组的第一个元素，这么来第一个元素以前的位置就成了空位，我们需要把这个空位挪至叶子节点，然后把数组最后一个元素插入这个空位，把这个“空位”尽量往上挪。这种操作的复杂度也是Ο(logn)。

【适用范围】

海量数据前n大，并且n比较小，堆可以放入内存

【基本原理及要点】

最大堆求前n小，最小堆求前n大。方法，比如求前n小，我们比较当前元素与最大堆里的最大元素，如果它小于最大元素，则应该替换那个最大元 素。这样最后得到的n个元素就是最小的n个。适合大数据量，求前n小，n的大小比较小的情况，这样可以扫描一遍即可得到所有的前n元素，效率很高。

【扩展】

双堆，一个最大堆与一个最小堆结合，可以用来维护中位数。

【问题实例】

1)100w个数中找最大的前100个数。

用一个100个元素大小的最小堆即可。

海量数据处理专题

（六）火龙果整理 uml.org.cn

【什么是双层桶】

事实上，与其说双层桶划分是一种数据结构，不如说它是一种算法设计思想。面对一堆大量的数据我们无法处理的时候，我们可以将其分成一个个小的单元，然后根据一定的策略来处理这些小单元，从而达到目的。

【适用范围】

第k大，中位数，不重复或重复的数字

【基本原理及要点】

因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子，分治才是其根本（只是“只分不治”）。

【扩展】

当有时候需要用一个小范围的数据来构造一个大数据，也是可以利用这种思想，相比之下不同的，只是其中的逆过程。

【问题实例】

1).2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。当然这个题也可以用我们前面讲过的BitMap方法解决，正所谓条条大道通罗马~~~ 2).5亿个int找它们的中位数。

这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。

实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几 大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。

3).现在有一个0-30000的随机数生成器。请根据这个随机数生成器，设计一个抽奖范围是0-350000彩票中奖号码列表，其中要包含20000个中奖号码。

这个题刚好和上面两个思想相反，一个0到3万的随机数生成器要生成一个0到35万的随机数。那么我们完全可以将0-35万的区间分成35/3=12个区间，然后每个区间的长度都小于等于3万，这样我们就可以用题目给的随机数生成器来生成了，然后再加上该区间的基数。那么要每个区间生成多少个随机数呢？计算公式就是：区间长度*随机数密度，在本题目中就是30000*（20000/350000）。最后要注意一点，该题目是有隐含条件的：彩票，这意味着你生成的随机数里面不能有重复，这也是我为什么用双层桶划分思想的另外一个原因。

第二篇：常用大数据量、海量数据处理方法 (算法)总结

 大数据量的问题是很多面试笔试中经常出现的问题，比如baidu google 腾讯 这样的一些涉及到海量数据的公司经常会问到。

下面的方法是我对海量数据的处理方法进行了一个一般性的总结，当然这些方法可能并不能完全覆盖所有的问题，但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目，方法不一定最优，如果你有更好的处理方法，欢迎与我讨论。

1.Bloom filter

适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集

基本原理及要点：

对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。

还有一个比较重要的问题，如何根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。

举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。

注意这里m与n的单位不同，m是bit为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。

扩展：

Bloom filter将集合中的元素映射到位数组中，用k（k为哈希函数个数）个映射位是否全1表示元素在不在这个集合中。Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter（SBF）将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

问题实例：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？

根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip，则大大简单了。

2.Hashing

适用范围：快速查找，删除的基本数据结构，通常需要总数据量可以放入内存

基本原理及要点：

hash函数选择，针对字符串，整数，排列，具体相应的hash方法。

碰撞处理，一种是open hashing，也称为拉链法；另一种就是closed hashing，也称开地址法，opened addressing。

扩展：

d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key时，同时用两个哈希函数进行计算，得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置，哪一个位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key 存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。

问题实例：

1).海量日志数据，提取出某日访问百度次数最多的那个IP。

IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。

3.bit-map

适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下

基本原理及要点：使用bit数组来表示某些元素是否存在，比如8位电话号码

扩展：bloom filter可以看做是对bit-map的扩展

问题实例：

1)已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。

8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。

2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map。

4.堆

适用范围：海量数据前n大，并且n比较小，堆可以放入内存

基本原理及要点：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我们比较当前元素与最大堆里的最大元素，如果它小于最大元素，则应该替换那个最大元素。这样最后得到的n个元素就是最小的n个。适合大数据量，求前n小，n的大小比较小的情况，这样可以扫描一遍即可得到所有的前n元素，效率很高。

扩展：双堆，一个最大堆与一个最小堆结合，可以用来维护中位数。

问题实例：

1)100w个数中找最大的前100个数。

用一个100个元素大小的最小堆即可。

5.双层桶划分

适用范围：第k大，中位数，不重复或重复的数字

基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子。

扩展：

问题实例：

1).2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。

2).5亿个int找它们的中位数。

这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。

实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。

6.数据库索引

适用范围：大数据量的增删改查

基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。

扩展：

问题实例：

7.倒排索引(Inverted index)

适用范围：搜索引擎，关键字查询

基本原理及要点：为何叫倒排索引？一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。

以英文为例，下面是要被索引的文本：

T0 = “it is what it is” T1 = “what is it”

T2 = “it is a banana”

我们就能得到下面的反向文件索引：

“a”: {2} “banana”: {2} “is”: {0, 1, 2} “it”: {0, 1, 2} “what”: {0, 1}

检索的条件“what”, “is” 和 “it” 将对应集合的交集。

正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词，而反向索引则是单词指向了包含它的文档，很容易看到这个反向的关系。

扩展：

问题实例：文档检索系统，查询那些文件包含了某单词，比如常见的学术论文的关键字搜索。

8.外排序

适用范围：大数据的排序，去重

基本原理及要点：外排序的归并方法，置换选择 败者树原理，最优归并树

扩展：

问题实例：

1).有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。

这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1m做hash有些不够，所以可以用来排序。内存可以当输入缓冲区使用。

9.trie树

适用范围：数据量大，重复多，但是数据种类小可以放入内存

基本原理及要点：实现方式，节点孩子的表示方式

扩展：压缩实现。

问题实例：

1).有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序。

2).1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？

3).寻找热门查询：查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节。

10.分布式处理 mapreduce

适用范围：数据量大，但是数据种类小可以放入内存

基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。

扩展：

问题实例：

1).The canonical example application of MapReduce is a process to count the appearances of

each different word in a set of documents: void map(String name, String document):

// name: document name

// document: document contents

for each word w in document:

EmitIntermediate(w, 1);

void reduce(String word, Iterator partialCounts):

// key: a word

// values: a list of aggregated partial counts

int result = 0;

for each v in partialCounts:

result += ParseInt(v);

Emit(result);

Here, each document is split in words, and each word is counted initially with a “1” value by

the Map function, using the word as the result key.The framework puts together all the pairs

with the same key and feeds them to the same call to Reduce, thus this function just needs to

sum all of its input values to find the total appearances of that word.2).海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。

3).一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)？

经典问题分析

上千万or亿数据（有重复），统计其中出现次数最多的前N个数据,分两种情况：可一次读入内存，不可一次读入。

可用思路：trie树+堆，数据库索引，划分子集分别统计，hash，分布式计算，近似统计，外排序

所谓的是否能一次读入内存，实际上应该指去除重复后的数据量。如果去重后数据可以放入内存，我们可以为数据建立字典，比如通过 map，hashmap，trie，然后直接进行统计即可。当然在更新每条数据的出现次数的时候，我们可以利用一个堆来维护出现次数最多的前N个数据，当然这样导致维护次数增加，不如完全统计后在求前N大效率高。

如果数据无法放入内存。一方面我们可以考虑上面的字典方法能否被改进以适应这种情形，可以做的改变就是将字典存放到硬盘上，而不是内存，这可以参考数据库的存储方法。

当然还有更好的方法，就是可以采用分布式计算，基本上就是map-reduce过程，首先可以根据数据值或者把数据hash(md5)后的值，将数据按照范围划分到不同的机子，最好可以让数据划分后可以一次读入内存，这样不同的机子负责处理各种的数值范围，实际上就是map。得到结果后，各个机子只需拿出各自的出现次数最多的前N个数据，然后汇总，选出所有的数据中出现次数最多的前N个数据，这实际上就是reduce过程。

实际上可能想直接将数据均分到不同的机子上进行处理，这样是无法得到正确的解的。因为一个数据可能被均分到不同的机子上，而另一个则可能完全聚集到一个机子上，同时还可能存在具有相同数目的数据。比如我们要找出现次数最多的前100个，我们将1000万的数据分布到10台机器上，找到每台出现次数最多的前 100个，归并之后这样不能保证找到真正的第100个，因为比如出现次数最多的第100个可能有1万个，但是它被分到了10台机子，这样在每台上只有1千个，假设这些机子排名在1000个之前的那些都是单独分布在一台机子上的，比如有1001个，这样本来具有1万个的这个就会被淘汰，即使我们让每台机子选出出现次数最多的1000个再归并，仍然会出错，因为可能存在大量个数为1001个的发生聚集。因此不能将数据随便均分到不同机子上，而是要根据hash 后的值将它们映射到不同的机子上处理，让不同的机器处理一个数值范围。

而外排序的方法会消耗大量的IO，效率不会很高。而上面的分布式方法，也可以用于单机版本，也就是将总的数据根据值的范围，划分成多个不同的子文件，然后逐个处理。处理完毕之后再对这些单词的及其出现频率进行一个归并。实际上就可以利用一个外排序的归并过程。

另外还可以考虑近似计算，也就是我们可以通过结合自然语言属性，只将那些真正实际中出现最多的那些词作为一个字典，使得这个规模可以放入内存。

第三篇：数据处理和电子表格软件教案

“数据处理和电子表格软件”教学设计

【适用年级】 初二年级第二学期 【适用单元】 电子表格软件第1节 【教学目标】 ●知识目标

（1）熟悉EXCEL窗口。

（2）理解工作簿、工作表、单元格概念。（3）掌握建立、保存、关闭工作簿的操作。（4）掌握工作表、单元格的基本操作。●技能目标

通过学生探究学习过程中，掌握EXCEL窗口中几个的基本操作。●情感目标

（1）通过动手实践，培养学生在学习过程中自主探究、对比、举一反三的学习能力；

（2）利用知识的迁移，培养学生的综合信息素养能力。【课时安排】2课时（两节连上）【教学重点与难点】

（1）重点：工作簿、工作表、单元格概念。（2）难点：掌握工作表、单元格的基本操作。【教学方法】对比法、任务驱动法 【课前准备】软件EXCEL 【教学设计】

教学过程 教师活动 学生活动 教学意图

引入新课

大家打开书本的目录看本书要学习什么内容？目录中大家看到的黑体字是——用计算机处理数据，计算机能处理什么样的数据呢？ 观察本书目录

让学生了解这本书我们将要学习哪些内容？（培养学生每学习一本书前先了解所学内容大概的习惯）

阅读思考

大家打开课本P2—P3了解以下问题：

1、什么是信息？什么是数据？两者有联系吗？

2、什么是数据处理？数据处理使用到哪些软件？

3、说说EXCEL软件的功能？ 阅读教材

说说自己的理解

培养学生利用阅读获取知识的习惯

区别与拓展

大家看第2页后，看这（教师指黑板）它告诉你什么样的信息？

黑板是色彩和形状这些信息表现出来的，生活中每样东西都有自己的信息如我们每一位都自己的信息：姓名、身高、衣着等，因此信息是广义的，表现信息叫数据，如色彩、长宽都是数据，同理数据也是一个广义的概念，包括数值、文字、图像等一些。如何处理这些数据是我们所关心的，课本中提到什么样软件？ 引导学生说说阅读P3后对EXCEL知道了多少？

黑色的、有长和宽的黑板 EXCEL 学生积极发言 设疑激趣 拓展知识面

让学生表达自己的看法，展示自己的空间

任务驱动

大家说了这么多了，看看EXCEL是什么样的？阅读课本P4—P6，认识EXCEL窗口，并在计算机中实践，同时比较与WORD窗口不同处 学生实践

培养学生自主探究和对比学习的能力

学生演示 请发现不同处的学生在教师机上展示 观察

知识巩固

设置障碍

教师不小心关闭文件窗口，只剩下软件平台，问怎么办？

学生说，教师操作

知识迁移到工作簿的新建、保存操作上。

引入新问题

在了解窗口时提到了Sheet工作表，这儿怎么又是工作簿，还有单元格，这三者都有些混了，怎么区分它呢？ 教师操作并讲解„„

看课本P9回答：一个工作表中能有多少个单元格呢？ 单元格、当前单元格、单元格区域怎样区分呢？ 教师操作并讲解„„

观察区别概念

答（行：256列65536表格）观察区别概念

让学生正确区别工作簿、工作表、单元格概念

正确区别单元格、当前单元格、单元格区域概念

任务驱动

了解单元格后，结合课本P10—P12完成P15练习4、5、6题

学生实践

以单元格的练习促进学生自主学习单元格的操作

教师小结并处理练习问题

一、单元格的选定操作及地址表示：

1、单个（一个）单元格

2、连续单元格区域

3、整行或整列

4、不连续单元格区域

观察

总结知识点

任务驱动

P16的练习7，它主要是对工作表进行的操作，可结合课本P13—P14完成练习学生实践

以工作表的练习促进学生自主学习工作表操作

辅导并检查作业

重点检查工作表的复制操作 如何同时复制多个工作表？

知识举一反三

学生总结本课知识 这节课你学到了什么？

教学后记

这节课教师引导，学生自主学习充分体现出来，我上本节课的成功之处有以下几点。

1．以练习促学：布置练习完成单元格及工作表的学习，在学习的过程中所有的学生都在积极看书或互相交流，没有看到学生“等着吃”的现象，这种积极的心态也感染了我，同时在处理练习时学生有自己的表现方式，如练习4中的地址，他地址输入到相应的单元格中，既直观又好理解；在练习7中的操作使用多种不同方法是我没有料想到的。这是我尝试调动学生自主学习的方法的一种，我认为比较成功，今后也可以推广的方法。

2．设置问题障碍：使学生积极主动解决问题，情趣高、效果比较好，知识迁移比较巧妙。

3．区别与拓展：对“信息”与“数据”知识的拓展比较满意，扩大学生对抽象概念的理解。

4．通过找不同学习EXCEL窗口时，随机说了几道题如234+548＝256*652＝的计算题让学生找不同并用它解决这个计算问题，学生通过自己发现很容易记住“编辑公式＝”的用法，这对今后数据处理有很大的用处。5．内容衔接比较紧凑。不足之处有以下几点。

1．“信息与数据”知识的拓展时间掌握不好会影响下面知识的进展速度。2．“了解EXCEL窗口，并区别与WORD窗口不同处”学生实践区别完成后，学生讲解与展示时间太长也影响进度，在另一个班我进行对比区别，让学生和我的进行比较，注意自己没有发现的，这样效果比较好。

第四篇：火龙果软件-UMLATM设计文档

火龙果整理 uml.org.cn

UML实验报告

2.用例建模

掌握客户需求分析的方法和步骤 了解以用例驱动的软件开发方法 掌握用例图的画法

掌握用Rose或PowerDesigner进行用例建模的具体方法和步骤

1.ATM系统用例图:

存款现金管理取款客户修改密码银行管理员维护ATM设备转账余额查询

2.这个ATM系统主要显示了对客户提供存取款，转账，余额查询和密码修改的功能，以及银行管理员对客户修改密码，现金和ATM设备维护的操作。3.描述用例 “取款”用例 用例编号：0671 用例名：转账 执行者：.人执行者：客户

.系统执行者：取款子系统 目的：执行取款任务 类型：端点 主要的 基本的 级别：一级 过程描述： 1.插卡

2.输入密码

3.输入取款金额确定

4.取款打印凭条

5.退出系统 “查询”用例 用例编号：0670

火龙果整理 uml.org.cn

用例名：查询账户 执行者：.人执行者：客户

.系统执行者：查询子系统 目的：执行查询任务 类型：端点 主要的 基本的 级别：一级 过程描述： 1.插卡

2.输入密码

3.查询账号

4.人名币查询

5.查询打印凭条

6.退出系统

“修改密码”用例 用例编号：0669 用例名：修改密码 执行者：

.人执行者：客户、银行工作人员.系统执行者：修改密码子系统 目的：执行修改密码任务 类型：端点 主要的 基本的 级别：一级 过程描述：1.插卡

2.输入密码

3.修改密码

4.输入新密码

5.再次输入新密码

6.修改成功退出系统

“转账”用例 用例编号：0668 用例名：转账 执行者：.人执行者：客户

.系统执行者：转账子系统 目的：执行转账任务 类型：端点 主要的 基本的 级别：一级 过程描述：1.插卡。

2.输入密码。

3.进入转账界面。

4.输入转入卡号或账号（只能同行转账）。

5.再次输入卡号或账号。

火龙果整理 uml.org.cn

6.输入转入金额确定。

7.退出系统 “现金管理”用例 用例编号：0667 用例名：现金管理 执行者：

.人执行者：银行管理员.系统执行者：现金管理子系统 目的：执行现金管理任务 类型：端点 主要的 基本的 级别：一级

过程描述： 1.进入银行系统

2.进行添加现金操作

3.退出系统 “维护ATM设备”用例 用例编号：0667 用例名：维护ATM设备 执行者：

.人执行者：银行管理员

.系统执行者：维护ATM设备子系统 目的：执行现金管理任务 类型：端点 主要的 基本的 级别：一级

过程描述： 1.进入银行系统

2.对ATM设备进行检查

3.对ATM设备进行相应维护

4.退出系统

3.活动图建模

了解活动图建模的概念

掌握描述一个操作执行过程中所完成工作（动作）的方法 掌握描述对象内部工作的具体步骤

ATM取款子系统活动图：

火龙果整理 uml.org.cn 客户需求分析规格说明书/系统分析规格说明书

了解用包模型来描述系统体系结构（用例模型）的方法 掌握用Rose或PowerDesigner进行包图建模的具体方法和步骤

火龙果整理 uml.org.cn

掌握书写客户需求规格说明书的基本格式

5.类建模

 对象类建模

理解面向对象系统分析和对象类建模的概念 了解和掌握面向对象系统分析的方法和步骤 了解和掌握寻找待开发系统中类的方法和技巧 掌握使用Rose或PowerDesigner建立类模型的方法

 类的继承建模

理解类之间的继承关系

了解和掌握分析类之间继承关系的方法

掌握使用Rose或PowerDesigner建立类之间继承关系模型的过程

 对象类关联关系建模

理解面向对象类之间关联关系的概念 了解和掌握分析类之间的关联关系的方法

了解和掌握待开发系统中类之间关联关系的分析方法

掌握使用Rose或PowerDesigner如何对关联关系进行建模的过程

许多单个的帐户组成了帐户库。帐户具有帐户类型、帐户号、余额三个属性，均为private，其类型分别为char，int，double。六个操作分别为setType、getType、getAccountNumbe、setAccountNumbe、caculateBalance、getBalance，除caculateBalance为protected其余均为public。

setType设置帐户类型，返回类型为void，参数类型为char，输入帐户类型。

getType获取帐户类型，返回类型为char，无参数。

setAccountNumbe设置帐户号，返回类型为void，参数类型为int，输入帐户号。

getAccountNumbe获取帐户号，返回类型为int，无参数。

caculateBalance计算余额，返回类型为void，参数为double，第一个参数为输入存取款数额，第二个参数为存款余额，既为输入也为输出。

getBalance获取帐户余额，返回类型为double，无参数。

许多银行储户组成了储户库。ATM系统包含了许多ATM机。银行储户及ATM机两个类包含哪些属性，哪些操作，它们的可见性及操作的返回类型、参数个数、参数类型从类图上都一目了然。更多的属性及操作都可以一一加上，使这个类图更详细更完整，从而使参与项目的每个成员都能无歧义的明了整个设计的类的结构。同样对于一个真正的银行系统，这个类图过于简单。比如帐户类型我们可以先定义一个abstract class，它包含一个帐户最基本的属性及操作。而有些操作先定义为abstract，如余额的计算。然后再继承这个abstract class，我们可以有saving account 和checking account等等。不同的帐户有不同的余额计算方法，我们可以加上具体的算法。对于不同的帐户可能还有一些它特有的操作，我们也可以加上，比如saving account在存款达到多少时可以享受机票打折的优惠。

对象类关联关系图：

火龙果整理 uml.org.cn

银行0..10..10..*0..10..1账号库0..*银行储户库ATM系统0..10..10..10..*账户---++++++账户类型: char账户号·: int余额: DoublesetType()getType()setAccountNumbe()getAccountNumbe()caculateBalance()getBalance()0..*1..*银行储户: char: char: void: int: Double: Double---+++用户姓名: int用户ID: int用户密码: int存钱(): int取钱(): int其他操作(): intATM机0..*0..*-+++ATM机ID: int收款(): int吐款(): int其他服务(): int1..*0..1 顺序图建模

理解顺序图的基本概念

了解和掌握软件工程中用例逻辑时序的分析方法 了解和掌握待开发系统中顺序图的设计和实现 掌握使用Rose或PowerDesigner创建顺序图的方法

下图描述了顾客在ATM机上取款时信息的流动情况。以时间为顺序。因为仅是示例，所以整个过程是没有出现任何故障时的流程，并且只画到了取款结束。通过这个图，我们可以看出消息是如何在系统中不同对象之间进行交互。

通过流程图我们可以很清楚地看到系统是如何工作的，系统各部分之间的信息及控制是如何发送的，整个流程是否合理。流程图对我们的设计起到了很好的帮助作用。注意在本图没有一个生命线终端有一个“X”，这是因为这个流程中还未遇到有对象生命结束。当有对象生命结束时需在对应的生命线终端画“X”，表明这个对象在这时被销毁。

首先银行储户将ATM卡插入读卡机，读卡机将信息传给客户管理，客户管理提出查询密码，显示部分将输入密码请求显示出来…..ATM取款顺序图 ：

火龙果整理 uml.org.cn

顺序客户读卡器显示设备输入设备ATM数据库点钞机银行数据库插入ATM卡接受ATM卡显示输入密码请求查询密码输入密码密码传递请求确认密码合法性询问服务类别显示输入服务类别请求输入取款请求取款请求确认密码合法性询问取款数额显示输入数额请求输入取款数额传递取款数额显示确认数额请求询问取款数额确认确认输入传递确认信息数额合法性确认请求确认数额合法性出钞请求出钞取钞询问是否打印凭条显示询问是否打印凭条确定请求退出取出ATM卡 火龙果整理 uml.org.cn 合作图建模

了解合作图的概念及其在系统设计中的作用 掌握两种交互图（顺序图和合作图）的差别 熟悉和掌握合作图案例的分析方法

掌握使用Rose或PowerDesigner依据用例绘制合作图

合作图和顺序图是可以无信息损失的相互转换，只是它们的侧重点是不一样的。顺序图着重于对象间消息传递的时间顺序，合作图着重于表达对象之间的静态连接关系。下图将顺序图转换为合作图。

ATM系统协作图 ：

1．插入ATM卡

2．接受ATM卡

3．查询密码

4．显示输入密码请求

5．输入密码

6．密码传递

7．请求确认密码合法性

8．确认密码合法性

9．询问服务类别

10．显示输入服务服务类别请求

11．输入取款请求

12．取款请求

13．询问取款数额

14．显示输入数额请求

15．输入取款数额

16．传递取款数额

17．询问取款数额确认

火龙果整理 uml.org.cn

18．显示确认数额请求

19．输入确认

20．传递确认信息

21．数额合法性确认请求

22．确认数额和法性

23．出钞请求

24．计算帐户余额

25．出钞

26．取钞

27．传递余额并询问是否还需要其他服务

28．显示帐户余额并提示选择下面的服务 状态图建模

了解状态图的概念及其在系统设计中的作用

掌握使用Rose或PowerDesigner依据用例绘制对象的状态图

下图描述了顾客在ATM机上进行操作会经历的几种状态，及各种状态之间转换的条件。因为是简化了的例子，所以除了等待顾客插入磁卡的起始状态和结束服务的终止状态，顾客会处于输入密码、选择服务类型、存款及取款四种状态。

ATM状态图：

插入磁卡后进入输密码状态，当密码输入正确时进入选择服务类型状态，当输入密码不正确时，停留在原状态，但如果三次不正确，服务结束。进入选择服务类型后根据选择的不同，顾客可进入存款和取款状态。存、取款结束后，顾客既可以选择结束服务到最终状态，也可以选择继续服务回到选择服务类型状态。

通过状态图我们可以无歧义的了解各个活动角色是如何在不同状况下转换的，转换的条件是什么，是否会出现死锁现象，是否有条件没考虑周全，是否有状态无法达到。状态图可以帮助我们发现问题，并及时改正。构件图建模

了解系统物理体系结构模型和表示方法 了解构件图建模的概念及其在系统设计中的作用 掌握使用Rose或PowerDesigner绘制构件图

火龙果整理 uml.org.cn 部署图建模

了解系统物理体系结构模型和表示方法 了解部署图的概念及其在系统设计中的作用 掌握使用Rose或PowerDesigner绘制部署图的方法

第五篇：海量阅读课题实施小结

一学期教七本书不是神话

一学期教七本书不是神话

浚县第二实验小学

张连锋

教书育人是教师的天职，教书是手段，育人是目的。学校教育就是要为社会培养合格公民和优秀人才。可是这些年来，我们大多情况下熟练地运用教书的手段，明争暗赛的培养着机械考试的高手，造成了严重的两极分化，普遍的厌学现象和道德滑坡。我们迷失在应试考试之中，忘记了育人的目的。怎样回归育人之道？《义务教育语文课程标准》要求：“要重视培养学生广泛的阅读兴趣，扩大阅读面，增加阅读量，提高阅读品位，提倡少做题，多读书，好读书，读好书，读整本的书。”著名教育家苏霍姆林斯基说过：“应该让孩子生活在书籍的世界里”。作家格林说过：“读书是世界上门槛最低的高贵行为”、“只有童年读的书，才会对人生产生深刻的影响”。我国著名学者、书香校园的首倡者朱永新先生在微博中则说：“没有阅读，就没有学生的精神成长”。而北大陈平原教授则认为：一辈子的道路决定于语文。真正的语文教育必须扩大阅读面，增加阅读量，去引导学生“读整本的书”。我们无论在课内还是课外都应该扩大孩子们的阅读量。

在本学期，我们课题组研究“课内外海量阅读”实验，我利用一切课堂时间，总共学习了七本书，具体做法如下：

一、化零为整，每天循序渐进

我们学校每天八点到八点二十有二十分钟的早读课，一般都是让学生熟悉课文的。而这个时间被我“公款私用”了，每天分享一首诗，有时候是现代诗，有时候是外国的优秀诗篇，有时候是与节气或者节日，或者单元主题有关的古诗，每天领着孩子们读诗，赏诗，背诗，也是“别有一番滋味在心头”。后来，发现了徐冬梅，薛瑞萍老师主编的《日有所诵》，如获至宝，从此，它成了我们早读课的主角。每天二十分钟，孩子们收获的不止一点点课外知识。

二、固定时间，养成习惯

阳光体育的时候，我们学校每个班的体育变成了三节。后来由于教师不够，每个班的一节体育课由班主任来上。由于基本的体育技能管体育的老师基本上都交过了，所以这一节课，我跟孩子们商量后又挪作他用了。《俗语儿歌100首》是一首简单易懂，道理简单的书，这节课每次抄五首，孩子们边抄边问，不认识的字查字典，不理解的就商量，商量完就背，背过了就说，说一句话或者一段话，用上今天所学习的俗语，这样学、背、用，一堂课基本上可以完成。有些当堂没有办法完成的，就当做课下作业，并联络家长一起督促。这样在孩子的生活中，遇到合适的情境，孩子们总是能说出一些有关的俗语，给别人出口成章的感觉，得到了别人的认可，孩子们学的尽头更大了。

三、整合资源，为我所用

国学经典走进课堂，给孩子们种植文化底蕴。《弟子规》《百家姓》《论语》《孟子》等纷纷走进各年级的课堂。《中华经典诵读》这套教材编的非常好，原文下面有注释，注释下面有译文，译文下面有故事链接。孩子们完全可以通过自己的用心阅读来理解，内化，吸收。我们这学期学的是《孟子》，孩子们已经不单单满足于每周五的阅读课来阅读这本书，放学后，吃饭余，他们都废寝忘食的读着。后来，他们纷纷找我说希望阅读更多的经典，于是我把课题组里其他班级的《增广贤文》借过来发到班里，孩子们如饥似渴的读起来。这样，我们用了同样的时间读了两本经典诵读，孩子们都满足而骄傲的说：“我们无法决定时间的长度，但我们拓宽了它的宽度。”

四、课本主角，力求详解

很多人劝我说：“课本是最基本的，一定要让孩子牢固掌握了课本，保证了考试成绩，才去干‘杂事’。”为了堵住悠悠之口，也为了向别人证明我做的是对的。我跟孩子们商量该怎么办。孩子们纷纷出谋划策，结合我们原来的学习方法，我们又制定了新的学习模式——“五读掌”。每天学习课文之前，自己在家里预习，解决生字等最基本的学习目标，在书本的空白处批上自己的理解，给不太懂的地方坐上标记。课堂上通过小组合作讨论，分享自己的理解所得，并解决昨天自己预习时所遇到的问题。下一步展示，小组推荐自己的批注里比较重要的地方，分享给全班同学。理解了课文后，演绎课文，选自己喜欢的地方或者感受最深的地方，通过朗读表演出来。孩子们基本上每堂课都在忙，忙于展示，忙于讨论，忙于分享，忙于表演......而且是乐在其中的忙。他们还说：“在别人展示的时候，认真听，一方面表示对别人的尊重，二是把别人的理解据为己有，我们就站在了巨人的肩膀上，自己就会变得更聪明。”

五、快速阅读，事半功倍

课堂变得高效，课文就学的特别快。在大半个学期的时候，我们就学完了课文，孩子们没有意思，就要求把我们的辅助读物《快乐作文》和《语文阅读》，也拿到课堂上用“五毒掌”来学习。由于，这两本书的单元主题是一样的，所以我们就合并学习，一次学习一个单元。通过预习，批注，提问，展示，演绎的方式，我们愉快的度过了一堂又一堂的语文课。我们知道了南京大屠杀使中国人前所未有的团结起来，我们知道了一个孩子一双小眼睛里有无数的情感，我们知道了......看着孩子们因学到了知识而闪光的笑脸，我心里特别欣慰。

“课内外海量阅读”研究实施以来，我带着孩子们一个学期学完了《语文课本》、《日有所诵》、《中华经典诵读之孟子》、《中华经典诵读之增广贤文》、《快乐作文》、《语文阅读》、《俗语儿歌100首》七本书，孩子们在课外也在一本本书里认识了杨红樱、沈石溪、郑渊洁、曹文轩等作家，尝到了读书的甜头，享受了读书的快乐。就这样读着，想着，实验着，摸索着，快乐着，一路走下去，我愿意。