見出し画像

またまたバグ···独学コンピューターサイエンティスト p235のサンプルプログラム

🥚𝓗𝓊𝓂𝓅𝓉𝓎𝓓𝓊𝓂𝓅𝓉𝓎𐇬🐾時々にゃん!ฅ(^•ω•*^ฅ

またと言うか、またまた独学コンピューターサイエンティストのサンプルプログラムのバグをみつけました。

日経BP発行の「独学コンピューターサイエンティスト」 第２部 第１３章 p234~p237 では、技術面接で頻繁に登場する「２つの整数の和」(two sum) と呼ばれる課題を取り扱っています。

具体的な課題内容は次になります。以下は独学コンピューターサイエンティスト p234 からの引用です。

この2つの整数の和の課題では、ソートされていない整数のリストと目標値が1つ与えられます。リストから2つの数値を選び、その2つを足すと目標値になる組み合わせを探して、その2つの数値のインデックスを出力します。そのリストには正解となる組み合わせは1ペアしかなく、同じ要素を2回使ってはいけません。

この課題内容で正解となる組み合わせに付いて書かれた

そのリストには正解となる組み合わせは1ペアしかなく、同じ要素を2回使ってはいけません。

の箇所は、丁寧に説明すると次のようになります。

リストには正解となる組み合わせが1ペアしかない。この正解となる1ペアの組合せには、同じ要素を2回使ってはいけない。よって、正解となるペアの組み合わせは、必ず異なる2つの要素になる。つまり、同じ要素を2回使うと偶然目標値になる場合、その同じ要素を2回使用する組合わせは解答ではない。

そして、独学コンピューターサイエンティスト p235 には、この解答を返す2つの関数が提示されています。総当たりで答えを探す two_sum_brute と、辞書を使い答えを探す two_sum です。

以下が、独学コンピューターサイエンティスト p235 から引用した、この2つの関数です。どちらの関数も、最初の引数に整数のリスト、2番目の引数に目標値を受け取ります。そして、答えの2つのインデックス(数値)を返します。

def two_sum_brute(the_list, target):
    index_list = []
    for i in range(0, len(the_list)):
        for j in range(i, len(the_list)):
            if the_list[i] + the_list[j] == target:
                return i, j
def two_sum(a_list, target):
    a_dict = {}
    for index, n in enumerate(a_list):
        rem = target - n
        if rem in a_dict:
            return index, a_dict[rem]
        else:
            a_dict[n] = index


それでは、two_sum_brute関数を p235_1.py ファイルに、two_sum関数を p235_2.py ファイルに保存してテストします。以下が、そのテストプログラムです。

from p235_1 import two_sum_brute
from p235_2 import two_sum


testlist = [8, 1, 4, 5]
tgt = 6
print('リスト', testlist, '  目標値', tgt, '  [解答 1 と 3]')
print('two_sum_brute', two_sum_brute(testlist, tgt))
print('two_sum      ', two_sum(testlist, tgt), '\n')


testlist = [3, 1, 4, 5]
tgt = 6
print('リスト', testlist, '  目標値', tgt, '  [解答 1 と 3]')
print('two_sum_brute', two_sum_brute(testlist, tgt))
print('two_sum      ', two_sum(testlist, tgt), '\n')


testlist = [8, 3, 4, 3]
tgt = 6
print('リスト', testlist, '  目標値', tgt, '  [解答 1 と 3]')
print('two_sum_brute', two_sum_brute(testlist, tgt))
print('two_sum      ', two_sum(testlist, tgt))

以下は出力結果です。

リスト [8, 1, 4, 5]   目標値 6   [解答 1 と 3]
two_sum_brute (1, 3)
two_sum       (3, 1) 

リスト [3, 1, 4, 5]   目標値 6   [解答 1 と 3]
two_sum_brute (0, 0)
two_sum       (3, 1) 

リスト [8, 3, 4, 3]   目標値 6   [解答 1 と 3]
two_sum_brute (1, 1)
two_sum       (3, 1)

見ての通り、two_sum関数は全て正しい解答インデックスを返していますが、two_sum_brute関数は2番目と3番目のテストで間違った解答インデックスを返しています。

この two_sum_brute関数のバグの理由は、総当たりで答えを探す二重ループで同じ要素(インデックス)同士を比較して、同じ要素を2回使うと偶然目標値になる場合、その同じ要素同士を解答として返している為です。

ここで、仮に「同じ要素を2回使ってはいけません。」を、「ソートされていない整数のリストには、同じ要素を2回使って目標値になる要素を含んではいけません。」だと理解したから、僕の提出した解答プログラムは間違っていません。と言い訳する技術面接の受験者が現れたらどうなるでしょうか？

おそらく技術面接官は、こう言って、その言い訳を否定するでしょう。

「どう読んでも、そんな意味にはならない。」

「そもそも、それでは解答となる要素ペアの各数値は、必ず異なる数値にしなければいけなくなる。」

「つまり、目標値を6とした場合、[3, 5, 3, 8]のようなインデックス0とインデックス2の同じ数値3が解答になるリストは、課題の制約に違反している事になる。」

「そんな無意味な制限を付けた two sum 課題は聴いたことが無い。勿論そんな無意味な制限を付けた two sum 課題を技術面接の課題に出す企業も聴いたことがない。」

「その制約に意味があるとしたら、それは貴方のバグを隠すことだけだ。もうお引取りください。」

チャンチャン！

話がそれました。元に戻します。

それでは、乗りかかった船なので、two_sum_brute関数の良いデバッグと悪いデバッグの二通りのデバッグを示します。

なお、デバッグ例を示す前に、一つ説明しておかなければ行けないことがあります。two_sum_brute関数の最初の行の

index_list = []

は、全く意味がない無駄なステップです。バグではありませんが不要です。おそらくは、index_list に返り値を格納するつもりで、この一行を書いて、結果、index_list に返り値を格納しなかったにも関わらず、削除を忘れてしまいとり残された一行なのでしょう。無意味なので以下のデバッグ例では、この行をコメントアウトしています。

では、まずは良いデバッグから。

バグがある二重ループを、同じ要素(インデックス)同士は比較せず、且つ総当たりになるように修正するデバッグです。

以下がデバッグをした two_sum_br_D1関数です。

def two_sum_br_D1(the_list, target):  #  two_sum_brute デバッグ例１
#   index_list = []  //コメントアウト//
    for i in range(0, len(the_list) - 1):  # デバッグ修正
        for j in range(i + 1, len(the_list)):  # デバッグ修正
            if the_list[i] + the_list[j] == target:
                return i, j


それでは、two_sum_br_D1関数を p235_1_D1.py ファイルに保存してテストします。以下が、そのテストプログラムです。なお、テストデータは最初のテストプログラムと全く同じものを使用しています。

from p235_1_D1 import two_sum_br_D1
from p235_2 import two_sum


testlist = [8, 1, 4, 5]
tgt = 6
print('リスト', testlist, '  目標値', tgt, '  [解答 1 と 3]')
print('two_sum_br_D1', two_sum_br_D1(testlist, tgt))
print('two_sum      ', two_sum(testlist, tgt), '\n')


testlist = [3, 1, 4, 5]
tgt = 6
print('リスト', testlist, '  目標値', tgt, '  [解答 1 と 3]')
print('two_sum_br_D1', two_sum_br_D1(testlist, tgt))
print('two_sum      ', two_sum(testlist, tgt), '\n')


testlist = [8, 3, 4, 3]
tgt = 6
print('リスト', testlist, '  目標値', tgt, '  [解答 1 と 3]')
print('two_sum_br_D1', two_sum_br_D1(testlist, tgt))
print('two_sum      ', two_sum(testlist, tgt))

以下は出力結果です。

リスト [8, 1, 4, 5]   目標値 6   [解答 1 と 3]
two_sum_br_D1 (1, 3)
two_sum       (3, 1) 

リスト [3, 1, 4, 5]   目標値 6   [解答 1 と 3]
two_sum_br_D1 (1, 3)
two_sum       (3, 1) 

リスト [8, 3, 4, 3]   目標値 6   [解答 1 と 3]
two_sum_br_D1 (1, 3)
two_sum       (3, 1)

two_sum関数と同じく two_sum_br_D1関数も全て正しい解答インデックスを返しています。これがバグである同じ要素(インデックス)同士が当たるループを削り、必要なループのみを行うようにした良いデバッグです。


では、次は悪いデバッグです。

バグがある二重ループをそのまま残して、本来バグでは無い箇所に小手先の修正を加えるデバッグです。

以下がデバッグをした two_sum_br_D2関数です。

def two_sum_br_D2(the_list, target):  #  two_sum_brute デバッグ例２
#   index_list = []  //コメントアウト//
    for i in range(0, len(the_list)):
        for j in range(i, len(the_list)):
            if the_list[i] + the_list[j] == target and i != j:  # デバッグ修正
                return i, j


それでは、two_sum_br_D2関数を p235_1_D2.py ファイルに保存してテストします。以下が、そのテストプログラムです。なお、テストデータは最初のテストプログラムと全く同じものを使用しています。

from p235_1_D2 import two_sum_br_D2
from p235_2 import two_sum


testlist = [8, 1, 4, 5]
tgt = 6
print('リスト', testlist, '  目標値', tgt, '  [解答 1 と 3]')
print('two_sum_br_D2', two_sum_br_D2(testlist, tgt))
print('two_sum      ', two_sum(testlist, tgt), '\n')


testlist = [3, 1, 4, 5]
tgt = 6
print('リスト', testlist, '  目標値', tgt, '  [解答 1 と 3]')
print('two_sum_br_D2', two_sum_br_D2(testlist, tgt))
print('two_sum      ', two_sum(testlist, tgt), '\n')


testlist = [8, 3, 4, 3]
tgt = 6
print('リスト', testlist, '  目標値', tgt, '  [解答 1 と 3]')
print('two_sum_br_D2', two_sum_br_D2(testlist, tgt))
print('two_sum      ', two_sum(testlist, tgt))

以下は出力結果です。

リスト [8, 1, 4, 5]   目標値 6   [解答 1 と 3]
two_sum_br_D2 (1, 3)
two_sum       (3, 1) 

リスト [3, 1, 4, 5]   目標値 6   [解答 1 と 3]
two_sum_br_D2 (1, 3)
two_sum       (3, 1) 

リスト [8, 3, 4, 3]   目標値 6   [解答 1 と 3]
two_sum_br_D2 (1, 3)
two_sum       (3, 1)


two_sum関数と同じく two_sum_br_D2関数も全て正しい解答インデックスを返しています。

このデバッグでは、バグである同じ要素(インデックス)同士が当たるループをそのままにしているので、デバッグ後も完全に無駄なループをし続けます。そしてループ内で目標値条件にヒットした時に、同じ要素(インデックス)同士かチェックする無駄に無駄を重ねる悪いデバッグです。あえて言わせてもらえれば、このようなデバッグをする人は、プログラミング能力が低い可能性が高いので、企業はこのような安易なデバッグをする人をソフトウェア開発者として雇うと失敗するかもしれません。



後書き。。。

まだ、このバグがあるページまでしか読んでないけど、また少し読み進めたら新しいバグに出会うんだろうな。。。(汗)

独学コンピューターサイエンティストを、少し読んではバグにぶつかる経験を何度したことか···

あ〜もう、、ずんだもん を使った、独学コンピューターサイエンティストのバグ公開動画を作って、ユーチューブに上げようかなぁ？

最後まで読めば、１０本近い動画を作れそうな気がする〜(￣ー￣)ﾆﾔﾘ

それでは、またね ($・・)/~~~



#日経BP
#独学コンピューターサイエンティスト #レビュー
#独CS #selftaughtcoder
#清水川貴之 さん
#CoryAlthoff さん
#バグ #bug
#２つの整数の和
#twosum
#Python #Python3