編集履歴

質問編集履歴

誤字など修正

2017/10/12 00:33

投稿

mosa

スコア218

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -136,7 +136,7 @@
  * キャッシュなし
- * LRUしないキャッシュ
+ * LRUで削除しないキャッシュ
  * Collections.syncronizedMap() で排他するLRUキャッシュ
@@ -172,11 +172,11 @@
 class NonCache<K, V> implements Calculator<K, V>{
-    private Function<K, V> initializer;
+  private Function<K, V> initializer;
-    NonCache(Function<K, V> initializer){ this.initializer = initializer; }
+  NonCache(Function<K, V> initializer){ this.initializer = initializer; }
-@Override public V get(K key){ return initializer.apply(key); }
+  @Override public V get(K key){ return initializer.apply(key); }
 }
@@ -186,106 +186,106 @@
 class NonLruCache<K, V> implements Calculator<K, V>{
-    private int capacity;
+  private int capacity;
-    private Function<K, V> initializer;
+  private Function<K, V> initializer;
-    private Map<K, V> map = new LinkedHashMap<>(capacity, 1.0f, true);
+  private Map<K, V> map = new LinkedHashMap<>(capacity, 1.0f, true);
-    NonLruCache(int capacity, Function<K, V> initializer){
+  NonLruCache(int capacity, Function<K, V> initializer){
-        this.capacity = capacity;
+    this.capacity = capacity;
-        this.initializer = initializer;
+    this.initializer = initializer;
+  }
+  @Override public V get(K key){ return map.computeIfAbsent(key, initializer); }
+}
+// Collections.syncronizedMap() で排他するLRUキャッシュ
+class LruCache1<K, V> implements Calculator<K, V>{
+  private int capacity;
+  private Function<K, V> initializer;
+  private Map<K, V> map = Collections.synchronizedMap(new LinkedHashMap<K, V>(capacity, 1.0f, true){
+    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest){ return size() > capacity; }
+  });
+  LruCache1(int capacity, Function<K, V> initializer){
+    this.capacity = capacity;
+    this.initializer = initializer;
+  }
+  @Override public V get(K key){ return map.computeIfAbsent(key, initializer); }
+}
+// StampedLock.writeLock() で排他するLRUキャッシュ
+class LruCache2<K, V> implements Calculator<K, V>{
+  private int capacity;
+  private StampedLock lock = new StampedLock();
+  private Function<K, V> initializer;
+  private Map<K, V> map = new LinkedHashMap<K, V>(capacity, 1.0f, true){
+    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest){ return size() > capacity; }
+  };
+  LruCache2(int capacity, Function<K, V> initializer){
+    this.capacity = capacity;
+    this.initializer = initializer;
+  }
+  @Override public V get(K key){
+    long stamp = lock.writeLock();
+    try{ return map.computeIfAbsent(key, initializer); } finally{ lock.unlockWrite(stamp); }
+  }
+}
+// daisuke7さんに教えていただいたbarakbさんのライブラリ https://github.com/barakb/Cache
+class LruCache3<K, V> implements Calculator<K, V>{
+    private Cache<K, V> cache;
+    LruCache3(int capacity, Function<K, V> initializer){ cache = new Cache<>(initializer::apply, capacity); }
+    @Override public V get(K key){
+        try{ return cache.get(key); } catch(Throwable throwable){ throw new RuntimeException(throwable); }
     }
-    @Override public V get(K key){ return map.computeIfAbsent(key, initializer); }
-}
-// Collections.syncronizedMap() で排他するLRUキャッシュ
-class LruCache1<K, V> implements Calculator<K, V>{
-    private int capacity;
-    private Function<K, V> initializer;
-    private Map<K, V> map = Collections.synchronizedMap(new LinkedHashMap<K, V>(capacity, 1.0f, true){
-        @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest){ return size() > capacity; }
-    });
-    LruCache1(int capacity, Function<K, V> initializer){
-        this.capacity = capacity;
-        this.initializer = initializer;
-    }
-    @Override public V get(K key){ return map.computeIfAbsent(key, initializer); }
-}
-// StampedLock.writeLock() で排他するLRUキャッシュ
-class LruCache2<K, V> implements Calculator<K, V>{
-    private int capacity;
-    private StampedLock lock = new StampedLock();
-    private Function<K, V> initializer;
-    private Map<K, V> map = new LinkedHashMap<K, V>(capacity, 1.0f, true){
-        @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest){ return size() > capacity; }
-    };
-    LruCache2(int capacity, Function<K, V> initializer){
-        this.capacity = capacity;
-        this.initializer = initializer;
-    }
-    @Override public V get(K key){
-        long stamp = lock.writeLock();
-        try{ return map.computeIfAbsent(key, initializer); } finally{ lock.unlockWrite(stamp); }
-    }
-}
-// daisuke7さんに教えていただいたbarakbさんのライブラリ https://github.com/barakb/Cache
-class LruCache3<K, V> implements Calculator<K, V>{
-    private Cache<K, V> cache;
-    LruCache3(int capacity, Function<K, V> initializer){ cache = new Cache<>(initializer::apply, capacity); }
-    @Override public V get(K key){
-        try{ return cache.get(key); } catch(Throwable throwable){ throw new RuntimeException(throwable); }
-    }
 }
@@ -318,87 +318,87 @@
-    public static final int COST = 1000; // 計算コスト
-    public static final int SIZE = 1000; // 要素数
-    public static final double DUPLICATION_RATE = 0.0; // 重複率
-    public static final double CAPACITY_RATE = 1.0; // 容量率
-    public static final int CAPACITY = (int) (Math.round(SIZE * (1.0 - DUPLICATION_RATE) * CAPACITY_RATE)); // 容量
-    public static final List<Integer> LIST = IntStream.rangeClosed(0, SIZE - 1).boxed()
-            .map(it -> (int) ((double) it * (1.0 - DUPLICATION_RATE))).collect(Collectors.toList());
-    public static final int UNIQUE = (int) LIST.stream().distinct().count(); // ユニーク数
-    public static void main(String... args){
-        Function<Integer, Integer> calc = it -> it + IntStream.rangeClosed(1, COST * 10000).sum();
-        Collections.shuffle(LIST); // リストをシャッフル
-        System.out.println("計算コスト:" + COST + " 要素数:" + SIZE + " ユニーク数:" + UNIQUE + " 重複率:" + DUPLICATION_RATE + " 容量:" + CAPACITY + " 容量率:" + CAPACITY_RATE);
-        seri("キャッシュなし", new NonCache<>(calc));
-        para("キャッシュなし", new NonCache<>(calc));
-        seri("LRUなし", new NonLruCache<>(CAPACITY, calc));
-        para("LRUなし", new NonLruCache<>(CAPACITY, calc));
-        seri("LRUキャッシュ1", new LruCache1(CAPACITY, calc));
-        para("LRUキャッシュ1", new LruCache1(CAPACITY, calc));
-        seri("LRUキャッシュ2", new LruCache2(CAPACITY, calc));
-        para("LRUキャッシュ2", new LruCache2(CAPACITY, calc));
-        seri("barakbさんのライブラリ", new LruCache3(CAPACITY, calc));
-        para("barakbさんのライブラリ", new LruCache3(CAPACITY, calc));
-    }
-    private static void seri(String name, Calculator<Integer, Integer> calculator){
-        long start = System.currentTimeMillis();
-        LIST.stream().mapToInt(calculator::get).sum();
-        System.out.println(name + " シリアル " + (System.currentTimeMillis() - start) + "ms. ");
-    }
-    private static void para(String name, Calculator<Integer, Integer> calculator){
-        long start = System.currentTimeMillis();
-        LIST.parallelStream().mapToInt(calculator::get).sum();
-        System.out.println(name + " パラレル " + (System.currentTimeMillis() - start) + "ms. ");
-    }
-}
-```
-### 速度計測結果
+  public static final int COST = 1000; // 計算コスト
+  public static final int SIZE = 1000; // 要素数
+  public static final double DUPLICATION_RATE = 0.0; // 重複率
+  public static final double CAPACITY_RATE = 1.0; // 容量率
+  public static final int CAPACITY = (int) (Math.round(SIZE * (1.0 - DUPLICATION_RATE) * CAPACITY_RATE)); // 容量
+  public static final List<Integer> LIST = IntStream.rangeClosed(0, SIZE - 1).boxed()
+         .map(it -> (int) ((double) it * (1.0 - DUPLICATION_RATE))).collect(Collectors.toList());
+  public static final int UNIQUE = (int) LIST.stream().distinct().count(); // ユニーク数
+  public static void main(String... args){
+    Function<Integer, Integer> calc = it -> it + IntStream.rangeClosed(1, COST * 10000).sum();
+    Collections.shuffle(LIST); // リストをシャッフル
+    System.out.println("計算コスト:" + COST + " 要素数:" + SIZE + " ユニーク数:" + UNIQUE + " 重複率:" + DUPLICATION_RATE + " 容量:" + CAPACITY + " 容量率:" + CAPACITY_RATE);
+    seri("キャッシュなし", new NonCache<>(calc));
+    para("キャッシュなし", new NonCache<>(calc));
+    seri("LRUなし", new NonLruCache<>(CAPACITY, calc));
+    para("LRUなし", new NonLruCache<>(CAPACITY, calc));
+    seri("LRUキャッシュ1", new LruCache1(CAPACITY, calc));
+    para("LRUキャッシュ1", new LruCache1(CAPACITY, calc));
+    seri("LRUキャッシュ2", new LruCache2(CAPACITY, calc));
+    para("LRUキャッシュ2", new LruCache2(CAPACITY, calc));
+    seri("barakbさんのライブラリ", new LruCache3(CAPACITY, calc));
+    para("barakbさんのライブラリ", new LruCache3(CAPACITY, calc));
+  }
+  private static void seri(String name, Calculator<Integer, Integer> calculator){
+    long start = System.currentTimeMillis();
+    LIST.stream().mapToInt(calculator::get).sum();
+    System.out.println(name + " シリアル " + (System.currentTimeMillis() - start) + "ms. ");
+  }
+  private static void para(String name, Calculator<Integer, Integer> calculator){
+    long start = System.currentTimeMillis();
+    LIST.parallelStream().mapToInt(calculator::get).sum();
+    System.out.println(name + " パラレル " + (System.currentTimeMillis() - start) + "ms. ");
+  }
+}
+```
+### ■速度計測結果
@@ -406,7 +406,7 @@
 →「キャッシュなしのパラレル」が当然最速。「LRUなしのパラレル」も排他がないため高速。
-→**「barakbさんのライブラリもパラレル」も高速。すごい。**
+→**「barakbさんのライブラリのパラレル」も高速。すごい。**
@@ -440,7 +440,7 @@
 ### ２．２割重複。キャッシュあふれなし。
-→当然、「キャッシュなし」以外すべて早くなる。
+→当然、「キャッシュなし」以外すべて速くなる。
@@ -474,9 +474,9 @@
 #### ３．８割重複。キャッシュあふれなし。
-→すごく早くなる。キャッシュの効果が大きい。
+→すごく速くなる。キャッシュの効果が大きい。
-→「barakbさんのライブラリもパラレル」があいかわらずすごい。
+→**「barakbさんのライブラリもパラレル」があいかわらずすごい。**
@@ -510,9 +510,9 @@
 #### ４．２割重複。キャッシュあふれあり。
-→LRUがあると当然、やや遅くなる。
+→LRUでの削除があると当然、やや遅くなる。
-→**それでも「barakbさんのライブラリもパラレル」が速い。**
+→**それでも「barakbさんのライブラリもパラレル」が速い。** → 「LRUなしのパラレル」に迫る勢い。

Javaでの速度計測を追記

2017/10/12 00:33

投稿

mosa

スコア218

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -4,7 +4,7 @@
-### 要件
+### ■要件
@@ -32,7 +32,7 @@
-### 質問
+### ■質問
@@ -52,88 +52,42 @@
-### ソースコード　→バグあり
+### ■ソースコード　（ご指摘により一部修正）
 ```Kotlin
+import java.util.*
 class LruCache<K, V>(val capacity: Int, private val initializer: (K) -> V) {
-  private val map = Collections.synchronizedMap(object : LinkedHashMap<K, V>(capacity, 1.0F, true) {
+  private val map = java.util.Collections.synchronizedMap(object : LinkedHashMap<K, V>(capacity, 1.0F, true) {
-    override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>?): Boolean {
+    override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>?) = size > capacity
-      return size > capacity
-    }
   })
-  operator fun get(key: K): V {
-    return map.getOrPut(key) {
-      if (!map.containsKey(key)) map[key] = initializer(key)
+  operator fun get(key: K): V = map.computeIfAbsent(key, initializer)
-      return map[key]!!
-    }
-  }
   override fun toString() = map.toString()
-}
+}
-```
+```
-### ご指摘を受けての修正版ソースコード
+### ■使用例
 ```Kotlin
-import java.util.*
-class LruCache<K, V>(val capacity: Int, private val initializer: (K) -> V) {
-  private val map = java.util.Collections.synchronizedMap(object : LinkedHashMap<K, V>(capacity, 1.0F, true) {
-    override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>?) = size > capacity
-  })
-  operator fun get(key: K): V = map.computeIfAbsent(key, initializer)
-  override fun toString() = map.toString()
-}
-```
-### 使用例
-```Kotlin
 // 容量が3で2倍の値を返し、計算結果をmemoizeするキャッシュ
 val cache = LruCache<Int, Int>(capacity=3) { it * 2 }
@@ -148,7 +102,7 @@
-### 実行結果
+### ■実行結果
@@ -162,96 +116,428 @@
 ---
+### ＝＝＝＝＝＝＝＝追記＝＝＝＝＝＝＝＝
+---
-### ここから追記
+### ■速度計測
-##### **■キャッシュなしの実装** の速度
+キャッシュクラスを５種類用意。（今回はJavaで）
+ * キャッシュなし
+ * LRUしないキャッシュ
+ * Collections.syncronizedMap() で排他するLRUキャッシュ
+ * StampedLock.writeLock() で排他するLRUキャッシュ
+ * daisuke7さんに教えていただいた[barakbさんのライブラリ](https://github.com/barakb/Cache)
-```Kotlin
+```Java
+import org.async.utils.cache.Cache;
+import java.util.Collections;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.concurrent.locks.StampedLock;
+import java.util.function.Function;
+interface Calculator<K, V>{ V get(K key); }
 // キャッシュなし
-val cache = object {
-    operator fun get(key: Int) = Math.sin(key.toDouble()) * Math.cos(key.toDouble()) * Math.tan(key.toDouble())
-}
-// マルチスレッドでアクセス
-val executorService = Executors.newFixedThreadPool(8)
-val start = System.currentTimeMillis()
-(1..10000000).forEach { cache[it / 3] }
-executorService.shutdown()
-println((System.currentTimeMillis() - start).toString() + "ms")
-```
-→10回処理した結果 **平均:7286.2ms** ```7452ms, 7126ms, 7296ms, 7287ms, 7276ms, 7281ms, 7298ms, 7277ms, 7295ms, 7274ms```
-##### **■質問者の実装** の速度
-```Kotlin
-val cache = LruCache<Int, Double>(10000) { Math.sin(it.toDouble()) * Math.cos(it.toDouble()) * Math.tan(it.toDouble()) }
-// あとは一緒
-```
-→10回処理した結果 **平均:2772.7ms** ```3239ms, 3069ms, 2702ms, 2666ms, 2677ms, 2667ms, 2675ms, 2677ms, 2690ms, 2665ms```
-##### **■barakbさんのライブラリ** の速度
-```Kotlin
-val cache = Cache<Int, Double>({ Math.sin(it.toDouble()) * Math.cos(it.toDouble()) * Math.tan(it.toDouble()) }, 10000)
-// あとは一緒
-```
-→10回処理した結果 **平均:3049.1ms** ```3513ms, 3292ms, 3089ms, 2933ms, 2932ms, 2949ms, 2948ms, 2934ms, 2949ms, 2952ms```
+class NonCache<K, V> implements Calculator<K, V>{
+    private Function<K, V> initializer;
+    NonCache(Function<K, V> initializer){ this.initializer = initializer; }
+@Override public V get(K key){ return initializer.apply(key); }
+}
+// LRUしないキャッシュ
+class NonLruCache<K, V> implements Calculator<K, V>{
+    private int capacity;
+    private Function<K, V> initializer;
+    private Map<K, V> map = new LinkedHashMap<>(capacity, 1.0f, true);
+    NonLruCache(int capacity, Function<K, V> initializer){
+        this.capacity = capacity;
+        this.initializer = initializer;
+    }
+    @Override public V get(K key){ return map.computeIfAbsent(key, initializer); }
+}
+// Collections.syncronizedMap() で排他するLRUキャッシュ
+class LruCache1<K, V> implements Calculator<K, V>{
+    private int capacity;
+    private Function<K, V> initializer;
+    private Map<K, V> map = Collections.synchronizedMap(new LinkedHashMap<K, V>(capacity, 1.0f, true){
+        @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest){ return size() > capacity; }
+    });
+    LruCache1(int capacity, Function<K, V> initializer){
+        this.capacity = capacity;
+        this.initializer = initializer;
+    }
+    @Override public V get(K key){ return map.computeIfAbsent(key, initializer); }
+}
+// StampedLock.writeLock() で排他するLRUキャッシュ
+class LruCache2<K, V> implements Calculator<K, V>{
+    private int capacity;
+    private StampedLock lock = new StampedLock();
+    private Function<K, V> initializer;
+    private Map<K, V> map = new LinkedHashMap<K, V>(capacity, 1.0f, true){
+        @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest){ return size() > capacity; }
+    };
+    LruCache2(int capacity, Function<K, V> initializer){
+        this.capacity = capacity;
+        this.initializer = initializer;
+    }
+    @Override public V get(K key){
+        long stamp = lock.writeLock();
+        try{ return map.computeIfAbsent(key, initializer); } finally{ lock.unlockWrite(stamp); }
+    }
+}
+// daisuke7さんに教えていただいたbarakbさんのライブラリ https://github.com/barakb/Cache
+class LruCache3<K, V> implements Calculator<K, V>{
+    private Cache<K, V> cache;
+    LruCache3(int capacity, Function<K, V> initializer){ cache = new Cache<>(initializer::apply, capacity); }
+    @Override public V get(K key){
+        try{ return cache.get(key); } catch(Throwable throwable){ throw new RuntimeException(throwable); }
+    }
+}
+```
+以下のプログラムで実行。（メモリやGCに注意が必要）
+```Java
+import java.util.Collections;
+import java.util.List;
+import java.util.function.Function;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
+public class LruCacheTest{
+    public static final int COST = 1000; // 計算コスト
+    public static final int SIZE = 1000; // 要素数
+    public static final double DUPLICATION_RATE = 0.0; // 重複率
+    public static final double CAPACITY_RATE = 1.0; // 容量率
+    public static final int CAPACITY = (int) (Math.round(SIZE * (1.0 - DUPLICATION_RATE) * CAPACITY_RATE)); // 容量
+    public static final List<Integer> LIST = IntStream.rangeClosed(0, SIZE - 1).boxed()
+            .map(it -> (int) ((double) it * (1.0 - DUPLICATION_RATE))).collect(Collectors.toList());
+    public static final int UNIQUE = (int) LIST.stream().distinct().count(); // ユニーク数
+    public static void main(String... args){
+        Function<Integer, Integer> calc = it -> it + IntStream.rangeClosed(1, COST * 10000).sum();
+        Collections.shuffle(LIST); // リストをシャッフル
+        System.out.println("計算コスト:" + COST + " 要素数:" + SIZE + " ユニーク数:" + UNIQUE + " 重複率:" + DUPLICATION_RATE + " 容量:" + CAPACITY + " 容量率:" + CAPACITY_RATE);
+        seri("キャッシュなし", new NonCache<>(calc));
+        para("キャッシュなし", new NonCache<>(calc));
+        seri("LRUなし", new NonLruCache<>(CAPACITY, calc));
+        para("LRUなし", new NonLruCache<>(CAPACITY, calc));
+        seri("LRUキャッシュ1", new LruCache1(CAPACITY, calc));
+        para("LRUキャッシュ1", new LruCache1(CAPACITY, calc));
+        seri("LRUキャッシュ2", new LruCache2(CAPACITY, calc));
+        para("LRUキャッシュ2", new LruCache2(CAPACITY, calc));
+        seri("barakbさんのライブラリ", new LruCache3(CAPACITY, calc));
+        para("barakbさんのライブラリ", new LruCache3(CAPACITY, calc));
+    }
+    private static void seri(String name, Calculator<Integer, Integer> calculator){
+        long start = System.currentTimeMillis();
+        LIST.stream().mapToInt(calculator::get).sum();
+        System.out.println(name + " シリアル " + (System.currentTimeMillis() - start) + "ms. ");
+    }
+    private static void para(String name, Calculator<Integer, Integer> calculator){
+        long start = System.currentTimeMillis();
+        LIST.parallelStream().mapToInt(calculator::get).sum();
+        System.out.println(name + " パラレル " + (System.currentTimeMillis() - start) + "ms. ");
+    }
+}
+```
+### 速度計測結果
+#### １．重複なし。キャッシュあふれなし。
+→「キャッシュなしのパラレル」が当然最速。「LRUなしのパラレル」も排他がないため高速。
+→**「barakbさんのライブラリもパラレル」も高速。すごい。**
+```
+計算コスト:1000 要素数:1000 ユニーク数:1000 重複率:0.0 容量:1000 容量率:1.0
+キャッシュなし シリアル 3000ms.
+キャッシュなし パラレル 519ms.
+LRUなし シリアル 2998ms.
+LRUなし パラレル 530ms.
+LRUキャッシュ1 シリアル 3004ms.
+LRUキャッシュ1 パラレル 3030ms.
+LRUキャッシュ2 シリアル 3009ms.
+LRUキャッシュ2 パラレル 3029ms.
+barakbさんのライブラリ シリアル 3007ms.
+barakbさんのライブラリ パラレル 514ms.
+```
+### ２．２割重複。キャッシュあふれなし。
+→当然、「キャッシュなし」以外すべて早くなる。
+```
+計算コスト:1000 要素数:1000 ユニーク数:800 重複率:0.2 容量:800 容量率:1.0
+キャッシュなし シリアル 2958ms.
+キャッシュなし パラレル 517ms.
+LRUなし シリアル 2369ms.
+LRUなし パラレル 471ms.
+LRUキャッシュ1 シリアル 2358ms.
+LRUキャッシュ1 パラレル 2393ms.
+LRUキャッシュ2 シリアル 2365ms.
+LRUキャッシュ2 パラレル 2382ms.
+barakbさんのライブラリ シリアル 2351ms.
+barakbさんのライブラリ パラレル 389ms.
+```
+#### ３．８割重複。キャッシュあふれなし。
+→すごく早くなる。キャッシュの効果が大きい。
+→「barakbさんのライブラリもパラレル」があいかわらずすごい。
+```
+計算コスト:1000 要素数:1000 ユニーク数:200 重複率:0.8 容量:200 容量率:1.0
+キャッシュなし シリアル 3028ms.
+キャッシュなし パラレル 525ms.
+LRUなし シリアル 596ms.
+LRUなし パラレル 136ms.
+LRUキャッシュ1 シリアル 615ms.
+LRUキャッシュ1 パラレル 624ms.
+LRUキャッシュ2 シリアル 611ms.
+LRUキャッシュ2 パラレル 614ms.
+barakbさんのライブラリ シリアル 595ms.
+barakbさんのライブラリ パラレル 99ms.
+```
+#### ４．２割重複。キャッシュあふれあり。
+→LRUがあると当然、やや遅くなる。
+→**それでも「barakbさんのライブラリもパラレル」が速い。**
+```
+計算コスト:1000 要素数:1000 ユニーク数:800 重複率:0.2 容量:400 容量率:0.5
+キャッシュなし シリアル 2965ms.
+キャッシュなし パラレル 516ms.
+LRUなし シリアル 2381ms.
+LRUなし パラレル 413ms.
+LRUキャッシュ1 シリアル 2546ms.
+LRUキャッシュ1 パラレル 2577ms.
+LRUキャッシュ2 シリアル 2549ms.
+LRUキャッシュ2 パラレル 2521ms.
+barakbさんのライブラリ シリアル 2525ms.
+barakbさんのライブラリ パラレル 456ms.
+```

誤記修正

2017/10/11 11:31

投稿

mosa

スコア218

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -114,7 +114,7 @@
   })
-  override operator fun get(key: K): V = map.computeIfAbsent(key, initializer)
+  operator fun get(key: K): V = map.computeIfAbsent(key, initializer)
   override fun toString() = map.toString()

コメントでのご指摘を受けての修正

2017/10/10 05:04

投稿

mosa

スコア218

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -104,17 +104,19 @@
 ```Kotlin
+import java.util.*
 class LruCache<K, V>(val capacity: Int, private val initializer: (K) -> V) {
-    private val map = Collections.synchronizedMap(object : LinkedHashMap<K, V>(capacity, 1.0F, true) {
+  private val map = java.util.Collections.synchronizedMap(object : LinkedHashMap<K, V>(capacity, 1.0F, true) {
-        override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>?) = size > capacity
+    override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>?) = size > capacity
-    })
+  })
-    operator fun get(key: K): V = map.getOrPut(key) { initializer(key) }
+  override operator fun get(key: K): V = map.computeIfAbsent(key, initializer)
-    override fun toString() = map.toString()
+  override fun toString() = map.toString()
 }

ご指摘を受けての修正

2017/10/10 05:03

投稿

mosa

スコア218

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -52,7 +52,7 @@
-### ソースコード
+### ソースコード　→バグあり
@@ -98,6 +98,30 @@
+### ご指摘を受けての修正版ソースコード
+```Kotlin
+class LruCache<K, V>(val capacity: Int, private val initializer: (K) -> V) {
+    private val map = Collections.synchronizedMap(object : LinkedHashMap<K, V>(capacity, 1.0F, true) {
+        override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>?) = size > capacity
+    })
+    operator fun get(key: K): V = map.getOrPut(key) { initializer(key) }
+    override fun toString() = map.toString()
+}
+```

速度などを追記

2017/10/10 00:30

投稿

mosa

スコア218

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -133,3 +133,99 @@
 {2=4, 3=6, 4=8}
 ```
+---
+### ここから追記
+##### **■キャッシュなしの実装** の速度
+```Kotlin
+// キャッシュなし
+val cache = object {
+    operator fun get(key: Int) = Math.sin(key.toDouble()) * Math.cos(key.toDouble()) * Math.tan(key.toDouble())
+}
+// マルチスレッドでアクセス
+val executorService = Executors.newFixedThreadPool(8)
+val start = System.currentTimeMillis()
+(1..10000000).forEach { cache[it / 3] }
+executorService.shutdown()
+println((System.currentTimeMillis() - start).toString() + "ms")
+```
+→10回処理した結果 **平均:7286.2ms** ```7452ms, 7126ms, 7296ms, 7287ms, 7276ms, 7281ms, 7298ms, 7277ms, 7295ms, 7274ms```
+##### **■質問者の実装** の速度
+```Kotlin
+val cache = LruCache<Int, Double>(10000) { Math.sin(it.toDouble()) * Math.cos(it.toDouble()) * Math.tan(it.toDouble()) }
+// あとは一緒
+```
+→10回処理した結果 **平均:2772.7ms** ```3239ms, 3069ms, 2702ms, 2666ms, 2677ms, 2667ms, 2675ms, 2677ms, 2690ms, 2665ms```
+##### **■barakbさんのライブラリ** の速度
+```Kotlin
+val cache = Cache<Int, Double>({ Math.sin(it.toDouble()) * Math.cos(it.toDouble()) * Math.tan(it.toDouble()) }, 10000)
+// あとは一緒
+```
+→10回処理した結果 **平均:3049.1ms** ```3513ms, 3292ms, 3089ms, 2933ms, 2932ms, 2949ms, 2948ms, 2934ms, 2949ms, 2952ms```