いつもありがとうございます。
Kotlin、もしくはJavaで以下の要件を満たすプログラムを考えています。
■要件
1.与えられたキーに対して処理を行い結果を返す。
2.一度処理した結果は記憶し、同じキーに対してキャッシュが削除されるまで再度同じ計算はしない。
3.処理の関数はコンストラクタで指定する。
4.容量はコンストラクタで固定値を指定し、容量を超えたらLRUで削除する。
5.キーと処理結果の型はそれぞれ任意。
6.スレッドセーフである。
7.可能な限り高速に。
要はスレッドセーフで高速で汎用的な LRU Memoize です。
■質問
・上記の要件を「全て」満たすJava・Kotlinライブラリなどはありますか?(できればAndroidではないやつで)
・下記のソースコードを考えたのですが、正しくない点・懸念される点・もっと良い実装などはありますか?
※Map interfaceをimplementsしていなくてもよいです(してもよいです)。というかMap関係ないです。
※要件順は関係なくすべて重要です。
※「もっと良い実装」はJavaでもよいです。
■ソースコード (ご指摘により一部修正)
Kotlin
1import java.util.* 2class LruCache<K, V>(val capacity: Int, private val initializer: (K) -> V) { 3 private val map = java.util.Collections.synchronizedMap(object : LinkedHashMap<K, V>(capacity, 1.0F, true) { 4 override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>?) = size > capacity 5 }) 6 operator fun get(key: K): V = map.computeIfAbsent(key, initializer) 7 override fun toString() = map.toString() 8}
■使用例
Kotlin
1// 容量が3で2倍の値を返し、計算結果をmemoizeするキャッシュ 2val cache = LruCache<Int, Int>(capacity=3) { it * 2 } 3println("${cache[1]},${cache[2]},${cache[3]},${cache[4]}") 4println(cache.toString())
■実行結果
2,4,6,8 {2=4, 3=6, 4=8}
========追記========
■速度計測
キャッシュクラスを5種類用意。(今回はJavaで)
- キャッシュなし
- LRUで削除しないキャッシュ
- Collections.syncronizedMap() で排他するLRUキャッシュ
- StampedLock.writeLock() で排他するLRUキャッシュ
- daisuke7さんに教えていただいたbarakbさんのライブラリ
Java
1import org.async.utils.cache.Cache; 2 3import java.util.Collections; 4import java.util.LinkedHashMap; 5import java.util.Map; 6import java.util.concurrent.locks.StampedLock; 7import java.util.function.Function; 8 9interface Calculator<K, V>{ V get(K key); } 10 11// キャッシュなし 12class NonCache<K, V> implements Calculator<K, V>{ 13 private Function<K, V> initializer; 14 NonCache(Function<K, V> initializer){ this.initializer = initializer; } 15 @Override public V get(K key){ return initializer.apply(key); } 16} 17 18// LRUしないキャッシュ 19class NonLruCache<K, V> implements Calculator<K, V>{ 20 private int capacity; 21 private Function<K, V> initializer; 22 private Map<K, V> map = new LinkedHashMap<>(capacity, 1.0f, true); 23 NonLruCache(int capacity, Function<K, V> initializer){ 24 this.capacity = capacity; 25 this.initializer = initializer; 26 } 27 @Override public V get(K key){ return map.computeIfAbsent(key, initializer); } 28} 29 30// Collections.syncronizedMap() で排他するLRUキャッシュ 31class LruCache1<K, V> implements Calculator<K, V>{ 32 private int capacity; 33 private Function<K, V> initializer; 34 private Map<K, V> map = Collections.synchronizedMap(new LinkedHashMap<K, V>(capacity, 1.0f, true){ 35 @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest){ return size() > capacity; } 36 }); 37 LruCache1(int capacity, Function<K, V> initializer){ 38 this.capacity = capacity; 39 this.initializer = initializer; 40 } 41 @Override public V get(K key){ return map.computeIfAbsent(key, initializer); } 42} 43 44// StampedLock.writeLock() で排他するLRUキャッシュ 45class LruCache2<K, V> implements Calculator<K, V>{ 46 private int capacity; 47 private StampedLock lock = new StampedLock(); 48 private Function<K, V> initializer; 49 private Map<K, V> map = new LinkedHashMap<K, V>(capacity, 1.0f, true){ 50 @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest){ return size() > capacity; } 51 }; 52 LruCache2(int capacity, Function<K, V> initializer){ 53 this.capacity = capacity; 54 this.initializer = initializer; 55 } 56 @Override public V get(K key){ 57 long stamp = lock.writeLock(); 58 try{ return map.computeIfAbsent(key, initializer); } finally{ lock.unlockWrite(stamp); } 59 } 60 61} 62 63// daisuke7さんに教えていただいたbarakbさんのライブラリ https://github.com/barakb/Cache 64class LruCache3<K, V> implements Calculator<K, V>{ 65 private Cache<K, V> cache; 66 LruCache3(int capacity, Function<K, V> initializer){ cache = new Cache<>(initializer::apply, capacity); } 67 @Override public V get(K key){ 68 try{ return cache.get(key); } catch(Throwable throwable){ throw new RuntimeException(throwable); } 69 } 70 71}
以下のプログラムで実行。(メモリやGCに注意が必要)
Java
1import java.util.Collections; 2import java.util.List; 3import java.util.function.Function; 4import java.util.stream.Collectors; 5import java.util.stream.IntStream; 6 7public class LruCacheTest{ 8 9 public static final int COST = 1000; // 計算コスト 10 public static final int SIZE = 1000; // 要素数 11 public static final double DUPLICATION_RATE = 0.0; // 重複率 12 public static final double CAPACITY_RATE = 1.0; // 容量率 13 public static final int CAPACITY = (int) (Math.round(SIZE * (1.0 - DUPLICATION_RATE) * CAPACITY_RATE)); // 容量 14 public static final List<Integer> LIST = IntStream.rangeClosed(0, SIZE - 1).boxed() 15 .map(it -> (int) ((double) it * (1.0 - DUPLICATION_RATE))).collect(Collectors.toList()); 16 public static final int UNIQUE = (int) LIST.stream().distinct().count(); // ユニーク数 17 18 public static void main(String... args){ 19 Function<Integer, Integer> calc = it -> it + IntStream.rangeClosed(1, COST * 10000).sum(); 20 Collections.shuffle(LIST); // リストをシャッフル 21 System.out.println("計算コスト:" + COST + " 要素数:" + SIZE + " ユニーク数:" + UNIQUE + " 重複率:" + DUPLICATION_RATE + " 容量:" + CAPACITY + " 容量率:" + CAPACITY_RATE); 22 seri("キャッシュなし", new NonCache<>(calc)); 23 para("キャッシュなし", new NonCache<>(calc)); 24 seri("LRUなし", new NonLruCache<>(CAPACITY, calc)); 25 para("LRUなし", new NonLruCache<>(CAPACITY, calc)); 26 seri("LRUキャッシュ1", new LruCache1(CAPACITY, calc)); 27 para("LRUキャッシュ1", new LruCache1(CAPACITY, calc)); 28 seri("LRUキャッシュ2", new LruCache2(CAPACITY, calc)); 29 para("LRUキャッシュ2", new LruCache2(CAPACITY, calc)); 30 seri("barakbさんのライブラリ", new LruCache3(CAPACITY, calc)); 31 para("barakbさんのライブラリ", new LruCache3(CAPACITY, calc)); 32 } 33 34 private static void seri(String name, Calculator<Integer, Integer> calculator){ 35 long start = System.currentTimeMillis(); 36 LIST.stream().mapToInt(calculator::get).sum(); 37 System.out.println(name + " シリアル " + (System.currentTimeMillis() - start) + "ms. "); 38 } 39 40 private static void para(String name, Calculator<Integer, Integer> calculator){ 41 long start = System.currentTimeMillis(); 42 LIST.parallelStream().mapToInt(calculator::get).sum(); 43 System.out.println(name + " パラレル " + (System.currentTimeMillis() - start) + "ms. "); 44 } 45 46}
■速度計測結果
1.重複なし。キャッシュあふれなし。
→「キャッシュなしのパラレル」が当然最速。「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.
2.2割重複。キャッシュあふれなし。
→当然、「キャッシュなし」以外すべて速くなる。
計算コスト: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.
3.8割重複。キャッシュあふれなし。
→すごく速くなる。キャッシュの効果が大きい。
→**「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.
4.2割重複。キャッシュあふれあり。
→LRUでの削除があると当然、やや遅くなる。
→それでも「barakbさんのライブラリもパラレル」が速い。 → 「LRUなしのパラレル」に迫る勢い。
計算コスト: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.
回答3件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2017/10/10 00:31
2017/10/10 03:09 編集
2017/10/10 05:03
2017/10/10 07:01
2017/10/10 07:15
2017/10/10 07:59 編集
2017/10/10 08:10
2017/10/11 11:35
2017/10/13 02:28 編集
2017/10/13 03:18