未初期化メモリを使う方法 - Radium Software
research!rsc: Using Uninitialized Memory for Fun and Profit N個のフラグを扱う場面があるとする。まず，こんな感じで書き始めることになると思う。 bool flags[N]; for (int i=0; i<N; ++i) flags[i]=false; もしこのとき，Nがものすごく大きかったら……フラグをクリアする処理だけで，結構な時間を食ってしまうかもしれない。 そんなときのために編み出されたのが，上のエントリーで紹介されているアルゴリズム。二つのテーブルを組み合わせて使うことにより，メモリを未初期化のまま使うことを可能にしている。 未初期化のメモリへのアクセスなんて，それ自体が不正なことのように感じられるかもしれないけれど，たまには未初期化のまま使ってみるのもオツなものですよ……という話。実用性については，正直なところあまり無
『はてなブックマークリニューアル』
日記を相当長い間書いていませんでしたすいません・・・ 今日は、ちょっと時期をのがしてしまいましたが、はてなブックマークリニューアルについて書いてみようと思います。まずは、リニューアルおめでとうございます！＞はてなの皆様 今回のはてなブックマークリニューアルでは、弊社は、はてなブックマークのエントリ全文検索に携わりました。弊社の全文検索エンジンである、「Sedue」を用いて、複数台で全文検索機能を実現しています。リアルタイム性と大規模な検索が必要なタスクであったので、Sedueは今回のタスクにぴったりなエンジンでした。 エンジン自体は、もともと分散環境でいかに簡単に動作させるか、が売りのエンジンなので、すぐに稼働させることができました。ランキングの部分は、かなり力をいれていて、id:naoyaさんと弊社のCTO太田、エンジニアの久保田が協力して作成していきました。ランキングは、もうすでに汎用
とりとめのないパーサー談義 - あどけない話
パーサーに関して、調べたことと疑問を書いておきます。パーサーに詳しい人に答えて頂けると、とても嬉しいです。 チョムスキー階層によれば、以下のような関係が成り立ちます。 正規文法 < 文脈自由文法 < 文脈依存文法 < 制限のない文法 それで、文脈自由文法の中は、こういう関係が成り立ちます。 LL法 < SL法 < LALR法 < LR法 < GLR法 GLR法は、文脈自由文法の全体を解析できる能力を持ちます。 疑問1) GLR法は、文脈依存文法(の一部)も解析できるのか？ LL(1) LL(1)に、収まっているのは XML や Lisp です。 LALR(1) LALR(1)に、収まっているのは、ほとんどのコンピュータ言語です。たとえば、C や Java。 GLR GLRに収まっているのは、C++ です。たとえば、D 言語の「テンプレート再訪」には、以下のように文脈がないと比較なのかテンプ
Google の秘密 - PageRank 徹底解説
INDEX はじめに PageRank の基本概念 どうやって PageRank を求めるか 現実に適用する際の問題 Namazu での実装実験 PageRank に対する個人的見解 参考文献 おまけ：「グーグル？／ゴーグル？」 Since: Thu Feb 1 18:22:44 JST 2001 Last Refreshed: Sat Jan 24 18:30:35 JST 2004 ★(2004/1/24) Yuan Huanglin氏によって 本ページの中国語訳 が作成されました。 ★(2003/7/1) 拙著『Namazuシステムの構築と活用』を改訂しました。 詳しくは サポートページをご覧ください。 ★(2003/5/20) Google に関するオンラインニュース記事一覧(日本語記事のみ)を 別ページ(googlenews.html) として分離しました。 ★(2001/2/
GIFライセンス問題についてわかるページ
【集中企画】 GIFライセンス問題についてわかるページ さきごろ、Webブラウザーやメールソフトなど、Internet Explorer（IE）コンポーネントを呼び出しているソフトがいくつか、公開中止や仕様変更となった。これは、GIFフォーマットで使われているLZW圧縮伸張アルゴリズムに関して米Unisysが特許を持っており、これを使ったソフトを開発するにはライセンスを受ける必要があることによるもの。Microsoftは自社のライセンスについて、Microsoft製品を部品として使う開発者には適用されないと声明しており、ソフト作者がライセンス違反を懸念して今回の動きとなった。 今回の集中企画では、このGIF（LZW）ライセンス問題についてWebで論じているページを見てみる。 注意：ここで紹介するのはあくまでも各サイトの論点であり、その見解そのものを保証するものではありません。
レコメンデーションの虚実（3）～顧客属性はなぜ追い求められなかったのか
レコメンデーションの虚実（3）～顧客属性はなぜ追い求められなかったのか：ソーシャルメディア セカンドステージ（1/2 ページ） 「顧客の属性」を読み取る方法 連載前回で、協調フィルタリングには顧客同士の行動の類似性を見ているだけで、“顧客の属性を見ていない”という問題があるということを書いた。例えば、妻にプレゼントするために夫が女性用化粧品を購入すると、その後しばらくは女性用化粧品をさかんに勧められるような現象が起きてしまうというようなことを挙げた。そしてこうした顧客の属性を見ていないという問題は、コンテンツフィルタリングでも協調フィルタリングでもカバーできないということも書いた。 「モノを買う」という行動を解析してみよう。バラバラに分解すれば、次の3つに分けることができる。 ・商品の属性（その商品がどのような分野の商品で、どのような名前を持ち、どのような特徴があるのか） ・顧客の属性（顧
ソーシャルメディア セカンドステージ：【第2回】レコメンデーションの虚実（2）?レコメンデーションの分類 (1/2) - ITmedia アンカーデスク
レコメンデーションの代表的手法 レコメンデーションには、いくつかのアプローチがある。とりあえずそのアプローチを俯瞰してみると、おおむね以下の5つに分類することができる。 （1）ルールに基づくレコメンデーション （2）コンテンツベースのフィルタリング （3）協調フィルタリング （4）統計学的なアプローチ （5）行動ターゲティング （6）ソーシャルネットワーキング ひとつずつ説明していこう。 （1）のルールに基づくレコメンデーションというのは、「ビジネスルール方式」とか「インテンショナル（意図的な）レコメンド」などと言った呼び方もある。例えば「美容室に髪を切りに来た人に、ヘアケア製品を勧める」「プリンターを買った人に、インクトナーを勧める」など、最初に「ある製品を買った人、ある行動をした人には、この製品やサービスを勧める」というルールを定めておく方法だ。このレコメンデーションはわかりやすいけれ
レコメンデーションの虚実（1）〜認知限界をどう乗り越えるのか (1/2) - ITmedia アンカーデスク
【新連載】レコメンデーションの虚実（1）～認知限界をどう乗り越えるのか：ソーシャルメディア セカンドステージ（1/2 ページ） ネット情報増大と認知限界 インターネットの情報は、今や洪水のようになっている。この洪水の中からどのように有用なコンテンツやデータをすくい上げるのかは、インターネットにおける最も重要なテーマだ。この問題を解決するアーキテクチャとしては検索エンジンが長く定番だったが、情報のオーバーロード（過負荷）が起きている中で、検索エンジンだけでは対応しきれなくなった。 つまりはネットの情報の総体が、人間の認知能力をはるかに超えてしまっているということだ。これを「認知限界」という。認知限界というのはもともと、1978年にノーベル経済学賞を受賞したアメリカの経営学者、ハーバート・アレクサンダー・サイモンが企業などの組織を説明するために使った言葉である。外の世界がどんどん複雑になってく
第10回 麻雀の役を判定する：ITpro
図1に示す(1)から(3)までの麻雀（マージャン）の手牌があります。「あがり牌」はすべて山からツモったものとし，リーチはかけていません。またドラやハイテイ＊1なども関係ないものとします。これらの役を判定して，親の場合の点数を計算するプログラムを作ってください。 「ややこしや～ややこしや～」というのは野村萬斎ですが，思わずそううなってしまうことがプログラミングをしているとよくあります。今回の麻雀の役判定は，考えれば考えていくほどややこしく，そうしたものの代表と言えるでしょう。排他処理や優先順位が複雑にからんでいて一筋縄ではいきません。 今回はややこしい組み合わせを解決する方法を考えてみます。麻雀になじみのない方も，ちょっとしたパズル気分で試してみてください。 麻雀の役を考える 麻雀を知らない方のためにルールをおおざっぱに説明しておきましょう＊2。麻雀の牌には，大きく分けて「萬子（マンズ）」「
Towards a Scalable Non-Blocking Coding Style（状態遷移機械の設計に関して）
Webinar: Managing the Security and Commercial Impact of Java Updates March 12, 2020 Live WebinarJoin Azul and SoftwareONE for this webinar about the security and commercial applications of Java...Read More dev.next March 24-27, 2020 Broomfield, CO, USAAzul is one of the sponsors at this event which brings together practitioners, experts, and...Read More
Sorting a million 32-bit integers in 2MB of RAM using Python
Ramblings through technology, politics, culture and philosophy by the creator of the Python programming language. Someone jokingly asked me how I would sort a million 32-bit integers in 2 megabytes of RAM, using Python. Taking up the challenge, I leared something about buffered I/O. Obviously this is a joke question -- the data alone would take up 4 megabytes, assuming binary encoding! But there's
画像圧縮アルゴリズム (10) 算術符号化
Range Coder復号化処理による数直線の変化は、以下のようになります。 復号化の場合、数直線は常に0からRangeまでの範囲になります。符号が数直線上のどこに位置しているのかをチェックして、Rangeを復号化されたデータが持つ範囲に変換するところは、やはり算術符号化での処理と本質的に変わりありません。 処理方法は以上になりますが、ここでいくつかの問題を解決する必要があります。まず一つは、符号化と復号化での計算で使用している変数Range / Sizeが0になる可能性があるということで、このときはRangeを計算した結果が0になってしまうため、処理を続けることができなくなります。よってRangeの取り得る最小値は、データのサイズより大きくなければなりません。Range / Sizeが0になった場合、サンプル・プログラムでは単純にエラー終了しています。Rangeの最小値はサンプル・プログ
フィボナッチヒープ - Wikipedia
フィボナッチヒープの例。次数0，1，3の3つの木を持つ。(水色で示されている)3つの頂点はマークされている。それゆえにヒープのポテンシャルは9である。 フィボナッチヒープはminimum-heap propertyを満足する木の集まりである。つまり、ある子のキーは常に親のキーよりも等しいか大きい。つまり最小のキーは常に何れかの木のルートにある。二項ヒープと比較してフィボナッチヒープの構造はより柔軟である。木は規定された形を特に持っておらず、極端な場合はヒープ中の n 個の要素が全て別々の（n 個の）木に属しているかもしれないし、深さ n の一つの木に属しているかもしれない。この柔軟さによって、ある種の操作を後回しにするなど「怠惰な」処理方法が許される。例えば、二つのヒープを結合するには単に二つのヒープの木のリストを連結するだけで良いし、「キーの減算」操作の過程ではあるノードが親から切り離さ
DO++: 左傾赤黒木
漢字で書くと仰々しいが、赤黒木 (wikipedia) red-black tree (english wikipedia)という平衡二分木で最も多くつかわれているデータ構造の、改善版が出てたそうだ。 left-leaning red-black tree (pdf) 日本語に訳すと左傾赤黒木かな。簡単な漢字を並べている感じがしてしまう 赤黒木の詳細については、wikipediaなどをよんでもらうとして、これは更新時間が定数で更新箇所が局所的（これはマルチスレッドとかでロックする箇所をかなり細かい単位で、できるという強い利点もある）のだが、実装が結構面倒くさい。例えばC++ stl のmapとかの赤黒木の実装のstl_tree.h(google code search)は大変なことになっている（特にRb_tree_rebalance_for_eraseとか） 赤黒木というのは動的データ構造
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
[Think IT] 【深きプログラミング言語】続・アルゴリズムで頭の体操
http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html
Amazon.co.jp: アルゴリズム入門: 設計と解析 (HigherEducationComputerSeries 32): サラバッセ (著), Basse,Sara (原名), 和生,岩野 (翻訳), 仁,永持 (翻訳), 直樹,加藤 (翻訳): 本
サービス終了のお知らせ
Google Code Archive - Long-term storage for Google Code Project Hosting.
teacup. byGMO サービス終了のお知らせ｜GMO MEDIA
