きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
Makefileの書き方 - スキルアップ輪講
makeって何？ † ソースファイルを分割して大規模なプログラムを作成していると、コマンドでコンパイルするのが面倒です。また、一部のソースファイルを書き換えただけなのに全部をコンパイルし直すのは時間の無駄です。 そんな問題を解決するのがmakeです。Makefileと呼ばれるテキストファイルに必要なファイルと各ファイルのコンパイルのコマンド、ファイル間の依存関係を記します。そして、“make”というコマンドを実行するだけで、自動的にコマンドを実行してコンパイルしてくれます。これだけではスクリプトと大差がないのですが、makeはMakefileに記された依存関係に基づいて更新されたファイルの内関連のあるものだけを更新することで、コンパイル時間を短くします。 makeは特定のプログラミング言語に依存したものではありません。C言語のソースファイルのコンパイルにも使えますし、Verilog-HDL
VC++の使い方 [VC++の使い方]
このページについて このページは、VC++ の使い方を中心にまとめようと思っていましたが、管理者がいろいろな知識をメモ的に詰め込む用途にも使われ始めました。どこにでもある内容よりも、どこにもない情報をまとめてみたり、散らばっている情報を集積することを目的としています。 今のところの目玉コンテンツは VC++の使い方 GUIのプログラミング IEコンポーネント といったところです。 サイトマップ このサイトについて VC.NET関係の資料 VS .NET 60日間限定評価版を斬る ソリューションとプロジェクト チュートリアル VC++入門 デバッグ入門 リファレンス Ｃ／Ｃ＋＋メモ ビルドエラー対処法 GUIリファレンス VC++ Tips エディタとVC++の大人な関係 CVSによるソース管理 IEコンポーネントの使い方 ウインドウ選択 インターフェース 時代はXML 軽い実行可能ファイル
高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」：CodeZine
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。rank(p, c)――T[0...p]中のcの出現回数を返すselect(i, c)――(i+1)番目のcの位置を返す WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。対象読者 C++の利用
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
API別 Win32 サンプル集
AllocConsole コンソールの割り当て AngleArc 円弧の描画 Arc 楕円の描画 ArcTo 楕円形の円弧の描画 AssignProcessToJobObject ジョブオブジェクトにプロセスを追加 BackupEventLog イベントログのバックアップ BeginPath パスの作成の開始 BitBlt グラフィックデバイス間のイメージの転送 BlockInput マウスやキーボード入力のブロック CancelWaitableTimer 待機可能タイマの無効化 ChangeClipboardChain クリップボードビューアの削除 Chord 弓形の図形の描画 ChrCmpI 文字の比較 ClearEventLog イベントログのクリア CloseClipboard クリップボードのクローズ CloseDesktop オープンされているデスクトップハンドルのクローズ C
C++ for Haskeller
http://haskell.g.hatena.ne.jp/mr_konn/20061006/1160138831 Haskellから入った人には、cinとかcoutとか微妙すぎてよくないだろ、と、思ったので、適当に。 対象読者は、Haskellわかるし、C++もわかる人（意味ねー）。ネタを理解できる人です。 C++とは C++とは、以下のような特徴を持ったプログラミング言語です 参照透明（！） 出現評価(occurrence evaluation) （などといういかがわしい単語をつくる） パターンマッチできる 全く直感的でない構文 IOモナドを書くための大量のsyntax sugarがある 説明していくと長くなるので、それぞれ、おいおい必要になったときに説明するようにします。 C++の型 C++には、次の型があります。 整数 真偽値 連想配列 まあ、おいおい説明。（はやくも飽きてきた）
手軽な低レベルプログラミング環境として GBA はもっと評価されるべき
とりあえず開発を始めるにあたっては特殊なハードウェアなどは必要なくて、 コンパイルは gcc テストはエミュレータの VisualBoyAdvance といった流れで開発を進めます。 最後の最後に実機確認をする段階になったら、ロムイメージを書き込んで GBA の実機で実行させるためのマジコンが必要になりますが 当面は必要ありません。 まず VisualBoyAdvance で動けば実機で動きますし、その逆も真です。 ちなみに「Linuxから目覚めるぼくらのゲームボーイ！」などで用いられている ブートケーブル経由での開発はハードウェア資源の制限がキツくなるのでオススメできません。 コンパイルについては gcc で OK で、これは devkitPro r18 (buildscripts 20060412) をインストールすれば一式入ります。 Windows, MacOSX, Linux など
工学ナビ
(08/09/28) すっかり活動のメインがブログのほうになっちゃいましたが，こっちもちゃんと管理していきたいと思います． 今のところ企んでる特集企画が４〜５つあるので，なんとか暇を作って書きたいと思います． さて，すでにご存知だとは思いますが，当サイトの人気記事であるARToolKit特集が本になりました． ARToolKitの導入部分についてはサイトの内容とかぶるところはありますが， VRMLの表示のさせ方や，表示領域を複数持つアプリケーションの作り方， OpenCVとの連携など，新しい情報をあれこれ詰め込んでいるので是非手にとってみてください． (07/06/01) 新しい特集記事を書きました！ 「攻殻機動隊」「電脳コイル」の世界を実現！ ARToolKitを使った拡張現実感プログラミング 今回は過去最高の執筆時間を要した，とても濃い内容になってます． (07/03/02
Boost C++ Libraries Document
ライブラリ . ドキュメント: 最新のリリース CVS(毎日更新) . ライセンス . Getting Started . 退行テスト: 一般的な情報 テスト結果 メーリングリストと ニュースグループ . Boost (Developers) . Boost Users . Project-Specific . Announcements . Discussion Policy サポート . FAQ . Request Support . Report Bugs . Suggest Features . Commercial Support . Also: Mailing Lists About . Formal Reviews . Review Schedule . Requirements . Guidelines . Submissions Other Resources . Fil
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
標準 Windows API - WisdomSoft
Efficient data transfer through zero copy
IBM メモリー管理の内側 - Japan
http://park16.wakwak.com/~mimi/dotnet/top.html