fork(1) download
copy 
  1. import java.util.*;
  2.  
  3. class Main {
  4.     public static void main(String[] args) {
  5.         String[] data = {"red", "green", "blue", "red", "yellow", "red", "black", "red", "blue", "white", "green"};
  6.         final int size = 4;
  7.  
  8. //        System.out.println("\n##### Teste com FIFO #####");
  9. //        fifo(size, data);
  10. //
  11. //        System.out.println("\n##### Teste com LRU #####");
  12. //        lru(size, data);
  13.  
  14.         System.out.println("\n##### Teste com LFU #####");
  15.         lfu(size, data);
  16.     }
  17.  
  18.     static void fifo(final int size, final String[] data) {
  19.         ArrayDeque<String> cache = new ArrayDeque<>();
  20.  
  21.         int misses = 0, hit = 0, access = 0;
  22.  
  23.         for (String d : data) {
  24.             if (!cache.contains(d)) {
  25.                 if (cache.size() < size) {
  26.                     cache.add(d);
  27.                 } else {
  28.                     cache.remove();
  29.                     cache.add(d);
  30.                 }
  31.  
  32.                 misses++;
  33.             } else {
  34.                 hit++;
  35.             }
  36.  
  37.             access++;
  38.  
  39.             System.out.printf("access: %d, hit: %d, misses: %d >>> %s\n[ ", access, hit, misses, d);
  40.  
  41.             for (String x : cache) System.out.print(x + " ");
  42.  
  43.             System.out.println("]");
  44.         }
  45.     }
  46.  
  47.     static void lru(final int size, final String[] data) {
  48.         ArrayDeque<String> cache = new ArrayDeque<>();
  49.  
  50.         int misses = 0, hit = 0, access = 0;
  51.  
  52.         for (String d : data) {
  53.             if (!cache.contains(d)) {
  54.                 if (cache.size() < size) {
  55.                     cache.add(d);
  56.                 } else {
  57.                     cache.remove();
  58.                     cache.add(d);
  59.                 }
  60.  
  61.                 misses++;
  62.             } else {
  63.                 cache.remove(d);
  64.                 cache.add(d);
  65.  
  66.                 hit++;
  67.             }
  68.  
  69.             access++;
  70.  
  71.             System.out.printf("access: %d, hit: %d, misses: %d >>> %s\n[ ", access, hit, misses, d);
  72.  
  73.             for (String x : cache) System.out.print(x + " ");
  74.  
  75.             System.out.println("]");
  76.         }
  77.     }
  78.  
  79.     static void lfu(final int size, final String[] data) {
  80.         class DataWrapper implements Comparable<DataWrapper> {
  81.             private final String data;
  82.             private int frequency;
  83.  
  84.             DataWrapper(String data) {
  85.                 this.data = data;
  86.                 incrementFrequency();
  87.             }
  88.  
  89.             void incrementFrequency() {
  90.                 this.frequency++;
  91.             }
  92.  
  93.             @Override
  94.             public boolean equals(Object o) {
  95.                 DataWrapper dw = (DataWrapper) o;
  96.                 return dw.data.equals(this.data);
  97.             }
  98.  
  99.             @Override
  100.             public int compareTo(DataWrapper o) {
  101.                 if (this.frequency > o.frequency)
  102.                     return 1;
  103.                 else if (this.frequency < o.frequency)
  104.                     return -1;
  105.                 else
  106.                     return 0;
  107.             }
  108.  
  109.             @Override
  110.             public String toString() {
  111.                 return data;
  112.             }
  113.         }
  114.  
  115.         List<DataWrapper> cache = new ArrayList<>();
  116.         List<DataWrapper> temp = new ArrayList<>();
  117.  
  118.         int misses = 0, hit = 0, access = 0;
  119.  
  120.         for (String d : data) temp.add(new DataWrapper(d));
  121.  
  122.         for (DataWrapper d : temp) {
  123.             if (!cache.contains(d)) {
  124.                 if (cache.size() < size) {
  125.                     cache.add(d);
  126.                 } else {
  127.                     Object[] aux = cache.toArray();
  128.                     Arrays.sort(aux);
  129.  
  130.                     int pos = cache.indexOf( aux[0] );
  131.  
  132.                     cache.remove( aux[0] );
  133.                     cache.add(pos, d);
  134.                 }
  135.  
  136.                 misses++;
  137.             } else {
  138.                 cache.get(cache.indexOf(d)).incrementFrequency();
  139.                 hit++;
  140.             }
  141.  
  142.             access++;
  143.  
  144.             System.out.printf("access: %d, hit: %d, misses: %d >>> %s\n[ ", access, hit, misses, d);
  145.  
  146.             for (DataWrapper x : cache) System.out.printf("%s(%d) ", x, x.frequency);
  147.  
  148.             System.out.println("]");
  149.         }
  150.     }
  151. }
Success #stdin #stdout 0.06s 4386816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
##### Teste com LFU #####
access: 1, hit: 0, misses: 1 >>> red
[ red(1) ]
access: 2, hit: 0, misses: 2 >>> green
[ red(1) green(1) ]
access: 3, hit: 0, misses: 3 >>> blue
[ red(1) green(1) blue(1) ]
access: 4, hit: 1, misses: 3 >>> red
[ red(2) green(1) blue(1) ]
access: 5, hit: 1, misses: 4 >>> yellow
[ red(2) green(1) blue(1) yellow(1) ]
access: 6, hit: 2, misses: 4 >>> red
[ red(3) green(1) blue(1) yellow(1) ]
access: 7, hit: 2, misses: 5 >>> black
[ red(3) black(1) blue(1) yellow(1) ]
access: 8, hit: 3, misses: 5 >>> red
[ red(4) black(1) blue(1) yellow(1) ]
access: 9, hit: 4, misses: 5 >>> blue
[ red(4) black(1) blue(2) yellow(1) ]
access: 10, hit: 4, misses: 6 >>> white
[ red(4) white(1) blue(2) yellow(1) ]
access: 11, hit: 4, misses: 7 >>> green
[ red(4) green(1) blue(2) yellow(1) ]
https://ideone.com/dX2EvF
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!