主存储器和外存储器

• 计算机存储器主要有两种:
  • 主存储器 ( primary memory 或者 main memory ，简称“内存”，或者“主存”)
    • 随机访问存储器 ( Random Access Memory, 即 RAM )
    • 高速缓存 ( cache )
    • 视频存储器 ( video memory )
  • 外存储器
    • 硬盘
    • 磁带

内存的优缺点

• 优点:访问速度快
• 缺点:造价高，存储容量小，断电丢数据
• CPU 直接与主存沟通，对存储在内存地址的数据进行访问时，所需要的时间可以 看作是一个很小的常数

外存的优缺点

• 优点:价格低、信息不易失 、便携性
• 缺点:存取速度慢
  • 一般的内存访问存取时间的单位是 纳秒 (1 纳秒 = 10-9 秒)
  • 外存一次访问时间则以 毫秒(1 毫秒 = 10-3 秒)或秒为数量级
• 牵扯到外存的计算机程序应当尽量 减少外存的 访问次数， 从而减少程序执行的时间

文件的组织和管理

文件的逻辑结构

• 文件是记录的汇集
  • 一个文件的各个记录按照某种次序排列起来， 各纪录间就自然地形成了一种线性关系
• 因而，文件可看成是一种线性结构

文件组织

• 文件逻辑组织有三种形式:
  • 顺序结构的定长记录
  • 顺序结构的变长记录
  • 按关键码存取的记录
• 常见的物理组织结构:
  • 顺序结构——顺序文件
  • 计算寻址结构——散列文件
  • 带索引的结构——带索引文件
    • 倒排是一种特殊的索引

文件上的操作

增删改查排序

缓冲区和缓冲池

• 目的:减少磁盘访问次数的
• 方法:缓冲 ( buffering ) 或缓存( caching )
  • 在内存中保留尽可能多的块
  • 可以增加待访问的块已经在内存中的机会
• 存储在一个缓冲区中的信息经常称为一页 ( page )，往往是一次 I/O 的量
• 缓冲区合起来称为缓冲池( buffer pool )

替换缓冲区块的策略

新的页块申请缓冲区时，把最近最不可能 被再次引用的缓冲区释放来存放新页

• “先进先出”( FIFO )
• “最不频繁使用”( LFU )
• “最近最少使用”( LRU )

外排序

磁盘文件的排序

• 对外存设备上(文件)的排序技术
• 通常由两个相对独立的阶段组成:
  • 文件形成尽可能长的初始顺串(run )
  • 处理顺串，最后形成对整个数据文件的排列文件

置换选择排序

算法思想：

• 利用最小值堆（或最大值堆）对数据进行处理。每输出一个最小值（或最大值），就从缓冲区中读入下一个数。
• 数据如果比堆顶小，那么放到堆数组末尾，并把堆大小减1，直到堆大小为0，重新建堆
• 数据如果比堆顶大，那么把堆顶替换掉，然后调整堆

template 
    
     void replacementSelection(Elem * A, int n, const char * in, const char * out) {    Elem mval;    Elem r;    FILE * inputFile;    FILE * outputFile;    Buffer
     
       input;    Buffer
      
        output;    initFiles(inputFile, outputFile, in, out);    initMinHeapArry(inputFile, n, A); // 建堆     MinHeap
       
         H(A, n, n);     initInputBuffer(input, inputFile);    for(int last = (n-1); last >= 0;){        mval = H.heapArray[0];         sendToOutputBuffer(input, output, inputFile, outputFile, mval); input.read(r);        if (!less(r, mval))             H.heapArray[0] = r;        else {            H.heapArray[0] = H.heapArray[last];             H.heapArray[last] = r;  // 缓存到缓冲区等待重新建堆            H.setSize(last--);        }        H.SiftDown(0);     }    endUp(output, inputFile, outputFile); }复制代码
       
      
     
    

置换选择算法的效果

• 置换选择排序算法得到的顺串长度并不相等。 如果堆的大小是 M
• 一个顺串的最小长度就是 M 个记录
• 至少原来在堆中的那些记录将成为顺串的一 部分
• 最好的情况下，例如输入为正序，有可能一次 就把整个文件生成为一个顺串
• 平均情况下，置换选择排序算法可以形成长度 为 2M 的顺串

二路外排序

• 归并原理:把第一阶段所生成的顺串加以合并(例如通 过若干次二路合并)，直至变为一个顺串为止，即形成 一个已排序的文件
• 为一个待排文件创建尽可能大的初始顺串，可以大大减 少扫描遍数和外存读写次数
• 归并顺序的安排也能影响读写次数，把初始顺串长度作 为权，其实质就是 Huffman 树最优化问题

多路归并——选择树

• k 路归并是每次将 k 个顺串合并成一个排好序的顺串
• 在 k 路归并中，最直接的方法就是作k-1次比较来找出所要的记录，但这样做花的代价较大
• 我们采用选择树的方法来实现 k 路归并，比较logK次就够了
  • 选择树是完全二叉树，有两种类型:赢者树和败方树
• 一般情况下，对 m 个初始顺串进行k路归并时归并趟数为logkm。增加每次归并的顺串数量 k 可以减少归 并趟数

赢者树

在利用选择树进行归并时，将两个子女结点中的赢者（关键码值较小者）上升到父结点，称这种选择树为赢者树。因此，根结点是树中的最终赢者的索引，即为下一个要输出的记录结点。

败者树

由于败者树中直接保存了比赛失败者而不是胜利者的索引，故每次比较时不需要去访问兄弟结点。

在利用选择树进行归并时，将两个子女结点中的败者（关键码值较大者）上升到父结点，同时另加进一个结点以代表比赛的全局获胜者的索引值，称这种选择树为败者树。

败者树比赛过程：将新进入树的结点与其父结点进行比赛把败者存放在父结点中而把胜者再与上一级的父结点进行比赛这样的比赛不断进行，直到根结点处。并将全局获胜者的索引值存放在添加结点中。例如：

}

template
    
      class LoserTree{ private:    int MaxSize; // 最大选手数    int n;// 当前选手数    int LowExt; // 最底层外部结点数    int offset; // 最底层外部结点之上的结点总数    int * B;// 败方树数组，实际存放的是下标    T * L;    void Play(int p,int lc,int rc,int(*winner)(T A[],int b,int c));public:    LoserTree(int Treesize = MAX);    ~LoserTree(){delete [] B;}    void Initialize(T A[], int size,int (*winner)(T A[], int b, int c), int(*loser)(T A[], int b, int c)); // 初始化败方树    int Winner(); // 返回最终胜者索引    void RePlay(int i, int(*winner)(T A[], int b, int c), int (*loser)(T A[], int b, int c)); // 位置 i 的选手改变后重构败方树};// 成员函数Winner，返回最终胜者 B[0] 的索引template
     
      int LoserTree
      
       ::Winner(){    return (n)?B[0]:0; }template
       
          //初始化败者树void LoserTree
        
         ::Initialize(T A[], int size, int(*winner)(T A[], int b, int c), int(*loser)(T A[], int b, int c)) {    if (size > MaxSize || size < 2) {        cout<<"Bad Input!"<
         
          <
          
           void LoserTree
           
            ::Play(int p, int lc, int rc, int(* winner)(T A[], int b, int c), int(* loser)(T A[], int b, int c)){ B[p] = loser(L, lc, rc); // 败者索引放在B[p] int temp1, temp2; temp1 = winner(L, lc, rc);// p处的胜者索引 while(p>1 && p%2) { // 内部右，要沿路向上比赛 temp2 = winner(L, temp1, B[p/2]); B[p/2] = loser(L, temp1, B[p/2]); temp1 = temp2; p/=2; } // B[p]是左孩子，或者B[1]B[p/2] = temp1; //单独设置B[0]存储当前胜者索引，注意B1是根节点复制代码
           
          
         
        
       
      
     
    

RePlay重构

template
    
      void LoserTree
     
      ::RePlay(int i, int(*winner)(T A[], int b, int c), int (*loser)(T A[], int b, int c)){    if(i<=0||i>n) {        cout<<"Out of Bounds!"<
      
       <
       
        =1; p/=2) { // 沿路径向上比赛        int temp = winner(L,B[p/2], B[0]);         B[p/2] = loser(L,B[p/2], B[0]);        B[0] = temp;    }}复制代码
       
      
     
    

外排序效率考虑

假设对k个顺串进行归并。

• 原始方法：找到每一个最小值的时间是Θ(k)，产生一个大小为n的顺串的总时间是Θ (k×n)。
• 败者树方法：初始化包含k个选手的败者树需要Θ (k)的时间；读入一个新值并重构败者树的时间为Θ (log k)。故产生一个大小为n的顺串的，总时间为Θ (k+n×logk)。
• 为了减少归并趟数，可以从两个方面着手:
  • 减少初始顺串的个数 m
  • 增加归并的顺串数量 k

最佳归并树

如果在进行多路归并的时候，各初始顺串的长度不同，对外存扫描的次数，即执行时间会产生影响。把所有初始顺串的块数作为树的叶结点的权值，如果是K路归并则建立起一棵K-叉Huffman树。这样的一棵Huffman树就是最佳归并树。通过最佳归并树进行多路归并可以使对外存的I/O降到最少，提高归并执行效率。

在一般情况下，对于 k–路平衡归并来说，若 (m-1)MOD(k-1)=0，则不需要增加虚段；否则需附加 k-(m-1)MOD(k-1)-1 个虚段。

如果要想减小 m 的值，在外部文件总的记录数 n 值一定的情况下，只能增加每个归并段中所包含的记录数 l。而对于初始归并段的形成，就不能再采用上一章所介绍的内部排序的算法，因为所有的内部排序算法正常运行的前提是所有的记录都存在于内存中，而内存的可使用空间是一定的，如果增加 l 的值，内存是盛不下的。

通过置换选择排序算法得到的初始归并段，其长度并不会受内存容量的限制，且通过证明得知使用该方法所获得的归并段的平均长度为内存工作区大小的两倍。

例如已知初始文件中总共有 24 个记录，假设内存工作区最多可容纳 6 个记录，按照之前的选择排序算法最少也只能分为4个初始归并段。而如果使用置换—选择排序，可以实现将 24 个记录分为 3 个初始归并段.

置换—选择排序算法的具体操作过程为：

1. 首先从初始文件中输入 6 个记录到内存工作区中；
2. 从内存工作区中选出关键字最小的记录，将其记为 MINIMAX 记录；
3. 然后将 MINIMAX 记录输出到归并段文件中；
4. 此时内存工作区中还剩余 5 个记录，若初始文件不为空，则从初始文件中输入下一个记录到内存工作区中；
5. 从内存工作区中的所有比MINIMAX值大的记录中选出值最小的关键字的记录，作为新的 MINIMAX 记录；
6. 重复过程 3—5，直至在内存工作区中选不出新的MINIMAX记录为止，由此就得到了一个初始归并段；
7. 重复 2—6，直至内存工作为空，由此就可以得到全部的初始归并段。