fencepost error

名詞

[一般的]境界条件の離散版に関する問題で、しばしば反復ループのあるプログラムに現れる。次の問題に由来する。「10フィート間隔の柱で長さ100フィートのフェンスを作るとしたら、柱は何本必要か?」(明白な10本より、9本か11本のほうが良い答えだ)。たとえば、項目の長いリストや配列があって、m から n までの項目を処理したいとする。項目はいくつあるか?明白な答えは n - m だが、これは1つずれている。正しい答えは n - m + 1 だ。‘明白な’公式を使ったプログラムには、fencepost errorが含まれているだろう。zerothとoff-by-one errorも参照。そして、すべてのoff-by-one errorがfencepost errorというわけではないことに注意。椅子取りゲームには破滅的なoff-by-one errorが関わっており、N 人が N - 1 脚の椅子に座ろうとするが、これはfencepost errorではない。Fencepost errorは、ものとものの間の空間ではなくもの自体を数えること、あるいはその逆、あるいは一列の片端だけを数えるべきか両端を数えるべきかを考慮し忘れることから生じる。
[まれ]入力値の予想外の規則性によって引き起こされるエラーで、これは(たとえば)理論的には効率的な二分木やハッシュテーブルの実装を完全に妨げることがある。(ここでのエラーは、アルゴリズムの期待される振る舞いと最悪のケースの振る舞いとの違いに関わる。)