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

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

ただいまの
回答率

90.50%

  • Java

    14049questions

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

  • Kotlin

    359questions

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

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

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 3
  • VIEW 1,005

mosa

score 200

いつもありがとうございます。
Kotlin、もしくはJavaで以下の要件を満たすプログラムを考えています。

 ■要件

1.与えられたキーに対して処理を行い結果を返す。
2.一度処理した結果は記憶し、同じキーに対してキャッシュが削除されるまで再度同じ計算はしない。
3.処理の関数はコンストラクタで指定する。
4.容量はコンストラクタで固定値を指定し、容量を超えたらLRUで削除する。
5.キーと処理結果の型はそれぞれ任意。
6.スレッドセーフである。
7.可能な限り高速に。

要はスレッドセーフで高速で汎用的な LRU Memoize です。

 ■質問

・上記の要件を「全て」満たすJava・Kotlinライブラリなどはありますか?(できればAndroidではないやつで)
・下記のソースコードを考えたのですが、正しくない点・懸念される点・もっと良い実装などはありますか?
※Map interfaceをimplementsしていなくてもよいです(してもよいです)。というかMap関係ないです。
※要件順は関係なくすべて重要です。
※「もっと良い実装」はJavaでもよいです。

 ■ソースコード (ご指摘により一部修正)

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()
}

 ■使用例

// 容量が3で2倍の値を返し、計算結果をmemoizeするキャッシュ
val cache = LruCache<Int, Int>(capacity=3) { it * 2 }
println("${cache[1]},${cache[2]},${cache[3]},${cache[4]}")
println(cache.toString())

 ■実行結果

2,4,6,8
{2=4, 3=6, 4=8}

 ========追記========


 ■速度計測

キャッシュクラスを5種類用意。(今回はJavaで)

  • キャッシュなし
  • LRUで削除しないキャッシュ
  • Collections.syncronizedMap() で排他するLRUキャッシュ
  • StampedLock.writeLock() で排他するLRUキャッシュ
  • daisuke7さんに教えていただいたbarakbさんのライブラリ
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); }

// キャッシュなし
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に注意が必要)

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. ");
  }

}

 ■速度計測結果

 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. 
  • 気になる質問をクリップする

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

checkベストアンサー

+3

若干高速かも知れないコード(追記3)

前回まで指摘ばかりのコメントでしたが、高速化についてコメントしてみます。

import java.util.*

class LruCache3<K, V>(private val capacity: Int,
                      private val initializer: (K) -> V) {
    val map = object: LinkedHashMap<K, V>(capacity, 1.0F, true) {
        override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>?): Boolean {
            return size > capacity
        }
    }
    val lock = java.util.concurrent.locks.StampedLock()

    operator fun get(key: K): V {
        val stamp = lock.writeLock()
        try {
            return map.getOrPut(key) { initializer(key) }
        } finally {
            lock.unlockWrite(stamp);
        }
    }

    // toStringも上記と同様にwriteLockの中で実行。記載は省略します
}


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

対象クラス シリアル/パラレル 標本平均(ms) 標本標準偏差(ms)
オリジナル シリアル 63 16
オリジナル パラレル 166 17
StampedLock版 シリアル 62 11
StampedLock版 パラレル 82 16

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

元のコメント

解答ではありませんが。

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

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

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

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


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

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

リスト2

// kotlin
import java.util.stream.IntStream

...

fun runParallel(cache: LruCache<Int, Int>): Unit {
    IntStream.range(0, 10000000).parallel().forEach {
        cache[it / 3]
    }
}

===>

Exception in thread "main" kotlin.KotlinNullPointerException
    at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
        ...
    at test.SyncMapKt.main(SyncMap.kt:43)
Caused by: kotlin.KotlinNullPointerException
    at test.LruCache.get(SyncMap.kt:24)
        ...

追記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/10 09:31

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

    キャンセル

  • 2017/10/10 12:07 編集

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

    キャンセル

  • 2017/10/10 14:03

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

    キャンセル

  • 2017/10/10 16:01

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

    キャンセル

  • 2017/10/10 16:15

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

    キャンセル

  • 2017/10/10 16:57 編集

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

    キャンセル

  • 2017/10/10 17:10

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

    キャンセル

  • 2017/10/11 20:35

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

    キャンセル

  • 2017/10/13 10:47 編集

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

    キャンセル

  • 2017/10/13 12:18

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

    キャンセル

+2

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/09/28 17:23

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

    キャンセル

  • 2017/09/28 17:29

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

    キャンセル

  • 2017/09/28 17:39

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

    キャンセル

  • 2017/10/12 09:37 編集

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

    キャンセル

  • 2017/10/13 22:03

    このbarakbさんのソース、ポイントになりそうな一部だけ拾い読みしました。

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

    キャンセル

  • 2017/10/13 22:32

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

    キャンセル

+2

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

訂正

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/10/13 13:15 編集

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

    キャンセル

  • 2017/10/13 13:45

    おー、、、KSwordOfHasteさんの回答に全部書かれてましたね。。。重複失礼しました。
    Collections.synchronizedMapはConcurrentModificationException問題があるので、
    ConcurrentHashMapが強化されたJava8以降では使うことはないと思ってるのですが、computeIfAbsentだけで言えば特に問題ないんですかね。

    何よりKotlinでは単なるMutableMapなんですね。。。
    Javaの資産が使えるとはいえ、ここまでの違いがあると下調べしてからでないと使うの怖いですね。
    勉強になりました。

    そもそも「最も古い値を削除」はLRUではないと思うので、removeEldestEntryにこだわる理由もないと思います。
    最も古い値だったとしても、その値の参照頻度が高ければ、消すべきではないというのがLRUの考え方だと思っています。

    キャンセル

  • 2017/10/13 14:37

    自分は同期コレクションを利用するよりはアプリケーションレベルでの排他(synchronizedブロックの利用)を好むため、はずかしながらAtomicXxx系クラスやjava.util.concurrentクラスに非常に疎いです。今回の質問でconcurrentHashMapの方がsynchronizedMapと比べどういいかを勉強させてもらっているといったところです。前者の方が性能よさそうぐらいの認識でしたが、ConcurrentModificationException問題も勉強しといたほうがよさそうですね。コメントありがとうございます。

    > 下調べしてからでないと使うの怖い
    同意です。putOrGetって何だっけ?というところから始まって、それがKotlinのextension functionらしいのを知り、同期してないのでは?・・・と気づくまで自分は結構時間かかりました。実際にKotlinを使う機会がもしできたら、もっとつっこんで勉強しないと危ないと感じました。

    > 「最も古い値を削除」
    だと、古さが登録を指すのか参照を指すのか曖昧なので「最も古く参照された値を削除」というべきでしたね。LinkedHashMapは登録済みキーの参照であっても、参照される度に参照順チェーンの先頭へエントリーを移動するので、実際上LRUの定義を最も素直に実装したものと思います。

    キャンセル

  • 2017/10/13 14:46 編集

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

    キャンセル

  • 2017/10/13 15:17

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

    キャンセル

  • 2017/10/13 15:50

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

    キャンセル

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

  • ただいまの回答率 90.50%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 受付中

    JAVAに関する質問

    JAVAに関する質問です。 JAVAで以下のプログラムを作成しました。 import java.util.Scanner;  public class Sample {  /

  • 解決済

    JButtonでボタンを制作し、画面の大きさを切り替えると位置が変わってしまう

    前回の質問時にはコマンドラインでの電卓を作っていましたが、現在ではswingを使った電卓の制作に挑戦しています。 JButtonでボタンを作り、親パネルに貼り付けているのですが、

  • 解決済

    javaで効率のよい書き方

    いつもお世話になっております。 今回は効率化(?)について質問させていただきます。 やりたいこと String型の配列に入っている”2016/07/20”という文字列

  • 解決済

    2つの配列の同インデックス要素を演算する for ループの Stream への書き直し方

    前提・実現したいこと 最近 Java を学び始め、Java8 では多くのループ構造を Stream API で実装可能であり、またこれからは可能な限りそうするべきとも伺いました。

  • 解決済

    呼び出すメソッドで戻り値を変えたい

    CalendarClassを使って、1年分の日付を取得するPGを作ってます。 メソッドに返す戻り値を変える良い方法はありませんか。 例えば、mainClassでthisMo

  • 解決済

    Javaでマス当てゲームを作りたい

    前提・実現したいこと Javaで5*5のマス目から当たりを見つけるプログラムを作りたいと考えています。 インターネットで下記のプログラムを見つけ応用できないかと思っています。

  • 解決済

    double型の範囲について

    前提・実現したいこと 毎度お世話になっております。グラフで曲線を描きたいと思っております。 結果を格納する変数にdouble型を用いているのですが、途中から値がおかしくなります

  • 解決済

    while文でmapのkyeと値を表示

    現在java se 8を勉強しております。 while文を用いて、keyと値をコンソールに表示したいのですが、うまくいかず どなたかご教授いただければと存じます ※for 文の書き

同じタグがついた質問を見る

  • Java

    14049questions

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

  • Kotlin

    359questions

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