超巨大なデータの中から指定要素を定数時間で削除する
巨大なデータってありますよね、それこそ扱うのに困るような奴が。
IDictionary< TKey, TValue > を経由してそいつにアクセスしているとして、 IDictionary< TKey, TValue >.Remove(TKey key)の呼び出しには非常に高いコストが付きまとう事を前提とした場合に、こいつを瞬間、定数時間で削除するって話。
解
public class RemovedState< TKey, TValue > : IDictionary< TKey, TValue >
{
IDictionary<TKey,TValue> _original;
TKey _removedKey;
public RemovedState( IDictionary<TKey,TValue> original, TKey removedKey )
{
_original = original;
_removedKey = removedKey;
}
// IDictionary の実装
bool ContainsKey( TKey key )
{
if( _removedKey==key ) return false;
return _original.ContainsKey( key );
}
…続く
ContainsKey の実装で解りますよね、何をやろうとしているかは。
要するに削除したって知ってるから「ねーよ」と言うクラスを間に挟む。それだけ
なんだよ！って思う人もいるかもだけど、このアプローチ、アトミック性とトランザクション性を合わせ持つ事に注意。
IDictionary<TKey,TValue> storage があるとして、
var tran = storage;
tran = new RemovedState( tran, key );
tran = new UpdatedState( tran, key2, value1 );
tran = new InsertedState( tran, key3, value2 );
storage = tran;
storage = tran がすなわちコミット、tran をstorageへ書き戻さずに捨ててしまえば無かった事になる（ロールバック）し、書き戻しの瞬間までは更新は他には見えないし、見える様になる瞬間においてすべての更新は整っているって言うアトミック性を持っているわけ。
var tran = storage の行の直後で var original = tran; しておき、 storage = tran の直前で original==storage のチェックをすると更新競合も検出できる（マルチスレッド前提ならもちろんの事だがロック、チェック、アップデートの順で実行してくれたまえ）
単純にこのまま行くと更新が溜まって行くにつれて次第にスタックが深くなるっていう面はあったりするが、複数の更新を保持して更新されたはずの状態で結果を返すクラスを作れればスタックの深さは制約できるよね。
んなわけで、簡単なトリックで巨大な readonly の元データをさも更新したかの様に見せられ、それをトランザクション性やアトミック性をもって実行できるのよってお話でした。
さて、Blogってウサも晴らしたしExcel データをコピペする仕事に戻るか。
投稿日時 : 2009年12月19日 16:48
Tweet
コメントを追加
# re: 超巨大なデータの中から指定要素を定数時間で削除する 2010年1月12日 15:05 a
これって２つ下のエントリで「嫌い」って言ってるChangeSetそのものですよね。# re: 超巨大なデータの中から指定要素を定数時間で削除する 2010年1月13日 9:20 菊池
２つ下のエントリの話しはChangeSetをオリジナルデータに反映するという「動作」が嫌いって話なんだけどな。ChangeSetはストレージから遠く離れた場所にありストレージとの整合性なんて全く保障されない
一方似たような事をやってもトランザクションログやアーカイブリドゥログはストレージにきわめて近い場所というかストレージに密接して保持されて周囲に変更の整合性を保証する
このエントリで書いた事をシステムの上位レイヤでやって最終的な反映時にエラーが出るかもねにすることもできるし、ストレージとかの下位レイヤでやってシステムの性能と整合性の基盤とする事もできるけど、前者は嫌いって事です。