2008.08.21
二分探索法
今回は、二分探索法について解説します。
1.逐次探索
通常、n個の配列(list)の中からある要素(target)を調べる場合、次のようにします。
for i in range(len(list)):
if i == target:
return i
return -1 #falseこれは逐次探索と 呼ばれます。(線形探索とも呼ばれ
る。)
この方法は単純ですが一般に、データ量に比例して作業量も増えてしまいます。
Home > 8 月, 2008
2008.08.08
C言語では、メモリはどうやって確保されている？
勉強会は週に1回開催していて、メイン担当は持ち回り制である。
で、このブログ記事を更新するのはメイン担当者の役割だ。
と、ルールを決めた本人が自分の当番を忘れてしまっていて「やべっ、示しがつかない…」と猛反省。
さて、今回はC言語で「変数はメモリ内にどうやって格納されていくのか」のお話。
深いところまで突っ込んでいこうと思ったのだが、文章化すると思ったより長くなってしまったので序論な感じではある。
C言語では、関数内のローカル変数は、関数を抜けると確保していたメモリ領域は開放される。
この時に使われるのはメモリ内の「スタック」と呼ばれる領域だ。
スタックというのは後入れ先出し方式で使われ、その名の通り、後に格納した値から先に使う（解放する）時に利用される領域である。
int a = 123;
int b = 987;
という宣言をしたとしよう。
メモリの下（番地が大きい方）から値が格納されていくので、下図のようなイメージとなる。
├────────┤
│ 987 │
├────────┤
│ 123 │
├────────┤
│ < 使用済領域 > │
└────────┘
2008.08.06
ごく当たり前…のハズ。（テスト仕様書）
さて今回は「テスト仕様書」について…
とは言え、制作歴が長い方にとっては「ごくごく当たり前」の話なんですが。
ただ制作歴の短い…特にWebCGI（特にPHP）しか業務経験が無い方だと、どうも「リリース後に不具合発覚→検証→修正→更新」が容易に可能な環境が多い所為か（Web以外だと納品後の修正は、かなり面倒なコトに…）この辺りに関する意識が甘い方を、これまで何名か見てきてたゆえの話だったりします。
とは言え、わざわざこんなトコを好んで見ている方にとっては、このような話をする必要は無いのかもしれませんがｗ
/////////////////////////////////////////////////////////////////////
さて、テスト仕様書を作り慣れてない方る際、最も頭を悩ませるのは「テスト項目の挙げ方」だと思います。
自分も昔「テスト項目1,000個挙げろ」と言われ、最初は200も挙げられなかったような気がします。orz…
というワケで基本的なテキスト入力１つで、ちょっと挙げてみますと―――
【よくある『名前（姓）』の場合】
- 初回表示時、初期値が空白になっているか
- 半角カナを入れてsubmit
- 半角「￥」を入れてsubmit
- 半角ダブルクォートを入れてsubmit
- 半角シングルクォートを入れてsubmit
- 機種依存文字を入れてsubmit
- shift_jis固有で化ける文字を入れてsubmit
- HTMLタグを入れてsubmit
- JavaScriptを入れてsubmit
- 大量（仕様依存）の文字数を入れてsubmit
- 空入力でsubmit
- エラー判定条件にかかって戻ってきた場合の初期値
などなど。
まぁ、もう少し「半角記号」を細分化するだけでも、まだまだテキスト入力１個で項目の数は増えるワケで。とは言え内容を見ると幾つか―――
そんなの当たり前じゃないか。確認するまでも無い。
と思われる内容も含まれています。もしくは「項目数稼ぎでは？」と思われるかもしれません。でも、自分は「それでいい」と思ってます。
テスト仕様書自体は「試験の手順，実施内容」を記述するものですが、「その実施結果」と言うのは―――
ここに記述されている挙動については確認しました。間違いありません。
という証明の集まりです。ゆえに、その実施内容が―――
そこで何か起こるなど絶対あり得ない
ものであったとしてもず「本当に実施した」のであれば、各々の項目が被っていない限り、その数もまた説得力だと考えております。
だって―――
あり得ないと思っていたことが起こった
なんて、プログラマ稼業では日常茶飯事だと思いませんか？（笑）
/////////////////////////////////////////////////////////////////////
以上、本当に「ごくごく当たり前」のコトなんですけども―――
先日、一躍話題になった某サイト（判らなければぐぐれｗ）が、XSS（クロスサイトスクリプティング）にやられて騒ぎになり、
作者が謝罪…というニュース（事故？）がありました。
ちなみに記事を見る限りでは、ほんの１行で回避できたと予想される内容だったりします。
※まぁ「数時間で作成」と謳っているゆえ、事細かなテストまでは行なえていなかったのも無理はありませんが。
とはいえ、作った人は他の某サイト（判らなければぐぐれｗ）の作者であり、制作者としては相応な実績を積んでらっしゃるワケですが…やはり人間足る者、どうやっても「うっかり」ってのは少なからず存在するモノでして。どれだけ経験を積んだプログラマでも余程小規模でもない限り、イキナリ一発で「全くバグが存在しない」システムなんて作れないモノです。（むしろ経験を積んでいる方の方が、この辺りは痛感されているかと）
とは言え、スケジュールの都合上「メイン部分の実装」以外はどうしても意識が薄くなりがちです。
ただ「テストする手間」と「何か問題が起きた時に発生する対処」
この２つのトレードオフについて、頭の片隅に置いてみては如何でしょうか。
