きまぐれ日記: 動的配列への追加コストはなぜ 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
第8回 Unicodeからの多対一の変換［後編］ | gihyo.jp
前回は、WindowsにおいてWideCharToMultiByte APIを使用してUnicodeからShift_JISやISO-8859-1へ変換した場合に、WC_NO_BEST_FIT_CHARSというフラグを指定しなかった場合は「似ている文字への変換」が発生するため、セキュリティ上の問題が発生する可能性がある、という説明をしました。 今回は、実際にUnicodeから他の文字コードへの変換が、具体的に脆弱性を引き起こした例をいくつか紹介します。 電子メールの添付ファイル 電子メールの添付ファイル名には自由にUnicodeの文字が指定できますが、いくつかのメールクライアントにおいては添付ファイル名をUnicodeではなくShift_JISとして扱うために、問題が発生していました。 JVN#89344424: 複数のメールクライアントソフトにおける、添付ファイルによりメールクライアントソ
第7回 Unicodeからの多対一の変換［前編］ | gihyo.jp
文字コードが引き起こすセキュリティ上の問題として、もっとも興味深いもののひとつである、Unicodeから他の文字コードへの「多対一の変換」で引き起こされる問題点について、今回と次回で説明します。 ご存じのとおり、Unicodeには非常に多数の文字が収録されていますが（現在最新版のUnicode 5.1.0では100,713文字が収録されているそうです）、Unicodeから他の文字コードへの変換においては、互換性や可読性の維持のためか、複数のUnicodeの文字が他の文字コードでは単一の文字に変換されることがあります。 この「多対一」の変換が、開発者も想定していなかったような問題を引き起こす原因となることが多々あります。 具体的な例として、Windows上でのUnicodeからの変換について説明します。 Windows上でのUnicodeからShift_JISへの変換 Windows上で
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
