Algorithms with Python / スプレー木
はじめに 今回は splay tree (スプレー木、スプレイ木) という二分木を紹介します。今まで説明した AVL 木 や 赤黒木 は二分木をベースにした平衡木で、木のバランスをチェックするための情報を節 (node) に付加し、バランスが崩れたら一定の範囲に収まるように木を修正します。これに対し、1985 年に Sleater 氏と Tarjan 氏が提案したスプレー木はちょっと変わっています。 スプレー木は二分木と同じ構造なので、通常の操作 (探索、挿入、削除など) は二分木と同様に行うことができます。スプレー木の特徴は、このあとに行う操作にあります。スプレー木はアクセスした節を木の根 (ルート) に移動します。この方法を Move to Root といいます。 たとえば線形探索の場合、後ろにあるデータほど探索に時間がかかります。そこで、探索のたびに見つけたデータを少し前に移動します
Lossy Countingを実装してみた - 省メモリな頻度計測 - 唯物是真 @Scaled_Wurm
大規模データで頻度を数えると、欲しいのはよく登場するアイテムの情報なのに、ほとんど出現しないアイテムの種類数が非常に多くて、それらがメモリを大量に必要としてしまうという問題がある これに対してアイテムの種類数の最大値に制限を加えたり、頻度に誤差を許すなどの条件のもとで、省メモリに頻度計測を行う方法がいくつも提案されている これらについては以下の記事が詳しい 大規模データで単語の数を数える - ny23の日記 今回はそういった手法の一つであるLossy Countingを実装した 日本語では上記の記事と以下の記事が詳しい [を] 誤り許容カウント法(lossy count method)のサンプルプログラム [O] イプシロン劣シノプス性を保持した頻度カウント lossy countingアルゴリズム - 機械学習の「朱鷺の杜Wiki」 元論文はこちら。年を見ると結構前なので、現在ではもっと
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
