読み込んでいます...
2010年02月17日

昨天晚上看了一个题目,这个题目很强,一开始在做的时候,没有考虑那么多,想来想去还是没有什么头绪,后来看到一个哥们写的题目发现特别简单,但是特别难懂,后来查了一下相关资料,哇,确实是一个强题,可能一般人来看这个题目的话,代码可能会写很多,而且效率也不算很高,但是这个标准解答还是很不错的。题目如下。

结果为0的序列:

考虑由1到n(n<=9)按递增顺序排成的序列1234…n,在他们之间加入加号,减号或者什么也不加,分别使它们做加法,减法或者将数字合并。然后求出结果,看看是否为0。

写一个程序,找出所有长度为n的结果为0的序列,返回序列的个数。

函数接口:int ResultIsZero(int n);

其中n表示序列的长度,int表示返回的序列的个数。

举例:

n = 8,返回10。

序列分别为:

1+2+3+4-5-6-7+8 = 0;

1+2+3-4+5-6+7-8 = 0;

1+2-3+4+5+6-7-8 = 0;

1+2-3-4-5-6+7+8 = 0;

1-2+3-4-5+6-7+8 = 0;

1-2-3+4+5-6-7+8 = 0;

1-2-3+4-5+6+7-8 = 0;

1+23-45+6+7+8 = 0;

12-34-56+78 = 0;

1-23-4+5+6+7+8 = 0;

如果你看明白了题目,你可以开始做这个题目了,如果你看明白了但是想了半天和我一样不会做的话,那就需要先来了解一下深度优先搜索DFS了。

了解百度百科,还有一个详细资料,关于图论的,关于迷宫的深度搜索算法。下面我给出一个迷宫的算法,迷宫如下图所示。

迷宫的代码如下:

Code

我们只有了解了迷宫的深度优先的搜索的递归算法,才能再来回头看我们前面说的题目,那个找结果为0的数字的表达式集合,我们同样可以用深度优先搜索计算,代码如下所示。

Code

这个答案是不是很强,其实其中还有很多值得我们去学习。。

2010年02月16日

今天一个朋友发来一道题,初步看上去好像蛮有挑战的,但是仔细想了一下之后其实好像没那么难,好像也没什么特别的陷阱,琢磨了一下,貌似也真的没什么好检查的,所以觉得也不是很难,但是朋友发的,所以就贴上来告知一下答案了。。哎,其实也没什么好些的,放假的时候无聊的朋友也可以练一下小手。。

已知f[]和g[]两个数组,大小分别为m和n,其中的元素都已经从小到大排列,且每个数组内的元素都各不相同。

例:f[5] = {1,3,4,7,9}, g[4] = {3,5,7,8}; 因为只有2组元素相同,分别是f[1]与g[0] 和 f[3]与g[2],所以函数Count的返回值应为2。

C++代码如下:

Code
2009年12月7日

第一就是关于内存的速度的,其实不难,但是开发的时候想到的很少,能想到的优化的就是高人,我也是路过看到不错,觉得很有用,就贴过来了。

另一个就是《算法导论》了,国外的教材,也是MIT的标准教材,很好很强大,昨天看到了堆排序和快速排序(100页),用了好多张纸证明线性比较排序的上界和下界,堆排序和快速排序的最好的速度是nlogn,从数学角度上证明了线性比较排序(如判断a[1]>a[0])的最快就是nlogn,也就是说只要你是比较的,而且还是线性的,nlogn就是最快的了。

数学公式太复杂,什么期望啊,概率啊,极限啊,记的不是很清楚,让我自己推倒也没这个能力,不过倒是让我知道了,以后别想线性快速的排序还能超过nlogn了。:)

2009年12月3日

前面有一篇文章里面我写了LRU算法,其中还将一些算法更新了一下,现在我就做个笔记,写一下LRU算法的一些用途,另外说明一下,这里我们LRU算法都不会考虑空间不足的问题(因为从软件模拟来说基本不会存在这个问题),如果在CPU硬件设计上出现空间不足的话,我们直接将链表的第一个元素剔除即可,当然,也有相应硬件能够直接做这种事情。

当然,LRU不仅仅在硬件设计上有很好的作用,在软件设计上也有很好的作用,例如Orical的数据库就是用了LRU算法。我们可以先看看下面这个图。

Oracle的设计可以从上图看到,这里buffer(缓冲区)就像一个水池,水池的最小单位就是数据块。当每个数据块被读入buffer时,Oracle或相应的软件都会抽取数据块的头部,在内存中构建buffer header,并将这些buffer header串成链表的形式。而buffer header里面记录的指针就指向buffer中的该数据块本身。于是,当我们在搜索某个数据块时,就不用去缓冲区中找,而是直接扫描链表上该数据块所对应的buffer header,然后根据找到的buffer header所记录的指针就能到buffer中直接定位该数据块了。而维护buffer header就是hash表,而buffer header就是一个LRU维护的链表。

这里的buffer head就是数据的一些信息,例如如果我将数字存储到数据中,我可以通过一种方式获取其head的信息,存放到相应的hash组里面,而hash的key也是可以通过数据本身得到。例如我们可以将数字求100的余数得到key,然后余10得到页面id。例如25这个数字,我们可以余100为25,余10为5,那么我们就在缓冲区buffer[25,5]的地方将这个数据保存起来,下次我们取的时候可以直接从25获得hash的组id和存放的页面id,即25和5,则我们直接读取buffer[25,5]即可。

说了这么多,可以稍微总结一下,这个数据结构就是。

  • hash表:存放数据的组,用于查找和维护。
  • buffer head:LRU链表,被hash组维护,其内容为在内存(缓冲区)的页面id。
  • buffer:缓冲区,用于存放数据。

简单的说,也就是当数据读入,我们通过一种方法获取组的id,然后在相应的组中维护一个页面id(链表),然后查找的时候直接通过组id和页面id得到数据,从而提高速度。

不过这里就会有一个问题,hash表这里就不存在冲突的问题了,因为hash表的value是一个链表结构,所以不存在冲突,如果有相同的key的话,我们直接在后面添加节点即可,但是在缓冲区的话就有可能有问题,例如25和125这两个值最后在缓冲区的位置应该是一样的,那么我们肯定不能覆盖掉,所以我们就查找25这个位置(25,5)后面的这个空间是否被使用(25,6),如果没被使用,则我们写到这个空间中,并更改LRU链表指针里面的值。

例如25会是第25组,其页id为5,当读到125的时候,发现也是25组和id为5,那么我们就查找6的位置,如果6位置没数据写入,那么OK,写到6的位置,并更新链表为第25组,页id为6,直到内存缓冲区被写满为止,我们都不覆盖

这样我们解决了冲突问题,但是这样的话,查找也就出了问题,即不能够直接查找,同样是25和125这两个数,两个坐标最后会成为(25,5)和(25,6),但是我们两个数通过规则获得到的key和页面id是25和5。所以当我们查找的时候就不需要使用页面id,而是采用扫描的方式。即当我们搜索125这个数字的时候,可以获得组id,即25,然后扫描这个组维护的LRU链表,然后扫描内存块,查找是否是我们需要的数据,如果是,则返回。就是我们搜索125,发现组id为25,那么我们就找(25,5),发现数据为25,不是我们想要的,继续下一个链,(25,6)直到找到需要的数据。

不过上面我们也可以优化一下,即优化成结构体,每个数据都有自己的独立的页面id,而不是通过一种规则去找页面id,尽量避免冲突,提高效率。我们可以看一下Orical的做法。

“当前台进程发出SELECT或者其他DML语句时,Oracle根据SQL语句的执行计划找到符合SQL条件的数据块,然后Oracle会根据对请求的数据块的地址以及数据块的类型作为参数,应用hash函数以后,得到要找的数据块所处的hash bucket,也就是确定该数据块在哪条hash chain上。然后,Oracle进入该hash chain,从上面所挂的第一个buffer header开始,根据buffer header所含有的指针找到对应的块体,然后扫描其中的数据,确认其是否是SQL语句所需要的块,如果是,则返回该块里所需要的数据;否则,如果不是,则继续往下搜索,一直搜索到最后一个buffer header为止。如果一直都没有找到,则调用物理I/O,到数据文件里把该块所含有的内容复制一份到一个可用的buffer里,并构建该块的 buffer header,然后将该buffer header挂到hash chain上去。”

所以基本上我们可以明确算法了,下面我给一下C#模拟的代码。

namespace LRUandData
{
定义LRU链表

class Program
{
定义数据块,缓冲区和hash表

static void Main(string[] args)
{
hash
= new Dictionary<int, LRUList>();
//初始化数据
InsertData();
//查询数据
int value = SearchData(33);
Console.WriteLine(value);
Console.ReadKey();
}


初始化数据

查找数据
}

}

上面的代码模拟了基本的操作,如果有更多功能只能大家自己改了。:)

从这里我们也可以看到,设计一个好的软件,数学,数据结构,计算机组成原理等等基础的东西是非常重要的,决定技术高度,基础的牢固程度最重要,举个老师给我们举了一百遍的例子,房子的高度由地基牢固程度决定,真的一点不假。

2009年11月26日

昨天同事说了一道题,这道题说难也难,说简单也简单,但是细节比较麻烦,是个难题,如果这个是面试题的话,确实能够拦下很多人。

题目:有一串字符串,根据字符串生成二叉树,输入输出如下(输出是以树的形式输出)。

输入:{1}

输出:1

输入:{1{2,3}}

输出:根节点1,1的左节点为2,1的右节点为3

输入:{1{2{4},3{5,6}}}

输出:根节点1,1的左节点为2,2的左节点为4,右节点为空,1的右节点为3,3的左右节点分别为5,6。

下面是代码,慎看,并不一定是最好的,与标答还是有一定的距离的,不过效率还不错,标答就比较难理解了,过一段时间我再把标答发上来。思路不是很难,但是代码估计很难看懂:(

生成树

标答的技巧很巧妙,过一段时间让朋友帖上来。

2009年11月22日

最近看了一下堆这个数据结构,虽然在平时不太用到,但是也是基本的数据结构之一,不太了解所以就要了解,而且网上也没有什么好的可以使用的堆的排序方法,所以研究了一天终于把堆和优先级队列弄了个大概,在这里分享一下代码(C/C++)。

堆和堆排序

堆不是堆栈的堆,堆是以数组描述的类似二叉树的结构,但是堆的数据结构和二叉树有本质的区别,二叉树是用散列的表的形式描述的,如使用指针,而堆是以数组形式描述的,只是可以看做是二叉树,具体的基础我就不再过多的说了,可以Google一下。

堆分大根堆和小根堆,大根堆就是根节点最大的堆,左右节点都小于父节点的值,而小根堆刚好想法,根节点是最小的值,而左右节点都大于父节点,如下图。

堆满足两个性质,(1)顺序,节点和子节点都有一定的顺序,不过注意,这里的顺序不是遍历的顺序,只是父子节点之间的顺序,即父节点大于子节点或父节点小于子节点。(2)完全二叉树的特性,在创建堆得时候,我们从第0个元素开始创建,顺序的填满每个节点。

在对一组数据排序的时候,我们可以使用堆排序进行排序,堆排序最坏的情况系下为O(nlogn),所以在数据量很大的情况下是很有优势的,下面给出C#的堆排序的步骤和代码。

  1. 生成大根堆或小根堆,从最后的节点开始遍历调整节点。
  2. 将根节点和最后一个节点调换并调整调换的节点并使之符合堆的性质。(如上面我们在最右下角插入0的时候,就不满足堆的性质,我们这里就要重新调整节点并使之成为堆)

下面是代码和丰富的注释。

class Program
{
    
static int[] numbers = { 3, 2, 1, 4, 9, 7, 8, 5, 6 };

    //索引从0开始的堆
    
//父:(index – 1)/2
    
//左孩子:2*index+1
    
//右孩子:2*index+2

    //小根堆
    static void Main(string[] args)
    {
        
//堆排序
        heapSort(numbers);

        //优先级队列
        
//Insert(numbers, 0);
        
//Delete(numbers);

        //优先级队列是无序的,再次排序
        
//heapSort(numbers);

        //输出
        for (int i = 0; i < numbers.Length; i++)
        {
            Console.WriteLine(numbers[i]);
        }

        Console.ReadKey();
    }

    //先构造大根堆,然后大根堆调整顺序则返回小根堆顺序(顺序)
    
//先构造小根堆,然后小根堆调整顺序择返回大根堆顺序(逆序)
    public static void heapSort(int[] arr)
    {
        
//BuildMinHeap(numbers)
        BuildMaxHeap(numbers);

        for (int i = (arr.Length - 1); i > 0; i)
        {
            Swap(
ref arr[0], ref arr[i]); //将堆顶元素和无序区的最后一个元素交换  
            MaxHeapify(arr, i, 0); //将新的无序区调整为堆  
        }
    }

    private static void MaxHeapify(int[] arr, int heapSize, int i)
    {
        
int left = 2 * i + 1; // 左子节点  
        int right = 2 * i + 2; // 右子节点  
        int large = i; // 临时变量,存放大的节点值  

        // 比较左子节点  
        if (left < heapSize && arr[left] > arr[large])
        {
            large
= left;
        }

        // 比较右子节点  
        if (right < heapSize && arr[right] > arr[large])
        {
            large
= right;
        }

        if (i != large)
        {
            Swap(
ref arr[i], ref arr[large]);
            MaxHeapify(arr, heapSize, large);
        }
    }

    private static void MinHeapify(int[] arr, int heapSize, int i)
    {
        
int left = 2 * i + 1; // 左子节点  
        int right = 2 * i + 2; // 右子节点  
        int small = i; // 临时变量,存放小的节点值  

        // 比较左子节点  
        if (left < heapSize && arr[left] < arr[small])
        {
            small
= left;
        }

        // 比较右子节点  
        if (right < heapSize && arr[right] < arr[small])
        {
            small
= right;
        }

        if (i != small)
        {
            Swap(
ref arr[i], ref arr[small]);
            MinHeapify(arr, heapSize, small);
        }
    }

    //构造大根堆
    static void BuildMaxHeap(int[] nums)
    {
        
for (int i = nums.Length / 2 - 1; i >= 0; i)
        {
            MaxHeapify(nums, nums.Length, i);
        }
    }

    //构造小根堆
    static void BuildMinHeap(int[] nums)
    {
        
for (int i = nums.Length / 2 - 1; i >= 0; i)
        {
            MinHeapify(nums, nums.Length, i);
        }
    }

    private static void Swap(ref int a, ref int b)
    {
        
int tmp;
        tmp
= a;
        a
= b;
        b
= tmp;
    }
}

上述代码为堆排序代码,我们可以使用大根堆或者小根堆为堆进行排序操作,而且也具有不错的性能。堆排序顺序遍历是有序的,而堆得有序本身不是数的有序,也就是说堆这个数组在堆排序之后就变成有序的数组了,但是堆不一定有序。

注意:堆的特性,以0开始的索引的堆父节点为当前节点的值减去1除以2,左孩子为当前节点的值乘以2加1,右孩子为加2。以1开始的索引无序加减,直接除以2,或乘以2和乘以2加1。

优先级队列

优先级队列是一种特殊的队列,普通的队列是先进先出的,而优先级队列是根据优先级出的,例如操作系统的一些优先级进程管理等等,都可以使用优先级队列。优先级队列也有最小优先级队列和最大优先级队列。

从道理上来说,优先级队列可以是任何一种数据结构,线性的,非线性的,也可以是有序的或无序的。但是针对有序的来说,获取最小或最大的值是非常容易的,但是插入却是非常困难的,而对于无序的来说,插入是很容易的,但是获取最大最小的是很麻烦的,但是可以使用堆这种折中的模式来处理,下面是复杂度的几种比较。

顺序:

  • 一次插入O(n)
  • 一次删除O(1)
  • 平均操作n次O(n2)

无序:

  • 一次插入O(1)
  • 一次删除O(n)
  • 平均操作n次O(n2)

堆:

  • 一次插入O(nlogn)
  • 一次删除O(nlogn)
  • 平均操作n次O(nlogn)

要知道,nlogn和n2的复杂度相差很多,所以我们使用堆来实现优先级队列,代码如下,可以直接补在上面的代码中,优先级队列每次出列都是出优先级最小或最大的一个元素(也可以说是值最小,这要看怎么去设计),所以优先级队列只是保证根节点以及堆的特性,并不保证堆这个数组的有序性。

  • 优先级队列的插入操作:将节点放到最后一个元素x[n+1]中(如何动态构建数组根据语言来定),然后调整x[n+1]用ShiftUp函数保证满足堆得性质。
  • 优先级队列的删除操作:取出第一个元素x[0],并将x[n]放到x[0]中,然后用ShiftDown函数将顶部节点下移以保证堆的特性(ShiftDown时还要将变换的节点上移)。

代码和丰富的注释如下。

//优先级队列操作后是无序的堆
//插入操作
public static void Insert(int[] arr, int num)
{
    
int[] arrs = new int[arr.Length + 1];
    CopyTo(arr, arrs,
0);
    arrs[arr.Length]
= num;

    ShiftUp(arrs, arrs.Length - 1);

    numbers = arrs;
}

//删除操作
public static void Delete(int[] arr)
{
    
int ret = arr[0];
    
int[] arrs = new int[arr.Length - 1];
    CopyTo(arr, arrs,
1);

    Swap(ref arrs[0], ref arrs[arrs.Length - 1]);
    ShiftDown(arrs, arrs.Length,
0);

    numbers = arrs;
}

//CopyTo,动态修改数组
//不过这个地方我没有用动态数组,因为C/C++无法使用动态数组
//在实现的地方这里可以因语言不通而异
public static void CopyTo(int[] arr0, int[] arr1, int index)
{
    
for (int i = index, j = 0; i < arr0.Length + index && j < arr1.Length; i++, j++)
    {
        arr1[j]
= arr0[i];
    }
}

//将元素向上提
public static void ShiftUp(int[] arr, int index)
{
    
int pindex = (index - 1) / 2;
    
int large = index;

    if (pindex >= 0 && arr[pindex] > arr[index])
    {
        large
= pindex;
    }

    if (large != index)
    {
        Swap(
ref arr[pindex], ref arr[index]);
        ShiftUp(arr, large);
    }
}

//将元素向下放
public static void ShiftDown(int[] arr, int heapSize, int index)
{
    
int left = 2 * index + 1; // 左子节点  
    int right = 2 * index + 2; // 右子节点  
    int large = index; // 临时变量,存放大/小的节点值
    
//小根堆这里是比较小节点,大根堆是比较大节点
    
//大根堆
    
//if (left < heapSize && arr[left] > arr[large])
    
// 比较左子节点  
    if (left < heapSize && arr[left] < arr[large])
    {
        large
= left;
    }

    // 比较右子节点  
    if (right < heapSize && arr[right] < arr[large])
    {
        large
= right;
    }

    if (index != large)
    {
        Swap(
ref arr[index], ref arr[large]);
        ShiftUp(arr, index);
        ShiftDown(arr, heapSize, large);
    }
}

堆和优先级队列在一般的工程应用中除非是特殊情况我们一般是使用不到的,但是对于比较多的数据的性能提高而言,我们可以使用堆排序,另外,堆排序还可以优先级队列进行排序,当我们将元素全部插入到优先级队列之后再全部拿出数据,就是一个有序的结果集了,但是普通的优先级队列的排序方法需要使用n+1个内存,不过我们可以优化它,这里就不再深入描述了。

2009/12/5 附 C++代码

#include <iostream>
#include
<string>

#ifndef CONST
#define MAX 10
#endif

using namespace std;

class Heap
{
    
public:
        Heap();
        
void Init();
        
void Sort();
        
void OutPut();
    
private:
        
int numbers[MAX];
        
void MakeToBigHeap();
        
void MaxHeap(int n[],int heapsize,int i);
        
void Swap(int n[],int i,int j);
};

Heap::Heap()
{
    
}

void Heap::Init()
{
    
for(int i=MAX;i>=0;i)
    {
        numbers[i]
=i;
    }
}

void Heap::Sort()
{
    MakeToBigHeap();

    for(int i=MAX-1;i>0;i)
    {
        Swap(numbers,
0,i);
        MaxHeap(numbers,i,
0);
    }
}

void Heap::OutPut()
{
    
for(int i=0;i<MAX;i++)
    {
        cout
<<numbers[i]<<endl;
    }
}

void Heap::Swap(int n[],int i,int j)
{
    n[i]
= n[i]^n[j];
    n[j]
= n[i]^n[j];
    n[i]
= n[i]^n[j];
}

void Heap::MaxHeap(int n[],int heapsize,int i)
{
    
int left  = 2*i+1;
    
int right = 2*i+2;
    
int big = i;

    if(left<heapsize&&n[left]>n[big])
    {
        big
= left;
    }

    if(right<heapsize&&n[right]>n[big])
    {
        big
= right;
    }

    if(i!=big)
    {
        Swap(n,i,big);
        MaxHeap(n,heapsize,big);
    }
}

void Heap::MakeToBigHeap()
{
    
for(int i=MAX/2-1;i>=0;i)
    {
        MaxHeap(numbers,MAX,i);
    }
}

int main()
{
    Heap
* heap = new Heap();
    heap
->Init();
    heap
->OutPut();
    cout
<<"after sort"<<endl;
    heap
->Sort();
    heap
->OutPut();
    
return 0;
}

926路过 1评论 数据结构 阅读全文..
2009年11月16日

题目:一个好汉三个帮,三个好汉九个帮,九个好汉二十七个帮,…停,今天不是让你算n个好汉几个帮(有兴趣的网友可以自己算),我们来看这个集合

{ 1, 3, 9, 27, 81, … }

这个集合是一个递增的无限集,每个元素都是3的幂。

我们把这个集合的所有子集按照元素和从小到大的顺序排好: {}(空集), { 1 }, { 3 }, { 1, 3 }, { 9 }, { 1, 9 }, { 3, 9 }, { 1, 3, 9 }, …

现在给定一个正整数n,求第n个子集的所有元素,并按从大到小的顺序排列好

例:

n的值    结果
1        { }
4        { 3, 1 }
6        { 9, 1 }
500      { 6561, 2187, 729, 243, 81, 3, 1 }

题目:给出一个包含各种括号的表达式,判断括号是否配对。括号配对的条件:括号必须先左后右,并且左右括号数量相等;对于多重括号,从外到内嵌套顺序为:{} -> [] -> () -> <>。例如{[(<>)]}。

接口: bool match(char* str);   合法返回true, 否则返回false。

输入范例:
{[(<>)]}
{}
<(>)
<()>

返回:
true
true
false
false

来自编程爱好者编程比赛题。

Answer1
2009年11月15日

题目:训练场上n(1≤n≤50000)个高矮都不相同的士兵从左到右排 成一行,依次编号为1,2,…,n。第i个士兵的身高H(i),由于采用特殊单位,H(i)满足1≤H(i)≤2000000000。设第i个士兵右侧最 近的比他个高的士兵编号为j,则第i个士兵可看到在他的右侧比他矮的士兵的个数S(i)=j-i-1。(不考虑客观因素,比如视力范围等-,-)
求S(1)+S(2)+…+S(n)。

输入:
标准输入。
第一行为整数n,表示士兵的个数。
第二行n个整数,用一个空格隔开。分别表示编号为1,2。。。n的士兵的身高

输出:
S(1)+S(2)+…+S(n)的结果

例:
输入
6
10 3 7 4 12 2
输出
5

例子说明:
S(1) = 3
S(2) = 0
S(3) = 1
S(4) = 0
S(5) = 1
S(6) = 0
S(1)+S(2)+S(3)+S(4)+S(5)+S(6) = 3+0+1+0+1+0 = 5

Answer
2009年11月10日

首先先说一下LRU算法是什么。

LRU是关于操作系统的内存管理,如何节省利用容量不大的内存为最多的进程提供资源,一直是研究的重要方向的其中一种算法。在操作系统开发和管理的时候,为了提高内存的使用率,提高内存的性能,就需要使用某种算法来管理。使用扩展内存或者虚拟内存能够极大的方便操作系统对内存的管理和提高内存的能力,也就是常常我们说的虚拟内存了。当程序载入的时候,这个时候操作系统会读取一部分到内存中,一些信息段会存储需要调用的内存在磁盘上的地址。例如一个程序要读文件,在载入时,读文件的方法并没有载入到内存中,当需要读文件时,操作系统可能才把相应的内存给载入到寄存器,这样虽然提高了内存的功能,但是却加大了交互。所以就想到可以设计算法来减少交互,提高效率。LRU就是为了这个需求设计的算法中的一种。

LRU一般有两种算法:

计时法:给页表中的每一页增加一个域(也就是计时器),专门用来存放计时标志,用来记录该页面自上次被访问以来所经历的时间。页面每被访问一次,计时清0。要装入新页时,从内存的页面中选出时间最长的一页,调出,同时把各页的计时标志全部清0,重新开始计时。

链表法:操作系统为每个进程维护一条链表,链表的每个结点记录一张页面的地址。调用一次页面,则把该页面的结点从链中取出,放到链尾;要装入新页,则把链头的页面调出,同时将调入的页面结点放置到链尾。

计时法需要维护所有的页面的域,性能并不会很好,链表法提升了部分性能,但是并不能在数量级上得到提升,因为将链表放置到尾部也是很消耗性能的。下面我给出链表法的C#代码(最简单普通的,关于LRU链表法优化不提及)。

namespace LRU
{
    
public class LRUList
    
{
        
public int pageNum;
        
public LRUList next;
    }


    
class Program
    
{
        
static LRUList plist;

        
static void Main(string[] args)
        
{
            CreateList();
            PrintList();
            LRU(
0);
            PrintList();
            LRU(
1);
            
//LRU(7);
            PrintList();
            Add(
99);
            Add(
99);
            LRU(
99);
            PrintList();
            Console.ReadKey();
        }


        
//LRU主算法
        static void LRU(int pageNum)
        
{
            LRUList list
= plist;
            LRUList slist
= list;
            LRUList tempList
= new LRUList();
            tempList.next
= null;

            
if (list.pageNum == pageNum)
            
{
                tempList.pageNum
= list.pageNum;
                list
= list.next;
                slist
= list;
            }


            
while (list.next != null)
            
{
                
if (list.next.pageNum == pageNum)
                
{
                    tempList
= list.next;
                    list.next
= list.next.next;
                    tempList.next
= null;
                }

                list
= list.next;
            }

            list.next
= tempList;
            plist
= slist;
        }


        
//增加一个页面
        static void Add(int pageNum)
        
{
            LRUList list
= new LRUList();
            list.pageNum
= pageNum;
            list.next
= null;
            plist
= plist.next;
            LRUList slist
= plist;

            
while (slist.next != null)
            
{
                slist
= slist.next;
            }


            slist.next
= list;
        }


        
一些创建和输出的代码
    }

}

上面的代码模拟了LRU算法,我们也可以通过LRU算法去计算缺页中断,对比FIFO算法的缺页中断效率。

LRU算法在很多场合都在使用,例如数据库的开发中,也可以使用LRU算法进行性能和效率的提升,例如著名的甲骨文,是使用LRU算法维护一段链表(具体模拟我会在后文写出)。数据库即是一堆数据以文件等形式存储在磁盘中,这就要求数据库管理软件能够快速的进行数据库文件的管理,当查询语句进行查询时,就转换成相应的操作将磁盘上的文件结果显示到数据库软件中,而文件在磁盘上,I/O的性能是很慢的,所以这个时候我们就需要将一定的数据读入到缓冲区内,然后通过Hash表和链表对缓冲区进行维护,这个时候链表就需要使用LRU算法进行维护,提高命中的效率。

当然,用Hash表去维护链表然后使用LRU算法命中也是提高效率的一个很好的方法。

536路过 1评论 数据结构 阅读全文..
2009年10月31日

问题描述:我们通常把一个数组里面出现的次数最多的数字称为众数,那么众数中,如果比例超过一半了,我们可以叫这个数字为这个数组的支配者,如{1,2,3,4,1,1,1,1,1,8,8}数组中,1就为这个数组的支配者,求支配者的数字并且求出支配者在数组中的索引。

众数问题:其实从支配者问题中,我们可以很容易的了解众数问题,只要加以修改即可。下面写我的思路(支配者问题)。

首先遍历一遍数组,每个数组放到一个Hash表里面,并把当前的数字的索引放到这个Hash表里(数字作为key),Hash表的结构为<int,List<int>>,也就是两个散列表。这样遍历一次就能够知道所有的数字和相应的索引。其次,如何知道是不是支配者,这里有个技巧,支配者在数组中,必然是两个相等的数字连在一起,如(1,1),前面我没说清楚,如果对这个有疑问,可以看评论,因为支配者的个数在N/2个以上,所以我们每次遍历的时候把可能是支配者的数字放到另一个链表中即可。这个时候我们遍历了一次(O(N)),然后我们最后再维护支配者的候选的节点就可以了,如{1,2,3,4,1,1,1,1,1,8,8},我们会最后得到一个List,List里面存放两个支配者,1和8,最后我们遍历2次就能知道1是支配者,而8不是,这样就相当于遍历了一次数组,和一次筛选后的小型数组。而对于小型数组而言,最坏的情况的次数也只是N/2。

namespace FindHeavyNumber
{
class Program
{
static Dictionary<int,List<int>> numbers;
static List<int> hNumbers;
static int heavyNumber = -100;
static bool isFined = false;

static void Main(string[] args)
{
int[] words = { 1,2,1,3,1,4,1 ,1,8,2,1,1,3};
FindHeavy(words);
Output(words.Length);
}


static void FindHeavy(int[] array)
{
int fIndex = 0;
int lIndex = 0;
hNumbers
= new List<int>