Hash-flooding DoS と SipHash - あどけない話
以前、僕が実装している web サーバ Mighty が、Haskell で書いているにも関わらず、セグメンテーションフォールトを起こしていた。調べたところ hashable ライブラリがリンクする C の DJBX33X が、SipHash に変わったことが原因だった。このときから SipHash が気になっていたし、以前社内で説明した "Efficient Denial of Service Attacks" との関係も知りたかったので、少し調べてみた。この記事は、その覚え書き。 Hash-flooding DoS の歴史 1998 年に Alexander Peslyak 氏が Phrack Magazine で、Hash-flooding DoS を受けたことを報告している。ハッシュは、N 個の要素を挿入するのに通常 O(N) かかるが、ハッシュ値がすべて衝突する最悪の場合では O
Gitの「もしかしてコレ?」の実装を読む | Webシステム開発／教育ソリューションのタイムインターメディア
疑問 Gitを使っていると時々コマンドを入力し損ねたまま実行してしまうことがあります。 この時、Gitは親切にも近い名前のコマンドを列挙してくれます: $ git clone git@github.com:git/git.git $ cd git $ git grep -n 'Did you mean' -- '*.c' help.c:385: Q_("\nDid you mean this?", help.c:386: "\nDid you mean one of these?", help.c:444: Q_("\nDid you mean this?", help.c:445: "\nDid you mean one of these?", sha1_name.c:1234: "Did you mean '%.*s:%s' aka '%.*s:./%s'?", sha1_name.c
[その２] RubyとPythonの違いからガベージコレクタを理解する - ワザノバ | wazanova.jp
http://patshaughnessy.net/2013/10/30/generational-gc-in-python-and-ruby 前回のエントリーはこちら。 ブタペストで開催されたRUPY2013でのPat Shaughnessyのプレゼンの後半です。RubyとPythonのガベージコレクタの違いを、今回は、Pythonの循環データ構造への対応とRuby 2.1の世代別ガベージコレクタの話題に触れながら、紹介しています。 1) Pythonの循環データ構造と参照カウント Pythonは、いくつのポインタがそのオブジェクトを参照しているかを、参照カウントと呼ばれる整数で管理している。変数もしくはオブジェクトが、そのオブジェクトを参照しはじめれば数字が増えて、プログラムがそのオブジェクトを使うのをやめれば数字が減る仕組み。 1960年代以来、コンピュータ科学者が気づいているアルゴ
RAID5のパリティ生成アルゴリズム - sanonosa システム管理コラム集
「RAIDという仕組みは本当に安全なのか？」という懸念が昔からあったので、今回RAID5のParity algorithmについて研究してみました。(RAID6のParity algorithmについて研究しましたが、それはまた今度) 【RAID5の特徴】 RAID5の特徴について改めて整理すると以下のようになるかと思います。 •Block単位でパリティ分散記録する。 •水平パリティを1つ用いる。水平パリティにはXOR方式を用いることが一般的。 •HDDが1本壊れても復旧できる。 【XOR(排他的論理和)について】 RAID5ではXORを用いてパリティを生成しますので、まずはXORについておさらいしておきます。
RubyとPythonの違いからガベージコレクタを理解する - ワザノバ | wazanova.jp
http://patshaughnessy.net/2013/10/24/visualizing-garbage-collection-in-ruby-and-python Pat Shaughnessyが、ブタペストで開催されたRUPY2013でのプレゼンの前半を自らのブログで紹介しています。 ガベージコレクタは、「ゴミを集める」という行為だけでなく、「新しいオブジェクトのためにメモリをあてがう。」「不要なオブジェクトを見つける」「不要なオブジェクトからメモリを取り戻す。」という、人間の心臓が血液を浄化するような働きをしている。 この簡単なコードサンプルを見ると、RubyとPythonの記述はよく似ているが、それぞれの言語の内部でのインプリの仕組みは違う。 1) Rubyのメモリ Rubyは、コードが実行される前に、数千のオブジェクトを先につくり、それをリンクされたfree listに置
SmartNewsを支える機械学習
ニュースアプリSmartNews(https://www.smartnews.be/)の背景のアルゴリズムについてTokyoWebMining30th(http://tokyowebmining30.eventbrite.com/)で話させていただいた際の資料です。 •SmartNews iphone版: https://itunes.apple.com/jp/app/id579581125 •SmartNews Android版 https://play.google.com/store/apps/details?id=jp.gocro.smartnews.android •SmartNews開発者ブログ http://developer.smartnews.be/blog/
第5回 協調フィルタリング | gihyo.jp
この jaccard相関係数は、ユーザAとユーザB、C、Dの類似度を表します。値が大きいほど類似しています。図4では、ユーザCがこの中では、一番類似していることをしめしています。 それでは購入していない商品2と4を推薦するかどうかはどう決定するのでしょうか。商品2のスコアはユーザAの平均評価値に各ユーザの類似度を考慮した重みつきの評価を加えることで計算します。簡易ではありますが今回は次のように実装してみました。 #! /usr/local/bin/python # -*- coding:utf-8 -*- import sys def jaccard(v1, v2): """ jacard係数を求める """ v1_and_v2 = 0. v1_or_v2 = 0. for i in xrange(len(v1)): if v1[i] == 1 or v2[i] == 1: v1_or_v
FluentdとRedisを使ったランキング機能の実装 | SmartNews開発者ブログ
ゴクロの大平です。ごくろうさまです。 Redisは高速で、かつデータの永続化や、複数のデータ型によるストア(list,set,sorted set等）も対応しており、機能的が豊富ということから愛用者の多いKVS実装の一つだと思います。 特に私のようなアプリケーションエンジニアの人間にとってはデータ型のバリエーションの豊富さが便利さを感じる部分で、たとえばlistを用いてタイムライン的な情報や履歴情報の管理、sorted setを用いてランキング情報の管理、などのようにアプリケーションの需要の多くにRedisが対応することができます。 これらの情報を登録する際のフローとしては自作のアプリケーションから直接、というケースが多いと思いますが、せっかくFluentdのような便利なlog collector実装があるので、FluentdとRedisを組み合わせる事でカジュアルに情報の蓄積を行いたい
PFI の推薦エンジンを使っておすすめアニメを探すサイトを作ってみた - アニメおすすめDB運営ブログ
はてなブックマークの関連エントリ機能でお馴染みの Preferred Infrastructure さんが、オープンソースで Jubatus というレコメンデーションエンジン（ひとりひとりの好みを学習して、その人にあったアイテムを提示するためのソフトウェア）を公開しています。（もっと詳しい話はこのへんを見るといいかもしれません。） このエンジンと Ruby On Rails を利用して、閲覧者の好みにあったおすすめアニメを推薦するサイトを作ってみました。 推薦に使うための評価データがまだ少ないため、推薦結果はもうひとつかもしれませんが、多くの人がおすすめ診断を試せば、データが蓄積されておすすめの精度が上がっていくので、興味のある方は是非試していただければと思います。 Jubatus とは もともとこのエンジンは、レコメンデーションを行うための計算を、多くのコンピュータで分散処理しつつ結果を
PostgreSQLの共有バッファ(shared_buffer)とMySQLのバッファプール(buffer_pool)のメカニズム比較 - interdb’s blog
PostgreSQLとMySQLのバッファについて。 PostgreSQLのバッファマネージャ 詳細はこちらをみて頂くとして、PostgreSQLのバッファマネージャは、２００５年リリースのバージョン8.1で大幅に変わった。 以下の表をみて頂くとわかるようにページ置換アルゴリズムは、8.0まではリストで実装したLRUとそのバリエーションであったが、8.1から配列で実装したClockSweep方式になった。 ページ置換アルゴリズムとロックの変遷 バージョン ページ置換アルゴリズム バッファマネージャのロック 方式 説明 PostgreSQL での呼称 説明 7.4まで [〜2004] LRU "Least Recently Used"の略称。最もオーソドックスなアルゴリズム。 BufMgrLock 排他ロックのみ。ページの入れ替えだけでなく、読み取りでも排他ロックをかける*1。 8.0.0〜
ビットを数える・探すアルゴリズム
作成日：2004.05.04 修正日：2012.09.01 このページは 2003年の9/11、9/28 の日記をまとめて作成。 はじめに PowerPC 系や Alpha などには population count と呼ばれるレジスタ中の立っているビット数を数える命令が実装されている。 集合演算を行うライブラリを実装したい場合などに重宝しそうな命令である。 職場でこの population count 命令について話をしているうちにビットカウント操作をハードウェアで実装するのは得なのか？という点が議論になった。 CPU の設計をできるだけシンプルにするためには、複雑で使用頻度の低い命令は極力減らした方がよい。 例えば SPARC は命令セット中にビットカウント演算があるが、CPU 内には実装しないという方針をとっている(population 命令を実行すると不正命令例外が発生し、それを
b-Bit MinHashによる高速かつ省スペースな類似度判定 | SmartNews開発者ブログ
ゴクロの浜本です。ネットカフェでコードを書くのが好きです。 前回のエントリーでも触れられていますが、SmartNewsはホットな話題をユーザにお届けするために、常時、膨大な数のツイートおよびURLをクロールしています。こうして収集した記事に対し、様々な分析が施されますが、その中でも重要な処理の1つに、記事の類似度判定があります。内容の似通った記事をインデックスから発見し、グループ化する処理です。 毎秒、大量の新着記事が到着することから、この類似度判定は高速に実行する必要があります。また、インデックスを全てメモリに載せているので、類似度判定を実現する際の空間効率も要求されます。 今回は、SmartNewsが高速かつ省スペースな類似度判定のために使用しているb-Bit MinHashと呼ばれる手法を紹介します。2年前に、PFIの岡野原さんが非常に分かりやすい解説記事を書かれており、本エントリー
遺伝的アルゴリズムを楽しく理解できるサイトをまとめてみた - download_takeshi’s diary
女優の菊川怜さんが学生時代に研究テーマにしていたという事で有名な「遺伝的アルゴリズム」ですが、名前の仰々しさとは裏腹に、意外と直感的に理解できる取っ付きやすいアルゴリズムだったりします。 それにしても菊川怜さん、美人ですねー。こんな先生にイロイロと教えてもらいたかったなぁ。。。 という願望はおいといて、「遺伝的アルゴリズム」を目で見て＆手で触って、直感的に「理解したつもり」になれそうなサイトをまとめてみました！ 学術的なことはガン無視でいきます。 動画で見て雰囲気を知る まずは動画で見て楽しみましょう。ニコ動から何本か動画を紹介します。 【人工知能】物理エンジンで人工生命つくって学習させた http://www.nicovideo.jp/watch/sm6392515 いきなりですが、強烈なインパクトをはなつ動画です。 人工生命がうにょうにょ動きながら、勝手に「歩き方」を学んでいきます。超
「組み合わせ爆発」動画のコンピューターをWebで実装 アルゴリズムを駆使した高速化モードも - はてなニュース
お姉さんが人生を懸けて「組み合わせ爆発」を解説する日本科学未来館の動画が、ネット上で大きな話題となりました。この動画に登場した「同じ場所を2度通らずに何通りの線が引けるか」という問題を解くコンピューターが、Webで実装されています。動画では6年掛かりで導き出された「9×9」マスの計算や、25万年掛かった「10×10」マスの計算も忠実に再現。動画の最後で言及されている、高速化したアルゴリズムで解くことも可能です。 ▽ おねえさんのコンピュータ ▽ お姉さんが人生を懸けて“組み合わせ爆発”を力説 動画「フカシギの数え方」が壮大すぎる - はてなニュース 再現された「おねえさんのコンピューター」を使って、実際に5×5の問題に挑戦してみました。動画でもそうだったように、数秒で計算が終了します。コンピューターが線を辿りながら組み合わせを計算している様子も再現されていました。 左が「おねえさんのコンピ
try-and-back-off アルゴリズム - melpon日記 - HaskellもC++もまともに扱えないへたれのページ
C++11 には、複数の Lockable なオブジェクトをロックしてくれる std::lock 関数があります。 template<class L1, class L2, class... L3> void lock(L1& m1, L2& m2, L3&... m3); この関数の最大の特徴は、決してデッドロックしないことです。 そして、このデッドロックしないという要件を満たすために使われるアルゴリズムが、try-and-back-off アルゴリズムと呼ばれるものです。 今回はこの try-and-back-off アルゴリズムについて説明します。 （この記事には独自解釈が含まれているので、間違ってる部分とかあれば指摘して頂けると嬉しいです） デッドロックの条件 デッドロックは、正確ではないですが、大まかに言って以下の条件を満たすと発生します。 ロックを取得するために待機を行なう あ
ImageMagick 改造入門 (その弐) 減色処理前編 | GREE Engineering
こんにちは。クライアント基盤チームのよやです。 アバター等を表示する為に PNG や JPEG の画像を元に GIF アニメーションを生成する事がよくありますが、GIF は 256色までしか扱えない為、元画像が数万といった単位で色を使っていると減色処理に大変時間がかかります。そこで、ImageMagick の減色処理を改造して高速化した事例をご紹介します。 尚、一度に読む分量ではまとめ切れない為、前編と後編に分けました。前編は減色処理、後編はその改造について説明します。 プログラム構成では上の図の magick/quantize.c が減色処理に相当します。 まず、減色処理の一般的な話から始めます。 減色の利点 Web で見かける画像ファイルの多くは、1つのpixel(描画の最小単位)に対して、Red, Green, Blue が各々8bits で計 24bits(= 3bytes) 、透
ImageMagick 改造入門 (その参) 減色処理後編 | GREE Engineering
こんにちは。クライアント基盤チームのよやです。 減色処理の話の続きで、ImageMagick の改造についてお話します。 前回 > ImageMagick 改造入門 (その弐) 減色処理前編 ImageMagick 減色処理の３つのフェーズのうち２つ目にあたる「RGB 空間で分割された立方体の統合処理」で特に時間がかかっていたので、少し手を加えて高速化しました。 前回のこの図に相当する処理です。 ImageMagick の既存の処理 前回、説明した「RGB 空間で分割された立方体の統合処理」のより細かい解説です。 統合処理の詳細 既存の ImageMagick の減色処理では、quantize_error の小さい順にRGB色空間内の立方体を削除して、それらのひとつ親の立方体に統合する処理を繰り返します。 対応コード (magick/quantize.c) 望みの色数になるまで繰り返す (
［SQEXOC 2012］FFXIVで使われているAI技術〜敵NPCはどうやって経路を探索しているのか？
［SQEXOC 2012］FFXIVで使われているAI技術〜敵NPCはどうやって経路を探索しているのか？ ライター：米田 聡 スクウェア・エニックスが2012年11月23日と24日の両日開催した「スクウェア・エニックス オープンカンファレンス」の最後には「AIセッション」が用意されていた。AIセッションは前半と後半に分かれ，前半は「ファイナルファンタジーXIV: 新生エオルゼア」（以下，新生FFXIV）における経路探索の実装に関する実践的な解説，後半はゲームAIの第一人者とも評される三宅陽一郎氏による，Luminous Studio用AIエンジンのやや概念的な話という構成だった。本稿では，まず前半の，より実践的なセッションから紹介してみたい。 テーマは，「MMORPGでマップ上を移動する敵NPCの経路をどう決めるのか」である。複雑で広いマップを有するMMORPGでは，移動する経路を賢く選択
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
バンディットアルゴリズム入門と実践
BLUE*アルゴリズム
