exponential backoffのメモ
exponential backoffとは? データ送信処理が失敗して再送信するときに、失敗回数が増えるに連れて再送信するまでの待ち時間を指数関数的に増やす仕組みを exponential backoff という。 有名な例としては Carrier sense multiple access with collision detection (CSMA/CD) や Carrier sense multiple access with collision avoidance(CSMA/CA) といった通信方式で、失敗回数 N に対して、[0, 2^N-1] からランダムな数を選び、その slot time 分だけ待って再送信するようになっている。 ランダムに選んでいるのは、複数の通信が同じタイミングで失敗した時に、また同じタイミングで再送されないようにするため。 また、失敗回数が一定値を超え
ruby-list jp - [ruby-list:43857] Hashへの生成順は保障されないのか？
こんにちは、笠松と申します。 vine linux 4.1でruby1.8.5(rpmパッケージ版)を使っています。 次のようなHashを生成したとします。 pair=Hash.new pair["apple"]="apple" pair["and"]="and" pair["bee"]="bee" pair["cat"]="cat" このhashを表示したら apple=>apple and=>and bee=>bee cat=>cat のように生成順を期待していたのですが、 pair.each do |key, val| print key, "=>", val, "\n" end で表示させると、 cat=>cat and=>and bee=>bee apple=>apple の順になってしまいました。できれば生成していった順で 表示されるとよいのですが、hashの中身はどのような基
Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found
2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳 つまり「終わったコンテナ」。 以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。 徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。 そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構
RE: sort を使うときは，LC_ALL=C を忘れずに - ny23の日記
Twitter ID も livedoor ID もないので直接コメントできないが，sort (GNU coreutils) の名誉のために，ここにメモしておく． 404 Blog Not Found:algorithm - bucketsort.[ch] - 汎用かつlibcの*sortより高速な まず第一印象として，この程度のサイズのファイルのソートで sort (GNU coreutils) がいまどきこんなに遅いはずはない．LC_ALL=C で追試すると，やはり bucketsort との差は無くなった．上の記事（に対するツイート）は Twitter 上でもそれなりにリツイートされているように見えるのだけど，この実行時間に違和感を感じる人が全くいないのはどういうことなのだろうか．sort を実際に使う人がほとんど見ていないのか，それとも計算量が違うから速くて当然という思い込みか．
memcachedのように使えるBloomFilter - walf443's blog
YAPCでmalaさんの話を聞いていて、memcachedのようにお手軽に使えるbloom filterがあるとひょっとすると便利かもしれない、とふと思ったのでAnyEventつかって、Bloom::Fasterのwrapperを書いてみました。 https://github.com/walf443/p5-bloomd-server 以下のようなプログラムを書いてサーバーを起動します use strict; use warnings; use EV; use AnyEvent; use Bloomd::Server my $cv = AnyEvent->condvar; my $server = Bloomd::Server->new( capacity => 100_000_000, backupdir => '.', ulog => 'ulog', ); $server->run $c
livedoor Techブログ : decision tree (決定木) でユーザエージェント判定器を作ってみる
アクセスログのユーザエージェント(UA)からブラウザを判別するのって，みんな何使ってますか？ 自分が作ったアクセス解析システムでは HTTP::BrowserDetect と HTTP::MobileAgent にそれぞれ独自パッチをあてたものを使っています。これらはルールベースの判定器なので，新しいブラウザや新種の bot が登場するたびに手作業でルールを追加し，パッチを作って配布するという作業が必要になります。 この更新作業が大変面倒くさくて対応が遅れがちになるので，「このUA文字列はこのブラウザですよ、という例を大量に与えたら、自分で勝手に判定ルールを学習してくれるようになったら便利なのになぁ」と思い，decision tree (決定木)を使ってみることを思い立ちました。 目標は， "Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1
はてなのCAPTCHAを破るプログラムは30分で書ける - やねうらおブログ(移転しました)
CAPTCHAとは、スパムコメントなどを防止するための認証画像のことである。 それにしても、はてなのCAPTCHAはひどい。無いよりマシという考え方もあるのでそれについてはあまり議論する気は無いのだが、それにしてもこれを破るプログラムは30分あれば十分書ける。 具体的には、はてなのCAPTCHAには8つの好ましくない特徴と、2つの脆弱性がある。 ■ 8つの好ましくない特徴 ・画像自体のサイズが小さすぎる。→ こんなに小さいと探索量(計算量)が小さくて済む。 ・フォントにゆがみがない → フォントはある程度変形させたほうが良い。変形させてあるとテンプレートマッチングがしにくくなる。 ・フォントが固定。→ フォントは毎回変えたほうが良い。 ・フォントを回転させていない → フォントは文字ごとにある程度ランダムに回転させた方が良い。 ・フォントサイズが一定 → フォントサイズは文字ごとにある程度
検索と挿入がともにO(1)であるようなHashを作るにはコツがいる
このところ立て続けに表記の事実を理解していない俺実装のHash(しかもCで!)を見かけたので、おそらく知られていないんだと思う。以降、同じ轍を踏む人が少なくなればと思い、啓蒙のために公開しておく。 先に言っておくがおまえらはHashを再発明するんじゃねよボケが。おとなしくありもののライブラリ使えよ。つうかHashのある言語使えよ。Cとかマゾかよ。 言葉と前提とりあえずHashが何であるかとか、どういう作りになっているかとか、そういうことは既知とする。リストの配列ってことね。←これで何言ってるか分からないおまえらにはこの文章はちょっとはやい。先にデータ構造の教科書を読むことをおすすめ。以下ではHashに登録されるキーとデータのペアのことをentryと呼び、リストの配列と言ったときのリストのほうをbin、配列のほうをbucketと呼ぶ。つまり、 class Hash { typedef lis
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
How TokuDB Fractal Tree Indexes Work
MySQLにおけるJOINのチューニングの定石