Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found
2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳 つまり「終わったコンテナ」。 以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。 徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。 そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構
P2Pの専門知識ゼロから独自DHTを実装評価するまでの学習方法と参考資料まとめ - 情報科学屋さんを目指す人のメモ（FC2ブログ版）
何かのやり方や、問題の解決方法をどんどんメモするブログ。そんな大学院生の活動「キャッシュ」に誰かがヒットしてくれることを祈って。 P2P、特にDHTの前提知識が無い状態から、オリジナルDHTアルゴリズムを実装・評価できるようになるまでの学習方法と参考資料をまとめました。 基本的なアルゴリズムの仕組みから、実装評価に用いるツールキットの使い方までを短期間で学習することが出来ます。 「P2Pに関する卒論を書こうと思っている人」や「P2Pアプリケーションの開発前に、アルゴリズムをテストしたい人」、「なんとなくP2Pアルゴリズムに興味が出た人」などにぴったりだと思います。また、研究室での後輩教育用資料にするのも良いと思います。実際に使いましたし。 ここで紹介する資料一覧は以下の通りです。 資料１：「ChordアルゴリズムによるDHT入門」 資料１ーオプション１：「DHTアルゴリズムSymphony
統計的機械学習入門
統計的機械学習入門(under construction) 機械学習の歴史ppt pdf 歴史以前 人工知能の時代 実用化の時代 導入ppt pdf 情報の変換過程のモデル化 ベイズ統計の意義 識別モデルと生成モデル 次元の呪い 損失関数, bias, variance, noise データの性質 数学のおさらいppt pdf 線形代数学で役立つ公式 確率分布 情報理論の諸概念 (KL-divergenceなど) 線形回帰と識別ppt pdf 線形回帰 正規方程式 正規化項の導入 線形識別 パーセプトロン カーネル法ppt pdf 線形識別の一般化 カーネルの構築法 最大マージン分類器 ソフトマージンの分類器 SVMによる回帰モデル SVM実装上の工夫 クラスタリングppt pdf 距離の定義 階層型クラスタリング K-means モデル推定ppt pdf 潜在変数のあるモデル EMアル
Karetta|Cパズルプログラミング-再帰編
はじめに基本的過ぎること階乗fact1.c (2)fact2.c (1)fact3.c組合せcomb1.ccomb2.ccomb3.c四則演算１行入力の動作確認expr1.cトークン処理の準備expr2.cトークンがやっと動き出すexpr3.c (1)数式もどきexpr4.c優先順位を考えた式の処理 (1)expr5.c整理expr6.c８クイーンボードの準備queen1.cqueen2.cクイーンを左端に置いてみようqueen3.cqueen4.cクイーンを８個置いてみようqueen5.cqueen6.cqueen7.c効き筋のチェックqueen8.cqueen9.cqueen10.cデバッグをする羽目にqueen11.cqueen11.txtqueen12.cqueen12.txtqueen13.c動くようになったので整理整頓queen14.cqueen15.c対称移動の研究対象移動の
γ符号、δ符号、ゴロム符号による圧縮効果 - naoyaのはてなダイアリー
通常の整数は 32 ビットは 4 バイトの固定長によるバイナリ符号ですが、小さな数字がたくさん出現し、大きな数字はほとんど出現しないという確率分布のもとでは無駄なビットが目立ちます。 Variable Byte Code (Byte Aligned 符号とも呼ばれます) は整数の符号化手法の一つで、この無駄を幾分解消します。詳しくは Introduction to Information Retrieval (以下 IIR) の第5章に掲載されています。(http://nlp.stanford.edu/IR-book/html/htmledition/variable-byte-codes-1.html で公開されています) Variable Byte Code はその名の通りバイトレベルの可変長符号で、1バイトの先頭1ビットを continuation ビットとして扱い、続く 7 ビット
yebo blog: クヌース教授は間違っていた
2010/06/15 クヌース教授は間違っていた Slashdotによれば、この数十年間、クヌース教授をはじめとするコンピュータ科学者が最適としてきたアルゴリズムを10倍高速にする方法をPoul-Henning Kamp (PHK) というハッカーが見付けたという。その論文タイトルは「You're Doing It Wrong (あなた達のやっている事は間違っている)」で、ACM Queueに掲載されている。別にクヌース教授の考えが間違っているわけではなく、アルゴリズム的には正しいが、実用レベルでは、OSには仮想メモリがあり、VMと干渉しないようにすれば簡単に高性能なシステムが作れる。従来の考え方はモダンな計算機を考慮に入れていないので、現実的には不適合を起こしている。具体的にはヒープにBツリーの要素を取り込んだBヒープというデータ構造を使うことで、バイナリヒープの10倍のパフォーマンスを
最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ
動的計画法とメモ化再帰 今回は、非常によく用いられるアルゴリズムである、「動的計画法」「メモ化再帰」について説明します。この2つはセットで覚えて、両方使えるようにしておくと便利です。 なお、メモ化再帰に関しては、第5・6回の連載の知識を踏まえた上で読んでいただけると、理解が深まります。まだお読みになっていない方は、この機会にぜひご覧ください。 中学受験などを経験された方であれば、こういった問題を一度は解いたことがあるのではないでしょうか。小学校の知識までで解こうとすれば、少し時間は掛かるかもしれませんが、それでもこれが解けないという方は少ないだろうと思います。 この問題をプログラムで解こうとすると、さまざまな解法が存在します。解き方によって計算時間や有効範囲が大きく変化しますので、それぞれのパターンについて考えます。 以下の説明では、縦h、横wとして表記し、プログラムの実行時間に関しては、
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
知れば天国、知らねば地獄――「探索」虎の巻
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 今後紹介していくアルゴリズムについて お待たせしました！ 「最強最速アルゴリズマー養成講座」という連載タイトルのとおり、今回の連載からいよいよ具体的なアルゴリズムの紹介に入っていきたいと思います。 しかし、それを読んでいただく前に、1つ注意してもらいたいことがあります。連載第3回でもお伝えしたように、「問題を、既存の適当なアルゴリズムに当てはめる」という考え方は、非常に危険である、ということです。 筆者の経験上、TopCoderでRedCoder以上を目指すのであれば、回答時間短縮のために、いままでのパターンを利用するのも方法の1つなのですが、本連載では
PubSubHubbubでRSSもTwitter並にリアルタイムに － ＠IT
2009/08/19 「PubSubHubbub」（パブサブハブバブ）という奇妙な名前のプロトコルが注目だ。2009年8月5日にグーグルはRSSリーダーサービスのGoogle ReaderでPubSubHubbub対応を明らかにしたほか、国内ではライブドアが、同じくRSSリーダー「livedoor Reader」とブログサービスの「livedoor Blog」でPubSubHubbubに初対応したことを8月18日に発表している。まだ対応サービスは少なく、その“効能”も「ブログの更新がRSSリーダーに反映されるのが、ほぼリアルタイムになりました」というだけで小さく見えるかもしれない。しかしPubSubHubbubは、ネット全体のリアルタイムコミュニケーションプラットフォーム化を促す重要なキーとなるかもしれない。 Twitterが見せつけた“リアルタイム”のテンポの良さ Twitter人気が高
PythonでA*(A-Star)アルゴリズム - Pashango’s Blog
今回はA*アルゴリズムをPythonでやってみます。 ゲームプログラマの間では、もはや常識となりつつある最短経路問題解決アルゴリズムです。 A*は、古典的手法である「ダイクストラ法」を改良したものです。 スタート地点からノードnを通ってゴールに辿り付くとき、最短距離をf(n)とすると、 f(n) = g(n) + h(n) とすることができます、g(n)は「スタートからノードnまでの最短距離」、h(n)は「ノードnからゴールまでの最短距離」です。 でも、最初から適切なg(n)とh(n)が判ってるなら苦労しませんよね。 だから、テキトーな予測値を使って、最短経路をある程度予測して効率的に経路探索をしてみようという事です。 テキトーな予測値を使った最短経路距離をf*(n)とすると f*(n) = g*(n) + h*(n) となります、f*(n)を求めるためにテキトーなg*(n)とh*(n)を
ネットワークプログラムのI/O戦略 - sdyuki-devel
図解求む。 以下「プロトコル処理」と「メッセージ処理」を分けて扱っているが、この差が顕著に出るのは全文検索エンジンや非同期ジョブサーバーなど、小さなメッセージで重い処理をするタイプ。ストリーム指向のプロトコルの場合は「プロトコル処理」を「ストリーム処理」に置き換えるといいかもしれない。 シングルスレッド･イベント駆動 コネクションN：スレッド１。epoll/kqueue/select を１つ使ってイベントループを作る。 マルチコアCPUでスケールしないので、サーバーでは今時このモデルは流行らない。 クライアントで非同期なメッセージングをやりたい場合はこのモデルを使える： サーバーにメッセージを送信 イベントハンドラを登録；このときイベントハンドラのポインタを取っておく イベントハンドラ->フラグ がONになるまでイベントループを回す イベントハンドラ->結果 を返す １コネクション１スレッ
静かな注目を集める圧縮アルゴリズム「LZMA」
GNUプロジェクトの配布アーカイブなどを中心に、LZMAを用いた圧縮形式を目にする機会が増えてきた。組み込み用途などへの活用も期待されるこの圧縮形式を紹介しよう。 2001年に開発された可逆圧縮アルゴリズム「LZMA」（Lempel-Ziv-Markov chain-Algorithm）が静かな注目を集めている。LZMAといえば、高い圧縮率を備え、Windowsアーカイバ「7-Zip」に採用されていることでも知られる。 ZIPやLHAなど、ファイルのアーカイブと圧縮が統合されているWindows由来のプログラムとは異なり、UNIXやLinuxでは伝統的にアーカイブと圧縮が個々のコマンドとして用意されており、それらを組み合わせて利用することになる。現在では、アーカイブがtar、圧縮にはGNU zip（.gz）やbzip2（.bz2）が併用されることが多い。 .gzや.bz2をしのぐ圧縮率が特
ほぼ日刊イトイ新聞 - がんばれ森川くんの遺伝子くん
＜群れの知能＞ 前回まで考えない知能の代表として、 ゴキブリを紹介してきましたが、 昆虫には、彼のように １匹オオカミ（ゴキブリ）として生活するものと、 アリやハチのように集団を作って生活するものがいます。 今回は、この「群れの知能」がテーマです。 アリやハチの「社会」を見ていると、 なんだか、とても複雑なルールがあるように見え、 私たち人間の社会と似ている！同じだ！おれは働き蜂だ！！ と感じてしまうことも多いです。 そして、つい、社会を構成するものたちも、 私たちと同じように 「考える知能」の持ち主じゃないかと 思ってしまいがちです。 ところが、ところが、 この一見複雑で高度で知的に見える「群れの動き」が、 実はすっごく簡単なルールで作れてしまうとしたら、 どーしましょう。 上の３段論法 １：アリやハチの群れの動きは、とても複雑である。 ２：複雑な群れの動きは、 複雑で高度な知性（ルール
Boidsとは
Boid（ボイド）とは、1987年にCraig Raynoldsによって発表された理論です。 この理論は、３つのルールを規定するだけで鳥の群れをシミュレーションできるというものです。 ちなみにBoidという名の由来は、鳥もどきという意味の言葉birdoid（バードイド）が短くなりこのように呼ばれるようになりました。 さて、Boidsの３つのルールとは、以下の通りです。 Separationは、近くの鳥や物体に近づきすぎたらぶつからないように離れるルールです。 もし、ボイド同士が近づきすぎてしまったら、前を飛んでいるボイドはスピードを速くし、 後ろを飛んでいるボイドはスピードを遅くするようにします。 障害物、例えば柱とか壁とかに対しては、それにぶつからないように方向転換して衝突を避けるようにします。 Alingmentは、近くの鳥たちと飛ぶスピードや方向を合わせようとするルールです。 すなわ
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
Infoseek[インフォシーク] - 楽天が運営するポータルサイト
Infoseek, およびInfoseekロゴは 楽天株式会社の商標です。 これら以外のマークは、それぞれ関係各社の商標および登録商標です。 Copyright (c) Rakuten, Inc. All Rights Reserved.
![Infoseek[インフォシーク] - 楽天が運営するポータルサイト](https://cdn-ak-scissors.b.st-hatena.com/image/square/67a82fbafb5e06f77d53cedfd9ceb7f789258213/height=288;version=1;width=512/https%3A%2F%2Fimage.infoseek.rakuten.co.jp%2Fcontent%2Ftop-ajax%2Fmobile%2Flogo.png)
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Amazon.co.jp: ニューメリカルレシピ・イン・シー 日本語版: C言語による数値計算のレシピ: William H.Press (著), 丹慶勝市 (翻訳): 本