XXmallocのメモリ管理アルゴリズムについてわかりやすい記事 - QiitaDeleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?
ned Productions - nedmalloc
If you want an explanation of the difference between the Packetised and Memory Mapped benchmarks, please see the Tn homepage (but basically, the Packetised involves performing a lot more memory ops in a more loaded multithreaded environment). As you can see above, the benefits of nedmalloc translate into real world code with more than a 50% speed increase over the default win32 allocator. The Tn s
公理的意味論を使ってプログラムの正しさを証明する (2)
公理的意味論 (axiomatic semantics) の2回目。 今回は二分探索をおこなうプログラムを検証する。 まとめ: 二分探索 (binary search) とは、 ソートされた数値の順列から目的の要素をすばやく検索するアルゴリズムである。 以下のような n個の要素をもつ数列 a = [ 0, ..., i0, ..., i, ..., i1, ... n-1 ] があるとき、2つの点 i0, i1 にはさまれた中点 i を考える。ここで、 目的の要素が [i0,i) の間にあれば、i よりも左側にある範囲を探索する。 目的の要素が [i,i1) の間にあれば、i よりも右側にある範囲を探索する。 以上の操作で、毎回、探索する要素の個数は半分になっていく。 これを繰り返すと、最終的に約 log2(n) の繰り返しで目的の要素を発見できる。 これは n個の要素を左から順に調べる
連想配列の進化 - DO++
キーに対して値を結びつける連想配列は多くのアプリケーションの肝であり、コンパクトかつ高速な処理が可能な連想配列を追い求め日夜研究が進められています。 特に非常に巨大な連想配列を高速に処理するというのが重要な課題となっています。例えば、音声認識・文字認識・機械翻訳などで使われている言語モデルでは、非常に大量のN個の単語列の情報（特に頻度）を格納することが重要になります。 この場合、キーが単語列であり、値が単語列のコーパス中での頻度に対応します。 例えばGoogle N-gram Corpusからは数十億種類ものN-gramのキーとその頻度などが取得できます。これらを主記憶上に格納し、それに関する情報（頻度や特徴情報）を操作することが必要になります。 そのほかにも大規模なデータを扱う問題の多くが巨大な連想配列を必要とします。 ここではこのような連想配列の中でも、キーの情報を格納することすら難し
一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
同じ文字列のn回繰り返しを作る最速の方法を探求してみた - moriyoshiの日記
注意: FF3.1b2の結果が不正確です。取り直したのはこちら。 ちょっとした事情により、ある文字列のn回繰り返しを作る関数 (PHPでいうところのarray_repeat(), Perlで言うところの「"..." x n」、RubyやPythonで言うところの「"..." * n」) を高速に実装しなければならない状況に遭遇したのでベンチマークをとってみたところ、その結果がとても新鮮で驚いたので、これを共有しつつもダメ出ししてもらえないかなーと思って晒してみることに。 あらまし JavaScriptの文字列型 (およびStringオブジェクト) はJavaのようにイミュータブルなので、こういう文字列構築を行う方法としては、以前から、+や+=演算子を用いるよりも、一旦Array()に入れておき最後にjoin()するという方法が有効だと言われていてですね、まあ確かに、文字列用メモリ領域の確保
連載：検索エンジンを作る｜gihyo.jp … 技術評論社
運営元のロゴ Copyright © 2007-2025 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
SIMD-oriented Fast Mersenne Twister (SFMT)
SIMD-oriented Fast Mersenne Twister (SFMT): twice faster than Mersenne Twister*1. English Version 最新情報 SFMT ver1.5.1 をリリースしました。(2017/2/22) SFMT ver1.5 をリリースしました。 53bit精度double出力にバグがありました。(2017/2/7) SFMT 論文の正誤表 を追加しました。(2015/9/1) dSFMT ver2.2.3 をリリースしました。(2013/12/19) SFMT ver1.4.1 をリリースしました。(2013/12/19) dSFMT ver2.2.2 をリリースしました。 ver2.2.2 はVisual C++ 2012 でコンパイルエラーになる部分を修正しました。 (2013/9/17) dSFMT ver
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
文書比較（diff）アルゴリズム
文書比較（diff）アルゴリズム 前のドキュメント 次のドキュメント ＶｉＶｉの文書比較（diff）機能で使用しているアルゴリズムについて解説する。 これらのアルゴリズムは Myers 氏らの論文によるもので、氏は筆者のためにわざわざ論文をＷｅｂサイトで入手可能な形式にしてくださった。この場を借りてお礼申し上げる。 オリジナル論文は以下のＷｅｂサイトから入手可能である。 http://www.cs.arizona.edu/people/gene [1] E.W.Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica, 1 (1986), pp.251-266 [2] S. Wu, U. Manber, G. Myers and W. Miller, "An O(NP) Sequence Comparis
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
w.l.o.g. ギャップバッファ
04:40 04/06/04 ピーステーブル PieceTable とも言う。文字列の Piece（小片）を繋げて、 一つの巨大な文書を表現する方式。 検索すると引っかかる文書のほとんどが AbiWord 関係なので、 このワープロソフトの主要な内部データ構造ということなのかな。 他に、MS-WordやOpenOffice.org関連の文書にも登場していて、 基本的に単なるテキストエディタよりは、文字に付加情報をくっつける系の 編集ソフトに使われる場面が今のところ多いみたいです。 余談ですがAbiWordは、綱渡り的にですがBeOS版の開発が続いている貴重なワープロソフトなのです。感謝感謝。 概要 ファイルを読み込んだとしましょう。ABCDEFG、という７文字のファイル。 とりあえず、７文字分のOrigという名前のバッファを用意して、そこに格納します。 それと別に、Addという名前の空のバ
第6回 上手なアルゴリズムの見つけ方
図1に示すHTML形式のテキスト・データ（以下，HTMLデータ）があります。このHTMLデータをブラウザに表示させたときに「表示される文字列」と「その文字列に対して有効なタグ名」を対応付けるアルゴリズムを考えてください。結果は配列に格納して，画面に表示させるものとします（図2）。 見わたせば，世の中はアルゴリズムだらけです。私のようなプログラマは，日常生活でも「締め切り順に仕事をソートしてごらん」「仕事のスタックがたまっているからてんてこまい」など，いま置かれている状態をアルゴリズムやデータ構造になぞらえて会話することがよくあります。前回紹介した再帰処理と言えば，落語の演目の一つ，「頭山」です。自分の頭に生えた桜の木を引っこ抜いて，その跡にできた池に自分自身が身を投げる，という不思議な話ですが，これこそ再帰処理をよく言い表していると思います。 このように世の中には，ハッシュだってスタックだ
The Aggregate Magic Algorithms
There are lots of people and places that create and collect algorithms of all types (here are a few WWW sites). Unfortunately, in building systems hardware and software, we in The Aggregate often have found it necessary to do relatively obscure low-level things very efficiently. Many of the tricks we've devised or collected either require assembly language coding or are not entirely portable when
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
