fork(2) download
copy 
  1. import java.util.*;
  2.  
  3. class Program {
  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.             cache.forEach((x) -> System.out.print(x + " "));
  41.             System.out.println("]");
  42.         }
  43.     }
  44.  
  45.     static void lru(final int size, final String[] data) {
  46.         ArrayDeque<String> cache = new ArrayDeque<>();
  47.  
  48.         int misses = 0, hit = 0, access = 0;
  49.  
  50.         for (String d : data) {
  51.             if (!cache.contains(d)) {
  52.                 if (cache.size() < size) {
  53.                     cache.add(d);
  54.                 } else {
  55.                     cache.remove();
  56.                     cache.add(d);
  57.                 }
  58.  
  59.                 misses++;
  60.             } else {
  61.                 cache.remove(d);
  62.                 cache.add(d);
  63.  
  64.                 hit++;
  65.             }
  66.  
  67.             access++;
  68.  
  69.             System.out.printf("access: %d, hit: %d, misses: %d >>> %s\n[ ", access, hit, misses, d);
  70.             cache.forEach((x) -> System.out.print(x + " "));
  71.             System.out.println("]");
  72.         }
  73.     }
  74.  
  75.     static void lfu(final int size, final String[] data) {
  76.         class DataWrapper implements Comparable<DataWrapper> {
  77.             private final String data;
  78.             private int frequency;
  79.  
  80.             DataWrapper(String data) {
  81.                 this.data = data;
  82.                 incrementFrequency();
  83.             }
  84.  
  85.             void incrementFrequency() {
  86.                 this.frequency++;
  87.             }
  88.  
  89.             @Override
  90.             public boolean equals(Object o) {
  91.                 DataWrapper dw = (DataWrapper) o;
  92.                 return dw.data.equals(this.data);
  93.             }
  94.  
  95.             @Override
  96.             public int compareTo(DataWrapper o) {
  97.                 if (this.frequency > o.frequency)
  98.                     return 1;
  99.                 else if (this.frequency < o.frequency)
  100.                     return -1;
  101.                 else
  102.                     return 0;
  103.             }
  104.  
  105.             @Override
  106.             public String toString() {
  107.                 return data;
  108.             }
  109.         }
  110.  
  111.         List<DataWrapper> cache = new ArrayList<>();
  112.         List<DataWrapper> temp = new ArrayList<>();
  113.  
  114.         int misses = 0, hit = 0, access = 0;
  115.  
  116.         for (String d : data) temp.add(new DataWrapper(d));
  117.  
  118.         for (DataWrapper d : temp) {
  119.             if (!cache.contains(d)) {
  120.                 if (cache.size() < size) {
  121.                     cache.add(d);
  122.                 } else {
  123.                     cache.remove(0);
  124.                     cache.add(d);
  125.                 }
  126.  
  127.                 misses++;
  128.             } else {
  129.                 cache.get(cache.indexOf(d)).incrementFrequency();
  130.                 hit++;
  131.             }
  132.  
  133.             Collections.sort(cache);
  134.             access++;
  135.  
  136.             System.out.printf("access: %d, hit: %d, misses: %d >>> %s\n[ ", access, hit, misses, d);
  137.             cache.forEach((x) -> System.out.printf("%s(%d) ", x, x.frequency));
  138.             System.out.println("]");
  139.         }
  140.     }
  141. }
Success #stdin #stdout 0.15s 4386816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
##### Teste com FIFO #####
access: 1, hit: 0, misses: 1 >>> red
[ red ]
access: 2, hit: 0, misses: 2 >>> green
[ red green ]
access: 3, hit: 0, misses: 3 >>> blue
[ red green blue ]
access: 4, hit: 1, misses: 3 >>> red
[ red green blue ]
access: 5, hit: 1, misses: 4 >>> yellow
[ red green blue yellow ]
access: 6, hit: 2, misses: 4 >>> red
[ red green blue yellow ]
access: 7, hit: 2, misses: 5 >>> black
[ green blue yellow black ]
access: 8, hit: 2, misses: 6 >>> red
[ blue yellow black red ]
access: 9, hit: 3, misses: 6 >>> blue
[ blue yellow black red ]
access: 10, hit: 3, misses: 7 >>> white
[ yellow black red white ]
access: 11, hit: 3, misses: 8 >>> green
[ black red white green ]

##### Teste com LRU #####
access: 1, hit: 0, misses: 1 >>> red
[ red ]
access: 2, hit: 0, misses: 2 >>> green
[ red green ]
access: 3, hit: 0, misses: 3 >>> blue
[ red green blue ]
access: 4, hit: 1, misses: 3 >>> red
[ green blue red ]
access: 5, hit: 1, misses: 4 >>> yellow
[ green blue red yellow ]
access: 6, hit: 2, misses: 4 >>> red
[ green blue yellow red ]
access: 7, hit: 2, misses: 5 >>> black
[ blue yellow red black ]
access: 8, hit: 3, misses: 5 >>> red
[ blue yellow black red ]
access: 9, hit: 4, misses: 5 >>> blue
[ yellow black red blue ]
access: 10, hit: 4, misses: 6 >>> white
[ black red blue white ]
access: 11, hit: 4, misses: 7 >>> green
[ red blue white green ]

##### 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
[ green(1) blue(1) red(2) ]
access: 5, hit: 1, misses: 4 >>> yellow
[ green(1) blue(1) yellow(1) red(2) ]
access: 6, hit: 2, misses: 4 >>> red
[ green(1) blue(1) yellow(1) red(3) ]
access: 7, hit: 2, misses: 5 >>> black
[ blue(1) yellow(1) black(1) red(3) ]
access: 8, hit: 3, misses: 5 >>> red
[ blue(1) yellow(1) black(1) red(4) ]
access: 9, hit: 4, misses: 5 >>> blue
[ yellow(1) black(1) blue(2) red(4) ]
access: 10, hit: 4, misses: 6 >>> white
[ black(1) white(1) blue(2) red(4) ]
access: 11, hit: 4, misses: 7 >>> green
[ white(1) green(1) blue(2) red(4) ]
https://ideone.com/7f6jdt
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!