最近、簡潔データ構造(Succinct Data Structure)がじわじわ人気が出てきているように感じるので入門の入門、くらいの記事を書いておく。 この記事では簡潔データ構造において最も基本的なデータ構造である完備辞書(Fully Indexable Dictionary)について説明する。 新しい概念が出てきた時に気になるのは「どうやって実現するのか」「それができると何が嬉しいのか」という2点だと思う。 前者についてはこの記事(http://d.hatena.ne.jp/takeda25/20140201/1391250137)がわかりやすいのでここでは述べない。この記事では「完備辞書があると何が嬉しいのか」について説明する。 完備辞書とは 完備辞書はrankおよびselectという操作が定数時間で実行できるビット列のこと。rank(i)はi番目のビットより前にいくつ1があるかを返
概要 インデックスに対してMongoDBはB Treeを採用し、MySQLのInnoDBはB+ Treeを採用しています。 どうして採用しているアルゴリズムが違うのだろう？と思って調べてみました。 主な違い B+ TreeはほとんどB Treeと同じですが、以下の点が異なります。 リーフノードとリーフノードを結ぶポインタがある データはリーフノードのみに保持する 具体例 言葉だけだと分かりにくいので、Visualizeするツールを使って具体例を表示します。 [1, 2, 3, 4, 5, 6, 8, 10, 15, 18]という数列に対し、Order: 3で作ってみます。 Orderは１ノードから出る枝の数のことです。 B Tree B-Tree Visualization B+ Tree B+ Tree Visualization 先程のB Treeと違って、データはリーフノードに持つの
電子署名というと、RSA 署名や DSA、ECDSA などが有名ですが、これ以外にも無数の電子署名方式が提案さ …
ほとんどの開発者は、自動のガベージコレクション（GC）を当たり前のように使っています。これは、私たちの仕事を容易にするために言語ランタイムが提供する素晴らしい機能の1つです。 しかし、最新のガベージコレクタの中をのぞいてみれば、実際の仕組みは非常に理解しづらいことが分かります。実装の詳細が無数にあるため、それが何をしようとしているのか、また、それがとんでもなく間違った事態を引き起こしかねないことについて十分理解していない限り、すっかり混乱してしまうでしょう。 そこで、5種類のガベージコレクションアルゴリズムを持つおもちゃを作ってみました。小さいアニメーションはランタイムの動作から作成しました。もっと大きいアニメーションとそれを作成するコードは github.com/kenfox/gc-viz で見ることができます。単純なアニメーションによってこうした重要なアルゴリズムを明らかにできることは
Diffie-Hellman鍵交換アルゴリズム -今日の勉強会の補足- アリエルでは、毎週土曜日に勉強会をしています。 暗号化全般の話で、Diffie-Hellman鍵交換アルゴリズムの話がでたので補足資料です(*)。 公開鍵アルゴリズムの一種ですが、最も有名な(AirOneも利用している)RSAアルゴリズムとは少し趣が異なります。 RSAのように暗号化や署名を行うために鍵ペアを使うのではなく、共有鍵(セッション鍵)を生成/交換するために鍵ペアを使います。 IPsecや(トンネリングソフトの)zebedeeなどでも鍵交換に使っています。 2者間で秘密鍵(private-key)を隠したまま、セッション鍵を交換する手順は次のようになります。秘密鍵を知らない第三者はセッション鍵を知ることができません(=計算量が多くて求めるのに時間がかかります(**))。 + お互いの秘密鍵をxとyとします。
Thanks to Vijay D'Silva's brilliant answer in cstheory.stackexchange.com I have been reading some of the famous data structures and algorithms used in the Linux Kernel. And so can you. Linked lists, doubly linked lists, lock-free linked lists.B+ Trees with comments telling you what you can't find in the textbooks.Priority sorted lists used for mutexes, drivers, etc.Red-Black trees are used are use
SIG-AUDIO 2025 Vol.02 オンラインセミナー 「GDC2025 オーディオ報告会」SIG-Audio_GDC2024_報告会資料_増野さ...
内容に関する質問は [email protected] まで 第１回 プログラム高速化の基礎 東京大学情報基盤センター 片桐孝洋 1 ２０１３年度 計算科学技術特論A 本講義の位置づけ 2 ２０１３年度 計算科学技術特論A 講義日程と内容について ２０１３年度 計算科学技術特論Ａ（１学期：木曜3限 ） 第１回：プログラム高速化の基礎、2013年4月11日 イントロダクション、ループアンローリング、キャッシュブロック化、 数値計算ライブラリの利用、その他 第２回：MPIの基礎、2013年4月18日 並列処理の基礎、MPIインターフェース、MPI通信の種類、その他 第３回：OpenMPの基礎、2013年4月25日 OpenMPの基礎、利用方法、その他 第４回：Hybrid並列化技法(MPIとOpenMPの応用)
2012年01月23日19:30 カテゴリアルゴリズム百選iTech algorithm - JPEGminiの仕組みを推理する なぜコンピュータの画像は リアルに見えるのか 梅津信幸 JPEGの仕組みをおぼろげに知っている人ほど、むしろこれみて「ありえない」と思ったのではないのでしょうか。 JPEGmini - Your Photos on a Diet! でもよーく考えてみると、これでいけるという方法を発見というか再発見したので。 なぜJPEGminiがありえなさそうに見えるかは、以下に集約されます。 「なぜコンピュータの画像はリアルに見えるのか」 P.131 たとえば「ここは文字」「ここは背景の空」などと、ユーザーが自由に品質を設定できれば、さらによい画像になるはずです(できれば、それもコンピュータが自動で決めてくれるとうれしいのですが)。 同書も指摘しているように、JPEG 200
かつてのMac OS9までの描画エンジンの主役はQuickDrawが担っていた。GUIなOSでは、文字も含めてすべてをグラフィックとして扱うので、画面に見えているすべてのもの*1はQuickDrawによって描かれていたことになる。描画エンジンは、GUIなOS開発の要となる技術である。その出来が、GUIなOS開発の成否を分けるとも言える。 そして、最初期のQuickDrawは、ビル・アトキンソンがたった一人で開発したそうである。 当時（25年以上前）のCPUは、動作クロックが8MHzという性能だった。（現在は2GHz=2000MHzかつ、複数コアが当たり前） そのような性能であっても、違和感なくマウスで操作できるOS環境にするために、斬新な発想や試行錯誤を重ね、相当な努力の末に開発されたのがLisaやMacintoshであった。 Amazon.co.jp： レボリューション・イン・ザ・バレー
kazinaが作ってるWebサービスやソフトについての情報、プログラミングのメモなどをたまに。あとはAGAT18Kなどカメラやシルバーアクセ作りについて、映画についてなどなど駄文です。 画像の拡大縮小（リサンプリング Resamplling とも）アルゴリズムはPhotoshopがそうであるように、代表的なものが３つあります。 ニアレストネイバー法、バイリニア法、バイキュービック法です。普通はバイキュービック法で処理してしまえば特に問題ないんですが、バイキュービック法（バイリニア法も）は補間されてしまう為、ドット絵やアイコンなど、拡大時に元のドットをそのまま拡大したいような場合はニアレストネイバー法が適しています。 そもそも拡大時の補間はそこに本来無かったものを想像で作り出すということになるので、写実的というか、事実に忠実な拡大というのはニアレストネイバー法なんじゃないかという気がします。
07 Dec 2007 The Danger of Naïveté In my previous post on shuffling, I glossed over something very important. The very first thing that came to mind for a shuffle algorithm is this: for (int i = 0; i < cards.Length; i++) { int n = rand.Next(cards.Length); Swap(ref cards[i], ref cards[n]); } It's a nice, simple solution to the shuffling problem: Loop through each card in the deck. Swap the current c
ハフマン符号化法は文字だけで説明したので、この場で読むことが出来るようにいたします。 ファイル圧縮技術 －ハフマン符号化法の紹介－ LHAってソフト、知ってますよね。ファイル圧縮ソフトです。たとえばフロッピーディスク２枚分のデータを、フロッピーディスク１枚に納まるようにしてしまいます。 なぜそんなことができるのでしょうか。 LHA付属のドキュメント・ファイルを読んでみます。 吉崎 栄泰「ＬＨＡ取り扱い説明書」Ver.2.13 1991/07/20 NIFTY-Serve SDI00506 の 「0. はじめに」には >>アルゴリズムを動的ハフマン法から静的ハフマン法に変更したので、・・・・ という一文が書いてあります。 ハフマン法って何だろう。きっと、ものすごい数学的技術を使っているんだろうな・・・と思っていたときに、たまたま読んだのがＡ・Ｋ・デュードニー「チューリング・オムニバス 第１巻
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
CÉGEK, RENDEZVÉNYSZERVEZŐK, ÖNKORMÁNYZATOK! Szórakozási lehetőség gyermekeknek! Rendezvényekre, partikra rendelhetők, vagy bérbe vehető szórakoztató eszközök. Bővebb felvilágosításért kattintson a képekre vagy válasszon a lenti elérhetőségeink közül. További képek Bővebb szöveges cég és szolgáltatás tájékoztató ITT! Elérhetőségeink Telefonszám: +36-30/9659-614
高校生の時、数学の先生がこう言いました。 ゲームなんて、開発者が作ったルールの上で遊ばれるだけだ。 と。 その時、ゲーマーな自分はこう思いました。 ゲーマーは、開発者が作ったルールの上で遊ばれたい。 と。 というわけで、普段何気なくプレイしているゲームには、どのようなルール（アルゴリズム）があるのか。それを知るために、いろいろなゲームのアルゴリズムなどを解析しているページへのリンク集を作りました。 ほとんどのゲームのアルゴリズムは正式に発表されていないので、ユーザーの手による逆解析だったり、大学の研究による真面目な考察だったりします。（リンク先には、一部アルゴリズムと呼べないものも含まれています） 各種ゲームのプログラム解析 ドラクエ、FF、ロマサガのプログラム解析 DQ調査報告書（リンク切れ） ドラクエの物理ダメージ計算式は本質的にどれも同じだが、細かい部分で微妙に違う RPG INST
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
