Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー
圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更
クラスカルのアルゴリズム - naoyaのはてなダイアリー
昨年からはじめたアルゴリズムイントロダクションの輪講も終盤に差し掛かり、残すところ数章となりました。今週は第23章の最小全域木でした。辺に重みのあるグラフで全域木を張るとき、その全域木を構成する辺の合計コストが最小の組み合わせが最小全域木です。 アルゴリズムイントロダクションでは、クラスカルのアルゴリズム、プリムのアルゴリズムの二点が紹介されています。いずれも20世紀半ばに発見された古典的なアルゴリズムです。 二つのうち前者、クラスカルのアルゴリズムは、コスト最小の辺から順番にみていって、その辺を選んだことで閉路が構成されなければ、それは安全な辺であるとみなし、最小全域木を構成する辺のひとつとして選択します。これを繰り返しているうちに最小全域木が構成されるというアルゴリズムです。 今日はクラスカルのアルゴリズムを Python で実装してみました。扱うグラフは書籍の例を使ってみました。以下
オブジェクト指向っぽい話が分かるかもしれないJavaScript講座 その2 | Takazudo Clipping*
自分なんぞがオブジェクト指向とはなんぞと語るなんておこがましく、「オブジェクトっぽい話」でいいかなーと思っていたのですが、ブックマークするときに「オブジェクト」でタグ付けてる人がいたので、これはいかんと思い、こっそりタイトルを直しました。 2回目の今回は、複数のインスタンスをまとめて操作する方法について書きます。 まんじゅうマネージャー 前回、クラス作ってインスタンスを作ると便利だというところで終わりましたが、便利な点としてはまず、「複数のインスタンスをまとめて操作したり、作ったりできることができる」という点があります。どういうことかというと、とりあえず、以下のサンプルを見てみてください。 まんじゅうマネージャーサンプル まんじゅうを一気に作ったり、隠したりすることができます。 これで賞味期限が切れたりしても大丈夫なはずです。 この機能を作れと言われたら、前回の知識だけは結構厳しいのではな
Webacula Home Page
Features The basic features of the program : Bacula and Webacula ACLs (Access Control Lists) implemented. ACLs stored in Bacula database in Webacula tables Full supported MySQL, PostgreSQL and Sqlite databases Run Job Restore all files or selected files from Job by JobId Restore the most recent backup for a client Restore backup for a client before a specified time Show Timeline for Jobs Mount, um
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
comparisons [Bacula DokuWiki]![comparisons [Bacula DokuWiki]](https://cdn-ak-scissors.b.st-hatena.com/image/square/1aff17a016269d55a7257c3201e9c3bb6d16e17d/height=288;version=1;width=512/http%3A%2F%2Fgitlab.bacula.org%2Fassets%2Ftwitter_card-570ddb06edf56a2312253c5872489847a0f385112ddbcd71ccfa1570febab5d2.jpg)