Posted 2019-04-06算法2 minutes read (About 327 words)

生产者消费者

维基百科解释：

In computing, the producer–consumer problem[1][2] (also known as the bounded-buffer problem) is a classic example of a multi-process synchronization problem. The problem describes two processes, the producer and the consumer, who share a common, fixed-size buffer used as a queue. The producer’s job is to generate data, put it into the buffer, and start again. At the same time, the consumer is consuming the data (i.e., removing it from the buffer), one piece at a time. The problem is to make sure that the producer won’t try to add data into the buffer if it’s full and that the consumer won’t try to remove data from an empty buffer.

import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

/**
 * @Author: cuzz
 * @Date: 2019/4/6 13:03
 * @Description: 生产者消费者
 */
public class ProducerConsumerDemo {
    public static void main(String[] args) {
        Container container = new Container();
        ExecutorService executor = Executors.newFixedThreadPool(2);
        executor.execute(() -> container.produce());
        executor.execute(() -> container.consume());
        executor.shutdown();
    }
}

class Container {
    private List<Integer> list = new LinkedList<>();
    private final int MAX_SIZE = 5;

    private Random random = new Random();

    public void produce() {
        while (true) {
            synchronized (this) {
                try {
                    while (list.size() >= MAX_SIZE) {
                        wait();
                    }
                    int i = random.nextInt();
                    System.out.println("produce..." + i);
                    list.add(i);
                    notify();
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    public void consume() {
        while (true) {
            try {
                synchronized (this) {
                    while (list.isEmpty()) {
                        wait();
                    }
                    int i = list.remove(0);
                    System.out.println("consume..." + i);
                    notify();
                    Thread.sleep(1000);
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

Posted 2019-03-16算法2 minutes read (About 329 words)

LRUCache

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高” 。

代码：

/**
 * @Author: cuzz
 * @Date: 2019/3/16 15:35
 * @Description: LRU cache
 */
public class LRUCache {

    private Map<Integer, DLinkedList> cache = new HashMap<>();
    private int count;
    private int capacity;
    private DLinkedList head, tail;

    public LRUCache(int capacity) {
        this.count = 0;
        this.capacity = capacity;

        this.head = new DLinkedList();
        this.tail = new DLinkedList();

        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        DLinkedList node = cache.get(key);
        if (node == null) {
            return -1;
        }
        removeNode(node);
        addHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedList node = cache.get(key);
        if (node == null) {
            node = new DLinkedList(key, value);
            addHead(node);
            cache.put(key, node);
            count++;
            if (count > capacity) {
                DLinkedList preTail = tail.pre;
                removeNode(preTail);
                cache.remove(preTail.key);
                count--;
            }
        } else {
            node.value = value;
            removeNode(node);
            addHead(node);
        }

    }

    // 移除给定的结点
    private void removeNode(DLinkedList node) {
        DLinkedList pre = node.pre;
        DLinkedList next = node.next;
        pre.next = next;
        next.pre = pre;
    }

    // 把结点添加头节点
    private void addHead(DLinkedList node) {
        DLinkedList next = head.next;
        head.next = node;
        node.next = next;
        next.pre = node;
        node.pre = head;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);                    
        System.out.println(cache.get(1));   // 返回 1
        cache.put(3, 3);                    // 使 2 作废
        System.out.println(cache.get(2));   // 返回 -1
        cache.put(4, 4);                    // 使 1 作废
        System.out.println(cache.get(1));   // 返回 -1 未找到
        System.out.println(cache.get(3));   // 返回 3
        System.out.println(cache.get(4));   // 返回 4
    }

}

class DLinkedList {
    int key;
    int value;
    DLinkedList pre;
    DLinkedList next;

    public DLinkedList() {};

    public DLinkedList(int key, int value) {
        this.key = key;
        this.value = value;
    }
}