質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.51%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Kotlin

Kotlinは、ジェットブレインズ社のアンドリー・ブレスラフ、ドミトリー・ジェメロフが開発した、 静的型付けのオブジェクト指向プログラミング言語です。

Q&A

解決済

3回答

1453閲覧

スレッドセーフで高速なLRUキャッシュ

mosa

総合スコア218

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Kotlin

Kotlinは、ジェットブレインズ社のアンドリー・ブレスラフ、ドミトリー・ジェメロフが開発した、 静的型付けのオブジェクト指向プログラミング言語です。

0グッド

3クリップ

投稿2017/09/28 06:38

編集2017/10/12 00:33

いつもありがとうございます。
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.

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答3

0

ベストアンサー

###若干高速かも知れないコード(追記3)
前回まで指摘ばかりのコメントでしたが、高速化についてコメントしてみます。

kotlin

1import java.util.* 2 3class LruCache3<K, V>(private val capacity: Int, 4 private val initializer: (K) -> V) { 5 val map = object: LinkedHashMap<K, V>(capacity, 1.0F, true) { 6 override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>?): Boolean { 7 return size > capacity 8 } 9 } 10 val lock = java.util.concurrent.locks.StampedLock() 11 12 operator fun get(key: K): V { 13 val stamp = lock.writeLock() 14 try { 15 return map.getOrPut(key) { initializer(key) } 16 } finally { 17 lock.unlockWrite(stamp); 18 } 19 } 20 21 // toStringも上記と同様にwriteLockの中で実行。記載は省略します 22}

上記は機能的に質問者さんの実装と同等ですが、同期にjavaのsynchronizedブロックではなく、StampedLock(compare and write命令を使うもの)で実装したものです。キャッシュサイズは少し増やして100、アクセスはほぼヒットとなるよう0~99の範囲とし、javaの並列ストリームパイプライン(以下)で実行し、20回の平均を見てみました。また比較のため単一スレッドでもやってみました。(なお自分のPCは2コアしかありません...)
IntStream.range(0, 1000000).parallel().forEach { cache[it / 15] }

対象クラスシリアル/パラレル標本平均(ms)標本標準偏差(ms)
オリジナルシリアル6316
オリジナルパラレル16617
StampedLock版シリアル6211
StampedLock版パラレル8216

単一スレッドの場合、競合がおきないため並列実行よりずっと高速に動作しますが、どちらの実装も差はでません。一方、並列処理ではsynchronizedブロックよりcompare & writeの方が早いという結果が伺えます。

###元のコメント
解答ではありませんが。

質問者さんのキャッシュクラスの実装に問題があると思います。

getOrPutの第二引数は、単に値を返すだけのものであり副作用を持たないものであるべきだと思います。元の実装では「キーの存在チェック」と「新たな値の追加」をしていますが、「キーの存在チェック」はgetOrPut側であらかじめ行われておりキーが存在しない場合のみこの関数を呼び出すため冗長です。また「新たな値の追加」もgetOrPut側がこの関数の戻り値を自動的に追加してくれることから冗長ですが、冗長である以上に「やってはいけない」ことではないかと思いました(※)。

ということでgetは単に次のようにすればよいと思います。

リスト1
operator fun get(key: K): V = map.getOrPut(key) { initializer(key) }


※:計算関数が副作用を持つ場合の問題

Kotlinに暗く質問者さんの性能測定コードが本当に並行動作しているのかどうか自分にははっきり分かりませんでした。そこでJavaのパラレルストリームを使って以下のように書き、元の実装とリスト1の両方を動かしたところ、元の実装の方で実行時例外が起きました。

リスト2

kotlin

1// kotlin 2import java.util.stream.IntStream 3 4... 5 6fun runParallel(cache: LruCache<Int, Int>): Unit { 7 IntStream.range(0, 10000000).parallel().forEach { 8 cache[it / 3] 9 } 10} 11 12===> 13 14Exception in thread "main" kotlin.KotlinNullPointerException 15 at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method) 16 ... 17 at test.SyncMapKt.main(SyncMap.kt:43) 18Caused by: kotlin.KotlinNullPointerException 19 at test.LruCache.get(SyncMap.kt:24) 20 ...

追記2:すみません、上記の指摘には足りない点があった気がします

Collections.synchronizedMapメソッドはjava.util.Collectionsのメソッドだと思います。そうだとするとkotlinはmapが単なるMutableMapであると解釈しアトミックでないgetOrPut拡張関数が用いられます。これがjava.util.concurrent.ConcurrentMapであればアトミック版のgetOrPutが用いられるのですが、ConcurrentMapにはCollections.synchronizedMapのようにコレクションをラップしてくれるような適当なクラスが用意されておらず、LinkedHashMapの特徴を生かすことができません。

ということで、getOrPutをjava.util.concurrent.locks.ReentrantLockなどにより自前で同期するか、あるいはgetOrPutではなくjava側で同期が保証されるcomputeIfAbsentを使うなどの対処が必要と思います。後者の方が以下のようにシンプルに書けます。

operator fun get(key: K): V = map.computeIfAbsent(key, initializer)

自分がKotlinに暗いのとimport文が質問文に明記されていなかったため、本指摘があたりかどうか確信がもてませんが、一応コメントいたします。

投稿2017/10/08 03:50

編集2017/10/10 07:59
KSwordOfHaste

総合スコア18392

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

mosa

2017/10/10 00:31

ありがとうございます。質問に一部追記しました。 おっしゃる通りですね。ボケてました。 なんで重複することやったんだろう。。。
KSwordOfHaste

2017/10/10 03:09 編集

もう一点気づいたことがあったので追記いたしました。指摘ばっかりでスミマセンが。
mosa

2017/10/10 05:03

コメントありがとうございます。コードに対する指摘もしてほしかったので助かります。 import の記述がなくてすみません。java.util.Collections であっています。 またもおっしゃる通りですね。質問内容を一部修正しました。
KSwordOfHaste

2017/10/10 07:01

何度にもわけてのコメントで恐縮ですが、高速化についてもコメントしました。 回答にあるコードはイマイチで、 val lock = java.util.concurrent.locks.ReentrantLock() override operator fun get(key: K): V { lock.withLock { return map.getOrPut(key) { initializer(key) } } } の方が良かったです。性能はこちらでも大差ないようでした。
mosa

2017/10/10 07:15

ありがとうございます。 StampedLock や ReentrantLock を知らなかったもので、今一生懸命勉強しているところです。 すみませんが2点ほど教えてください。 1.LruCache3 は Cache を継承していますが、こちらは何のクラスでしょうか。 2.私のコードも、追記3のLruCache3のコードもLinkedHashMapの継承ではなく委譲です。override operator fun get(key: K): V の override は不要、でよいですよね。(本題と関係ないですが。。。) 勉強しながらの質問で恐縮です。
KSwordOfHaste

2017/10/10 07:59 編集

失礼しました。1は自分が性能測定用のコードの都合で定義したgetのみ定義したインターフェースです。2はおっしゃる通りです。回答の方からCacheとoverrideを削除しておきました。
mosa

2017/10/10 08:10

ありがとうございます。 ちょっと自分なりに解釈・検証・勉強するのにお時間いただければと思います。
mosa

2017/10/11 11:35

とっても長くなってしまいましたが、ご指摘内容、教えていただいた内容などを含めて私のほうで速度計測の検証をしてみました。対象処理のコストにもよるかもしれませんが、StampedLockはあまり差がでなかったようですが、何か間違っていそうでしょうか。 というかすごく長くてすみません。お時間のある時にでも。。。
KSwordOfHaste

2017/10/13 02:28 編集

解答が既に長すぎるのでコメントで・・・loadFactorを1にするのはrehashを避けるためだと思いますが、よく考えるとキャッシュサイズ上限とcapacityを同じ値にするのはちょっとだけ不利だと思います。キャッシュ上限が16で16エントリーに達した直後に新たな値をputしようとするとcapacityが増えてしまう(A)気がします。また容量限度に近づくにつれキーの衝突確率が大きくなり若干不利です。キャッシュへ保持するデータ数上限より多少余裕をもったcapacityとしておくべきではないかと。(1.5倍とか)
mosa

2017/10/13 03:18

あー、そのとおりですね。 おっしゃるとおり、rehashを避けるため、と考えていました。 すこし安易でした。
guest

0

あんまり本質的な回答ではないですが、LinkedHashMapcomputeIfAbsent
アトミックではないため、スレッドセーフではないのではないでしょうか?
キャッシュにMapを使うのであれば、ConcurrentHashMapを使うべきだと思います。
スレッドセーフでないLinkedHashMapに比べればパフォーマンスは落ちるかもしれませんが、
ConcurrentHashMapの同期アルゴリズムは高速なので、自前で書くよりは確実で安全だと思います。

###訂正
LinkedHashMap自体はスレッドセーフではありませんが、
今回はCollections.synchronizedMapでラップをしているので、スレッドセーフになります。

投稿2017/10/13 03:42

編集2017/10/13 06:42
root_jp

総合スコア4666

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

KSwordOfHaste

2017/10/13 04:19 編集

Collections.synchronizedMapでwrapしてやるとcomputeIfAbsentはjava側の実装でアトミックになると思います。ただし、Collections.synchronizedMapの結果はKotlinが同期化されていない「単なるMutableMap」としてしか扱ってくれずputOrGetなどのextension functionが非アトミック版になるため、危険な手法と言えます。ですので、ご指摘のとおり一般のMapとしてならConcurrentHashMapが望ましいと思います。ただ「最も古い値を削除」という機能がConcurrentHashMapには抜けているので、危険な方法をやむなく採用している・・・というのが自分の解釈です。
root_jp

2017/10/13 04:45

おー、、、KSwordOfHasteさんの回答に全部書かれてましたね。。。重複失礼しました。 Collections.synchronizedMapはConcurrentModificationException問題があるので、 ConcurrentHashMapが強化されたJava8以降では使うことはないと思ってるのですが、computeIfAbsentだけで言えば特に問題ないんですかね。 何よりKotlinでは単なるMutableMapなんですね。。。 Javaの資産が使えるとはいえ、ここまでの違いがあると下調べしてからでないと使うの怖いですね。 勉強になりました。 そもそも「最も古い値を削除」はLRUではないと思うので、removeEldestEntryにこだわる理由もないと思います。 最も古い値だったとしても、その値の参照頻度が高ければ、消すべきではないというのがLRUの考え方だと思っています。
KSwordOfHaste

2017/10/13 05:37

自分は同期コレクションを利用するよりはアプリケーションレベルでの排他(synchronizedブロックの利用)を好むため、はずかしながらAtomicXxx系クラスやjava.util.concurrentクラスに非常に疎いです。今回の質問でconcurrentHashMapの方がsynchronizedMapと比べどういいかを勉強させてもらっているといったところです。前者の方が性能よさそうぐらいの認識でしたが、ConcurrentModificationException問題も勉強しといたほうがよさそうですね。コメントありがとうございます。 > 下調べしてからでないと使うの怖い 同意です。putOrGetって何だっけ?というところから始まって、それがKotlinのextension functionらしいのを知り、同期してないのでは?・・・と気づくまで自分は結構時間かかりました。実際にKotlinを使う機会がもしできたら、もっとつっこんで勉強しないと危ないと感じました。 > 「最も古い値を削除」 だと、古さが登録を指すのか参照を指すのか曖昧なので「最も古く参照された値を削除」というべきでしたね。LinkedHashMapは登録済みキーの参照であっても、参照される度に参照順チェーンの先頭へエントリーを移動するので、実際上LRUの定義を最も素直に実装したものと思います。
KSwordOfHaste

2017/10/13 09:18 編集

あ、回答の「スレッドセーフでない」は訂正していただいたほうがベターと思います。 --- 訂正済みなのに間抜けなコメントをしてしまいました。大変失礼いたしました。
mosa

2017/10/13 06:17

ご回答・ご指摘ありがとうございます。 色々とわかりずらい質問ですみません。 今回に関しては性能の向上を目的にしているだけですので、「参照頻度が最も低いものを削除」でも「最も参照が古いものを削除」でもかまいません。 「スレッドセーフで高速で汎用的な LRU? Memoizeを実現する」というのが要件ですので、synchronizedMapにも、removeEldestEntryにも、Mapインタフェースにも特にこだわってはいません。 「一部重複する高コストの計算を非同期で処理し、Memoizeすることで性能の向上を図りたいがメモリに限りがある。JavaでもKotlinでもよいのでいい方法はないか」と言ったほうがよかったのかもしれません。(計算コストとキャッシュヒット率やソートに依存するため一概に言えない、と言われてしまえばその通りなのですが) ConcurrentHashMapではなく、Collections.synchronizedMapを使っている理由は、KSwordOfHasteさんの仰る通りです。 私もConcurrentHashMapでさらっといけるのかな、と思っていたら意外と手段がない、と思い質問させていただきました。 と、思っていたら、「daisuke7さんに教えていただいたbarakbさんのライブラリ」が要件を満たした上で驚くほど高速だったので、今一生懸命見ていますが、私の知識ではなかなか・・・。
root_jp

2017/10/13 06:50

> 参照される度に参照順チェーンの先頭へエントリーを移動する すごい。知らなかった。まさにLRUになっているのですね。 確認するとJavaDocにモロに書いてました。。。 中途半端な知識でお恥ずかしい限りです。
guest

0

Javaだとこんなのは見つけました。
Cache -- An LRU Java Cache

投稿2017/09/28 06:58

daisuke7

総合スコア1563

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

mosa

2017/09/28 08:23

ありがとうございます。 さっそく試してみました。要件はすべて満たしているようです。 速度は私の実装のほうが10%程度速いようです。 追記に記載しました。
daisuke7

2017/09/28 08:29

そうでしたか。 シンプルかつ速いっていいですね!
mosa

2017/09/28 08:39

Kotlin、LinkedHashMap.removeEldestEntry、Collections.synchronizedMapの3つのおかげでという感じなのですが、何かもっといい方法があるようなないようなという感じです。 ご紹介ありがとうございます。私はなんだか色々探すのが不得意なようでteratailの皆様に頼りっぱなしです。
mosa

2017/10/12 00:43 編集

今更で恐縮ですが、私の速度計測方法が誤っていたようです。すみません。 また計測方法が誤っている部分があるかもしれませんが、教えていただいたライブラリはかなり高速なようです。 計測結果と実施内容を質問の追記に記載しました。 教えていただいたライブラリの実装内容を今、見ています。 ありがとうございます。
KSwordOfHaste

2017/10/13 13:03

このbarakbさんのソース、ポイントになりそうな一部だけ拾い読みしました。 このクラスは、内部で質問者さんと同様のLinkedHashMapを用いてますが、そのmapへ登録する値を「キーから値を計算するのに用いるFuture」にしているところがミソのようです。この工夫により、キーがmapにない場合はキーとFuture(値の計算がまだのもの)をmapへ登録し、その時点でさっさと排他を解除しています。その後おもむろに値を計算しにいきますが、他のスレッドのCacheへのアクセスを邪魔しないためトータルとして高速に動作します。この実装のため、シリアル実行したり値の計算コストが非常に低いケースではbarakbさんクラスが遅くなり、典型的なキャッシュのユースケース(値の計算に時間がかかる)でキャッシュへの同時アクセス頻度を上げてやると素朴な実装に比べて抜群に早くなるということみたいです。なんか・・・勉強になりました。
mosa

2017/10/13 13:32

まさに「未来」での計算完了を「約束」して次に移る、って感じですね。 すごいこと考える人がいるもんですね・・・。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.51%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問