2016头条校招笔试题(LRU)算法之JAVA实现

操作系统中可以使用LRU(Least Recently Used)内存淘汰旧数据的策略,如果内存需要加载新数据但空间不足,则会按照最近访问时间进行排序,并将最老的数据淘汰。假设现在内存空间大小为5,原本内存中没有数据,对内存中数据的访问顺序如下:1, 2, 5, 3, 4, 6,1, 4, 3, 6, 7, 8, 3, 9 问访问过程中发生缺页的次数是多少次?

JAVA实现:
首先实现一个固定长度的集合队列

package com.itstyle.list;

import java.util.Collection;  
import java.util.Iterator;  
import java.util.LinkedList;  
import java.util.Queue;  
  
/** 
 * 实现一个固定长度的集合队列 
 * 在开发中,有时候我们会遇到这样的需求:
 * 对一个集合操作,提前为集合指定最大大小,在我们不断向集合中添加数据的时候,当数据内容超过最大值的时候,自动将最先入队的元素移除队列。
 * @param <E> 
 */  
public class LimitQueue<E> implements Queue<E> {  
  
    /** 
     * 队列长度,实例化类的时候指定  
     */  
    private int limit;    
        
    Queue<E> queue = new LinkedList<E>();    
        
    public LimitQueue(int limit){    
        this.limit = limit;    
    }
        
    /** 
     * 入队 
     */  
    @Override    
    public boolean offer(E e){    
        if(queue.size() >= limit){    
            //如果超出长度,入队时,先出队    
            queue.poll();    
        }  
        return queue.offer(e);    
    }    
        
    /** 
     * 出队  
     */  
    @Override    
    public E poll() {    
        return queue.poll();    
    }    
        
    /** 
     * 获取队列  
     */  
    public Queue<E> getQueue(){    
        return queue;    
    }    
        
    /** 
     * 获取限制大小 
     */  
    public int getLimit(){    
        return limit;    
    }    
    
    @Override    
    public boolean add(E e) {    
        return queue.add(e);    
    }    
    
    @Override    
    public E element() {    
        return queue.element();    
    }    
    
    @Override    
    public E peek() {    
        return queue.peek();    
    }    
    
    @Override    
    public boolean isEmpty() {    
        return queue.size() == 0 ? true : false;    
    }    
    
    @Override    
    public int size() {    
        return queue.size();    
    }    
    
    @Override    
    public E remove() {    
        return queue.remove();    
    }    
    
    @Override    
    public boolean addAll(Collection<? extends E> c) {    
        return queue.addAll(c);    
    }    
    
    @Override    
    public void clear() {    
        queue.clear();    
    }    
    
    @Override    
    public boolean contains(Object o) {    
        return queue.contains(o);    
    }    
    
    @Override    
    public boolean containsAll(Collection<?> c) {    
        return queue.containsAll(c);    
    }    
    
    @Override    
    public Iterator<E> iterator() {    
        return queue.iterator();    
    }    
    
    @Override    
    public boolean remove(Object o) {    
        return queue.remove(o);    
    }    
    
    @Override    
    public boolean removeAll(Collection<?> c) {    
        return queue.removeAll(c);    
    }    
    
    @Override    
    public boolean retainAll(Collection<?> c) {    
        return queue.retainAll(c);    
    }    
    
    @Override    
    public Object[] toArray() {    
        return queue.toArray();    
    }    
    
    @Override    
    public <T> T[] toArray(T[] a) {    
        return queue.toArray(a);    
    }    
}  

执行方法:

package com.itstyle.list;

import java.util.ArrayList;
import java.util.List;


/**
 * 操作系统中可以使用LRU(Least Recently Used)内存淘汰旧数据的策略,如果内存需要加载新数据但空间不足,
 * 则会按照最近访问时间进行排序,并将最老的数据淘汰。假设现在内存空间大小为5,原本内存中没有数据,对内存中数据的访问顺序如下:
 * 1, 2, 5, 3, 4, 6,1, 4, 3, 6, 7, 8, 3, 9 问访问过程中发生缺页的次数是多少次?
 *
 */
public class LRU {
    public static void main(String[] args) {
        LimitQueue<String> list = new LimitQueue<String>(5);
        Integer[] array = new  Integer[]{1, 2, 5, 3, 4, 6,1, 4, 3, 6, 7, 8, 3, 9 };
        List<Integer> page = new ArrayList<Integer>();
        for(Integer i :array){
            if(list.contains(i.toString())){
                list.remove(i);
            }else{
                page.add(i);
            }
            list.offer(i.toString()); 
        }
        System.out.println("缺页数量"+page.size()+",缺页数据"+page.toString());
    }
}

最终执行结果:缺页数量10,缺页数据[1, 2, 5, 3, 4, 6, 1, 7, 8, 9]

qrcode_for_gh_bf7a27ade681_258.jpg

作者: 小柒

出处: https://blog.52itstyle.com

分享是快乐的,也见证了个人成长历程,文章大多都是工作经验总结以及平时学习积累,基于自身认知不足之处在所难免,也请大家指正,共同进步。

本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出, 如有问题, 可邮件(345849402@qq.com)咨询。