You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
Ruby on Rails 7.2.1 Module ActiveRecord::Locking::Optimistic activerecord/lib/active_record/locking/optimistic.rb What is Optimistic Locking Optimistic locking allows multiple users to access the same record for edits, and assumes a minimum of conflicts with the data. It does this by checking whether another process has made changes to a record since it was opened, an ActiveRecord::StaleObjectErro
どうも更新をサボりまくりの有末です。 本日はゲームなどのフラグ管理に使えるビット演算について書きたいと思います。 進数 日本人の100人にアンケートを取れば、おそらく9の次は10と答える人が大多数だと思います。 ただしこれは厳密には間違っていて9の次が10になるのは10進数で物事を考えているからです。 進数というのは簡単に言うと「いつ桁があがるか?」という事です。 例えば普段使用している10進数であれば0から数えて10個目(9)までは1桁で表せますが 11個目(10)からは2桁になります。 なかなかイメージがし難いと思うので以下2進数、8進数、10進数、16進数を見て行きます。 桁がいつ増えるか?に注目してください。 2進数 8進数 10進数 16進数 0 0 0 0 1 1 1 1 10 2 2 2 11 3 3 3 100 4 4 4 101 5 5 5 110 6 6 6 111 7
base-64よりもスペース効率の良い方法。 GitHub レポジトリ 1 概要 バイナリをテキストに変換するエンコード方式としての base-64 は、そのデータ量を33%増大させます。この記事では、UTF-8のテキスト変換方式であり、元のデータから14%増大するbase-122を紹介します。base22はWebを念頭において作られました。 実装 には、Javascriptのデコーダを使い、base-122でエンコードしたリソースをWebページに読み込ませる過程が含まれます。 免責事項 3で示すように、base-122は 大半のWebページが該当します gzip圧縮ページでの使用は推奨しません。ですが、base-122は一般的な文字エンコード方式として役に立つ可能性があります。 1.1 はじめに 画像、フォント、オーディオなどの外部のバイナリリソースは、base-64でエンコードする デ
The State of Go Where we are in February 2017 Francesc Campoy Google Developer Advocate Time flies Go 1.6 is one year old (Happy Birthday!) Go 1.7 is already 6 months old! Go 1.8 was released on February 16th. 2 Notes The slides are available on /talks/2017/state-of-go.slide Most of the code examples won't run except locally and using Go 1.8. The playground still runs Go 1.7. 3 Agenda Changes sinc
釣りタイトルを付けたかったのですがさっぱり思いつかないのでもう諦めました。徳永です。 今回はCentroid Path Decomposition(以下CPD)についての話を書きます。直訳すると重心パス分解となるでしょうか。Trieを実現するためのテクニック(普通のツリーにも使えるのかな?なかなか難しそうですが…)の一つです。CPDは一年前の弊社岡野原の記事に出てきますが、私のような素人にはあれだけでは理解できない部分があったので、今回はちょっと論文を読んでみました。 Trieの実装によくある問題 Trieを実現するためのデータ構造というとダブル配列とかが挙げられますが、こういった高速なデータ構造にも、ランダムアクセスが多いという弱点があります。メモリはHDDなどと比べるとランダムアクセスに耐えうる記憶媒体ですが、とは言えランダムアクセスは避けられるに越したことはありません。CPDを使うこ
説明 Trie は文字列のための多分探索木である.各頂点はアルファベットで指定できる枝の集合を持つ.文字列ひとつが根からアルファベットで辺を手繰ることで行き着く頂点に対応する. アルファベットサイズを定数と見たとき,文字列の数に対して trie のサイズは O(m) である.ただし m は蓄えられている文字列の長さの総和.これは通常の二分木で蓄えるのに対して特に不利ではない.検索性能は検索文字列の長さ n に対して O(n) である.これはうまく実装された二分木が O(n + log m) であることと比較して高速である. 結論として,文字列に対して std::map を使いたい場合は trie で代用できないか考えるべきである. 計算量 検索: O(n),ただし n は検索する文字列長. 使い方 Trie *find(char *t, Trie *v); t に対応する Trie の頂点
なにやらDan Kogai氏の以下の記事が話題になっている様子。 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン? 連想配列(キーワードを投げると対応する値が返ってくるデータ構造)はハッシュテーブルで実装するのではなく、これからはトライ(trie)木を使うのがイケてる!(意訳)という内容だった。 連想配列にハッシュテーブルを使うのが良いか悪いかについては色々と意見があると思うので特にこの記事では触れない。 今回は連想配列として使えると話題のトライ木とはなんぞ、という入門的な記事にしようと思う。 トライ木が持つ機能 最初にトライが持つ以下の3つの機能について説明する。 - lookup - common-prefix-search - predictive-searchまずトライは連想配列として利用できる。つまりキーワードと値のペアを登
はじめましてこんにちわ。 4月からPFIで働いているまるまる(丸山)です。最近のマイブームはスダチです。 リサーチブログの更新が再開されたので、私も流れに乗って初ブログを書いてみようと思います。 今回は社内の情報検索輪講で少し話題にあがったCompressed Permuterm Indexを紹介したいと思います。 Paolo Ferragina and Rossano Venturini. “The compressed permuterm index”, ACM Transactions on Algorithms 7(1): 10 (2010). [pdf] これを実装したので以下のgoogle codeに晒してみることにします。 http://code.google.com/p/cpi00/ 修正BSDライセンスです。ソースコードは好きにしてもらって構いませんが、完成度はまだまだな
ブログの更新がとまっていましたが、また少しずつ更新してきたいと思います。 今回はtrie(トライ)の最近の話をしたいと思います。 trieはキー集合を扱うためのデータ構造の一種です。例えば、単語集合からなる辞書であったり、クロールしたURL情報を扱ったり、最近だと、KVS(Key Value Store)のようにキーを介してデータを保存、読み込みをしたりと様々な場面で利用されます。 同じようにキー集合を格納するデータ構造としてハッシュを利用する方法があります。キーからハッシュ値を計算し、その場所に文字列へのポインタを格納しておくデータ構造です。ハッシュを利用した場合とtrieを利用した場合の一番の大きな違いは、trieの場合だと、ある文字列から始まるキーを全て列挙する、いわゆる接頭辞探索ができることです。例えば”te”で始まる文字列を網羅的に調べることができます。木をたどって、”te”の下
package search; /** * 文字列に対するマッチ処理を行うためのインターフェイス。 */ public interface Matcher { boolean match(String target); } package search; import java.util.HashMap; import java.util.Map; /** * マッチ対象の文字列集合を前処理し、ツリー構造で保持する。 * NGワードチェックなど、マッチ対象の文字列集合がほぼ静的に決定されるケースで高速に動作する。 */ public class TreeMatcher implements Matcher{ private CharTreeNode rootNode = null; public TreeMatcher(String[] words){ this.rootNode = ne
このページでは Ceph や RBD を使う上で分かり辛い RADOS、CRUSH、Placement Group の概念を掘り下げて説明する。 以下は関連ページ。 Ceph の覚え書きのインデックス Ceph を使ってみる Rados Block Device(RBD) を使ってみる Ceph の CRUSH マップの書き方 更新履歴 (2012.02.10) 作成。 (2012.10.27) Mapping Algorithm を追加。 目次 1. RADOS RADOS を使ってみる RADOS のファイルはどこに格納されたのか? 2. Replication 3. CRUSH バケット(Bucket) Bucket の種類 OSD の過負荷(overload)と残空き容量 4. Placement Group Placement Group を確認する オブジェクトを Placem
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く