29
12月
id:Yoshioriさんの作ってるやつの別実装。id:taichitaichiさんのとも別の視点で作ってみました。ポイントは次のような感じです。
- 一定時間しか保持しない、というよりは一定時間経過したエントリを隠す。
- タイムアウトしたエントリの自動削除機構までは含まない(Mapの使われ方によって削除のタイミングはニーズが読めない)。ただし、明示的な削除方法は提供する。
- 見えなくなる時間がわりと正確。ScheduledExecutorServiceを使って、正確なタイミングで削除されることを信頼しない。
この実装では、毎回Mapの操作に対してその時点でのスナップショットを作成します。snapshotの作成はわりと高価な作業ですが、それよりも時間に対して正確であることを目標としています。経験的に、Mapに数万エントリも入っていることはふつうの用途としてはまれなので、そこは目をつぶります。スレッドセーフとなるように気をつけましたが、テストはしていません。あ、全体的にテストはしていません。
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicReference;
/**
* 指定時間以上経過したエントリを隠すマップ.
*
* @author takayuki
*/
public class TimeoutMap<K, V> implements Map<K, V>, Serializable {
private final long timeout;
private ConcurrentHashMap<K, ValueAndTime<V>> map
= new ConcurrentHashMap<K, ValueAndTime<V>>();
final class ValueAndTime<V> implements Serializable {
private V value;
private long time;
public ValueAndTime(V value, long time) {
this.value = value;
this.time = time;
}
public long getTime() {
return time;
}
public V getValue() {
return value;
}
}
final class EntrySetImpl<K, V> implements Map.Entry<K, V>, Serializable {
private K key;
private AtomicReference<V> value;
public EntrySetImpl(K key, V value) {
this.key = key;
this.value = new AtomicReference<V>(value);
}
public K getKey() {
return key;
}
public V getValue() {
return value.get();
}
public V setValue(V value) {
return this.value.getAndSet(value);
}
}
/**
* コンストラクタ.
* @param timeout タイムアウト(ミリ秒).
*/
public TimeoutMap(long timeout) {
this.timeout = timeout;
}
private ConcurrentHashMap<K, ValueAndTime<V>> snapshot() {
long t = System.currentTimeMillis() - timeout;
ConcurrentHashMap<K, ValueAndTime<V>> snapshot
= new ConcurrentHashMap<K, ValueAndTime<V>>(map);
for (K key : snapshot.keySet()) {
if (snapshot.get(key).getTime() > t) {
snapshot.remove(key);
}
}
return snapshot;
}
private Collection<V> snapshotOfValues() {
Collection<V> values = new ArrayList<V>();
Map<K, ValueAndTime<V>> snapshot = snapshot();
for (K key : snapshot.keySet()) {
values.add(snapshot.get(key).getValue());
}
return values;
}
/**
* タイムアウトしたキーのエントリを削除.
*/
public void gc() {
map = snapshot();
}
public int size() {
return snapshot().size();
}
public boolean isEmpty() {
return snapshot().isEmpty();
}
public boolean containsKey(Object key) {
return snapshot().containsKey(key);
}
public boolean containsValue(Object value) {
return snapshotOfValues().contains(value);
}
public V get(Object key) {
ValueAndTime<V> v = snapshot().get(key);
return v == null ? null : v.getValue();
}
public V put(K key, V value) {
ValueAndTime<V> prev = map.put(key,
new ValueAndTime(value, System.currentTimeMillis()));
return prev == null ? null : prev.getValue();
}
public V remove(Object key) {
return map.remove(key).getValue();
}
public void putAll(Map<? extends K, ? extends V> map) {
for (K key : map.keySet()) {
put(key, map.get(key));
}
}
public void clear() {
map.clear();
}
public Set<K> keySet() {
return snapshot().keySet();
}
public Collection<V> values() {
return snapshotOfValues();
}
public Set<Entry<K, V>> entrySet() {
Set<Entry<K, V>> entryset = new HashSet<Entry<K, V>>();
Map<K, ValueAndTime<V>> snapshot = snapshot();
for (K key : snapshot.keySet()) {
entryset.add(new EntrySetImpl(key, snapshot.get(key).getValue()));
}
return entryset;
}
}
追記: スレッドセーフにしたいなあと思って書いているといろいろ、ぼろが見つかりますね。gc()が実行されている間、put(Object key, V value)と、remove(Object key)の実行をブロックしないとエントリの欠落や削除漏れが出そうです。
ShuttleMenu.tiff
に載っている完全マッチングアルゴリズムからの考察です。今回の転職では数社のエージェント(民間職業紹介業者)に協力いただいています。そのエージェントの働き方と、安定マッチングアルゴリズムの挙動とは興味深い類似性があることに気づきました。安定マッチングアルゴリズムは上述のアルゴリズムデザインという本で最初に紹介されているアルゴリズムです。アルゴリズムに興味がある方は、重くて高価な本ですが、ぜひ読んでみてください。高いので図書館で借りて読むといいと思います(なければリクエストすると買っていただけることがあります)。
です。
