Scalable memory allocation using jemallocの備忘録的和訳 - はてなかよっ！
Scalable memory allocation using jemalloc jemallocは今使ったりしてるし，今後ソース読む可能性もあるので，適当に(精度とかは期待しないように！)．気になる人は元記事を読みましょう． Scalable memory allocation using jemalloc Facebookは，8コア+CPUと8GiB RAMな専用マシンの上で走っている，様々な種類のサーバアプリケーションの集合で構成されています．これらのアプリケーションは，CPUとRAMと最大限使う事によって最高のスループットを目標に，並行処理のため大体POSIXスレッドを使っています．この環境は，メモリアロケーションのための重大なチャレンジをもたらします．具体的に言えば， 確保と解放は速くなければいけません．理想的に，メモリアロケーションはアプリケーションの定常状態においてはほとん
私が書いた最速のハッシュテーブル – PART 2 | POSTD
素数か2のべき乗か ハッシュテーブルのアイテムをルックアップする際に高負荷なステップが3つあります。 キーをハッシングする キーをスロットにマッピングする 該当スロットのメモリをフェッチする ステップ1は、キーが整数であれば、低負荷になります。単にintをsize_tにキャストするだけです。しかし、文字列のようなタイプのキーの場合は高負荷となります。 ステップ2はよくある整数モジュロ演算です。 ステップ3はポインタの間接参照です。std::unordered_mapの場合は複数のポインタ間接参照となります。 処理の遅いハッシュ関数でなければ、直観的にステップ3が最も高負荷になると考えると思います。しかし、全てのルックアップでキャッシュミスが生じなければ、整数モジュロが最も高負荷な処理となります。現代のハードウェアにおいても整数モジュロは非常に遅いのです。 Intelマニュアル では、整数モ
MySQLのfilesortは何ソートで行われているのか - $shibayu36->blog;
最近、CourseraのArgorithms, Part1という講義を受けている。そこでソートの講義を受けて、そういえばMySQLのORDER BYでfilesortになったときってどのソートが使われているのだろうと気になってきたので調べてみた。 調べてみると非常に難解で、結局いまいち分からなかったが、今の段階の調べた内容をひとまず書いておく。MySQLのコードを読んだのも初めてで、しかもちゃんと読み解くことができなかったので、情報が間違っている可能性も非常に高い。間違ってたら指摘してもらえるとうれしいです。 調査結果 最初に調査結果を書いておく。たぶんこれは非常に単純化したもので、詳しく見るともっといろいろチューニングされてそう。 sort_buffer_size以内のメモリ量でソートが可能な場合、メモリ内でのみソートされる ソートにsort_buffer_size以上のメモリが必要な場
RFC6238 Time-based One-time Password Algorithm (TOTP)の仕組みのメモ - Qiita
RFCはこれ。Javaでの実装例もアリ: RFC 6238 - TOTP: Time-Based One-Time Password Algorithm RFCも十分短いけど、Wikipediaのほうはさらに簡潔: Time-based One-time Password Algorithm - Wikipedia, the free encyclopedia 日本語での参照情報: Googleの2段階認証で使われているOTPの仕様が気になった - r-weblife RFCに書いてある実装使うとかでサクッとワンタイムパスワードを生成できるので、もっと普及するといいですね。その場合はシークレットの扱いは適切にお願いします。 認証の概要 サーバーと共有しているシークレットキーと現在時刻からハッシュを生成してそれが合ってるかをみる、というのが大筋の流れ。 ワンタイムパスワードの生成 Wikip
私が書いた最速のハッシュテーブル – PART 1 | POSTD
結局、やり出したら止まりません。私は以前、” I Wrote a Fast Hashtable（私が書いた高速なハッシュテーブル） “という記事と、それに次いで” I Wrote a Faster Hashtable（私が書いたより高速なハッシュテーブル） “という記事をブログにアップしましたが、今回ついに、最速のハッシュテーブルを書き上げました。これが意味するところは、ルックアップがどのハッシュテーブルよりも速いということです。それに加えて、挿入や削除も（最速とまではいかないまでも）非常に速く行えます。 秘訣は、探索回数の上限を設定したロビンフッドハッシュ法を使用することです。ある要素が、その理想的な位置からX数以上、離れた位置にある場合、テーブルを拡張することで、全ての要素が、その大きなテーブル内において、理想的な位置に近づくようにします。結果的に、このやり方は非常にうまくいきました。
CYK法 - Wikipedia
CYK法（英: CYK algorithm）は、ある文字列が与えられた文脈自由文法で生成できるかを決め、生成できる場合の生成方法を求めるアルゴリズムである。CYK は Cocke-Younger-Kasami の略（それぞれ、RISCの先駆と言われる801などでも知られるジョン・コック、Daniel Younger、嵩忠雄である）。文脈自由文法の構文解析手法と捉えることもできる。このアルゴリズムは一種の動的計画法である。 標準的なCYK法は、チョムスキー標準形で書かれた文脈自由文法で定義される言語を認識する。任意の文脈自由文法をチョムスキー標準形に書き換えるのはそれほど困難ではないので、CYK法は任意の文脈自由文法の認識に使うことができる。CYK法を拡張してチョムスキー標準形で書かれていない文脈自由文法を扱うようにすることも可能である。これにより性能は向上するが、アルゴリズムを理解すること
DSL-Researches
近年，通信理論の分野でgossipプロトコルという通信手法が注目されている．これは情報伝達を確率的に行う手法のひとつであり，例えばアドホックネットワーク上でルーティングを行う際などに多く用いられる[1-4]．しかし，gossipプロトコルの性能評価に関する理論的な結果はあまり多くない．また，gossipプロトコルは単一のパケットを拡散する場合のみが陽に考慮されており，複数のパケットを同時に拡散させた場合に関する研究はなされていないなどの問題もある． そこで本研究では，複数の情報が拡散するという現象を調べるために，既存のgossipプロトコルを拡張し，同時に複数の情報を扱えるようにする．そしてその拡張されたgossipプロトコルにおける情報浸透確率などを解析し，その性質を調べていく． Gossipプロトコル 近年，身の回りのあらゆる物を有線あるいは無線のネットワークでつなぐことで様々なサービ
Union Findアルゴリズムの様々な実装とパフォーマンス計測 - $shibayu36->blog;
CourseraにAlgorithms Part1という授業があり、これが非常に評判が良いので、会社で勉強会をしている。Week1にUnion Findというアルゴリズムが出てきて、その実装パターンがいくつかあった。それぞれ計算量が違うらしいのだけど、速度がどのように変化するか試したかったので、実装してパフォーマンス計測をしてみた。それぞれの実装の詳しい説明が知りたかったら、https://www.coursera.org/learn/algorithms-part1 を見ると良い。 Union Findとは何か 二つのノードを繋いでいき(Union)、あるノードとあるノードがつながっているか(Find or Connected)を判定するアルゴリズム。 例えば、union(1,6)、union(5,6)、union(2,7)、union(3,8)、union(4,9)、union(8,9
Suffix ArrayをRustで実装した - Islands in the byte stream
suffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6) - $shibayu36->blog; を読んで、ちょうど自分も何らかの形で全文検索を一部実装してみようと思っていたのでRustで真似してみました。 Rustを選んだ理由は、以下の理由からです。 実際に全文検索を実装するのに耐えうるパフォーマンスであること パッケージマネージャなどのエコシステムが完備されていること Rustについてはそれほど詳しくはないのですが、GCや例外がないとのこと。であればパフォーマンスチューニングがC言語並にやりやすい可能性がありますし、一度真面目に勉強してみたいと思っていました。Goと異なり、ジェネリクスがあるのも魅力的です。 というわけでコードこんな感じになりました: pub fn make_suffix_array(s: &str) -> Vec<i64> { use
文字列アルゴリズムの学びかた - Hatena Developer Blog
こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？ パーサやコンパイラを作りたいけど、何から始めればいいのか？ 本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
技術面接を受ける前に確認しておくといいこと | Wantedly Engineer Blog
ここで書くのは基本的なことなので、実際の面接ではもう少し複雑な問題になるかもしれません。 逆にいうと、このあたりの問題は一度は解いておいた方がいいので列挙しました。 普段ウェブの開発をしているだけでは考えたことがない場合もあるので、一度確認するといいかもしれないです。 アルゴリズムチェックポイント計算量, ハッシュと二分木, ソート, 再帰 計算量計算量の話 http://qiita.com/cotrpepe/items/1f4c38cc9d3e3a5f5e9c 二分探索とは https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2 ハッシュテーブルとは https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86%E3%83
Rust Collections Case Study: BTreeMap
Rust Collections Case Study: BTreeMap Alexis Beingessner This is the third entry in a series on implementing collections in the Rust programming language. The full list of entries can be found here. In my previous two posts I talked a lot about some high-level patterns and issues that make implementing collections in Rust an interesting problem. Today I'd like to really dig into one of my two favo
データ検証などで利用するMerkle Treeのメモ
データの検証などで利用される Merkle tree/マークル木/hash tree/ハッシュ木についてメモ。 Merkle Tree の概要 wikipedia の概要をそのままコピペ。 暗号理論および計算機科学において、ハッシュ木(Hash tree, ハッシュツリー)またはマークル木(Merkle tree)とは、より大きなデータ（例えばファイル）の要約結果を格納する木構造の一種であり、データの検証を行う際に使用される。このデータ構造はハッシュリストとハッシュチェインの組み合わせでできており、ハッシュ法の延長上にある手法といえる。 Merkle tree の利用例 merkle tree が2つ与えられた時に、ルートノードから子ノードに向かってハッシュ値をたどっていけば、どこが壊れているのか特定が簡単で、壊れている部分木だけを更新すればよい。 Amazon dynamo/cassan
Five Myths about Hash Tables
A hash table is data structure that is used to search for exact matches to a search key. For searching, they work like this: Take a search key (example: the word “cat”) Hash the search key: pass the key to a function that returns an integer value (example: the hash function returns 47 when the input key is “cat”) Use the integer value to inspect a slot to see if it contains the search key (example
高速なハッシュテーブルを設計する | POSTD
(訳注：2016/9/28、頂きましたフィードバックを元に記事を修正いたしました。) はじめに 本稿では、高速で汎用的なハッシュテーブルを作るために行う、設計についての多くの意思決定事項を紹介します。最終的に、私の emilib::HashSet とC++11の std::unordered_set の間のベンチマークが出来上がりました。もし、ハッシュテーブルに興味があって、自分で設計したいなら（どのプログラミング言語かに関わらず）、本稿がヒントになるかもしれません。 ハッシュテーブル は、素晴らしい発明です。 ならし計算量O(1) ( O(√N)時間 )で、挿入、削除、検索を行うことができます。ならし計算量とは、ハッシュテーブルの計算に平均でO(1)の計算量がかかることを意味しますが、時々、これよりも多くの時間がかかる場合があります。具体的には、ハッシュテーブルに空きがない場合で、挿入の
Page Redirection
If you are not redirected automatically, follow this link to the article..
The Lynx Queue | Department of Computer Science and Technology
Submitted by Timothy Jones on Tue, 09/08/2016 - 13:06 This post is about my group’s second ICS paper from June this year, which describes a new single producer / single consumer (SP/SC) software queue that we developed for frequent inter-core communication. It’s faster than existing implementations and we call it Lynx. It’s available on my group’s data page. Initially, we didn’t set out to create
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
500 Data Structures and Algorithms interview questions and their solutions
すぐお金必要な時に借りれるカード会社【今日融資して欲しい方向けバレないカードローン】
6.851: Advanced Data Structures