![見出し画像](https://assets.st-note.com/production/uploads/images/95604658/rectangle_large_type_2_c65f6e5d48dd68a64de25e6cb2eb1121.jpeg?width=1200)
間違いあり! 独学コンピューターサイエンティスト 第1部 第4章 p95 の指摘について
以下のツイートは、独学コンピューターサイエンティスト監訳者の清水川貴之さんへ向けてのものです。
清水川貴之 @shimizukawa さんへ
— にゃん! ฅ(^ •ω•*^ฅ @ Pythonと Kotlin を勉強してまふ。。。 (@rx_f00) January 8, 2023
時間が無くて斜め読みしかしてないので間違っていたらすいません🙇🏻
p95の right_i は right の長さよりも長いため、
は
right_i は right の長さと同じため、
だと思います。#独学コンピューターサイエンティスト#独CS #selftaughtcoder#Python #Python3
ケツカッチンで、急いで斜め読みしてる途中で見つけたものなので、検証してみました。
検証の為に、p87 のマージソートサンプルプログラム の一部を変更しました。指摘した部分の各値とマージソート関数を呼び出す箇所を追加しています。
以下が、その変更を加えたサンプルプログラムと出力結果です。
def merge_sort(a_list):
if len(a_list) > 1:
mid = len(a_list) // 2
left = a_list[:mid] # 修正前: left_half
right = a_list[mid:] # 修正前: right_half
merge_sort(left)
merge_sort(right)
left_i = 0 # 修正前: left_ind
right_i = 0 # 修正前: right_ind
alist_i = 0 # 修正前: alias_ind
while (
left_i < len(left) and
right_i < len(right)
):
if left[left_i] <= right[right_i]:
a_list[alist_i] = left[left_i]
left_i += 1
else:
a_list[alist_i] = right[right_i]
right_i += 1
alist_i += 1
# 検証の為、以下の print文を追加!
print(' while ( left_i < len(left) and right_i < len(right): ループ後の値!')
print(' left_i =', left_i, ' len(left) =', len(left),
' left_i が len(left) より大きくなることはない')
print(' right_i =', right_i, ' len(right) =', len(right),
' right_i が len(right) より大きくなることはない', end='\n\n')
while left_i < len(left):
a_list[alist_i] = left[left_i]
left_i += 1
alist_i += 1
while right_i < len(right):
a_list[alist_i] = right[right_i]
right_i += 1
alist_i += 1
return a_list
# merge_sort関数を実行するために以下を追加!
list = [6, 3, 9, 4, 1, 10, 3] # ソートされるリスト
print('ソート結果!', list, '=>', merge_sort(list[:]))
出力結果
while ( left_i < len(left) and right_i < len(right): ループ後の値!
left_i = 1 len(left) = 1 left_i が len(left) より大きくなることはない
right_i = 0 len(right) = 1 right_i が len(right) より大きくなることはない
while ( left_i < len(left) and right_i < len(right): ループ後の値!
left_i = 1 len(left) = 1 left_i が len(left) より大きくなることはない
right_i = 1 len(right) = 2 right_i が len(right) より大きくなることはない
while ( left_i < len(left) and right_i < len(right): ループ後の値!
left_i = 0 len(left) = 1 left_i が len(left) より大きくなることはない
right_i = 1 len(right) = 1 right_i が len(right) より大きくなることはない
while ( left_i < len(left) and right_i < len(right): ループ後の値!
left_i = 0 len(left) = 1 left_i が len(left) より大きくなることはない
right_i = 1 len(right) = 1 right_i が len(right) より大きくなることはない
while ( left_i < len(left) and right_i < len(right): ループ後の値!
left_i = 2 len(left) = 2 left_i が len(left) より大きくなることはない
right_i = 1 len(right) = 2 right_i が len(right) より大きくなることはない
while ( left_i < len(left) and right_i < len(right): ループ後の値!
left_i = 3 len(left) = 3 left_i が len(left) より大きくなることはない
right_i = 3 len(right) = 4 right_i が len(right) より大きくなることはない
ソート結果! [6, 3, 9, 4, 1, 10, 3] => [1, 3, 3, 4, 6, 9, 10]
出力結果から分かるように、left_i と len(left) が同じか、 もしくは right_i と len(right) が同じ時に、whileループを抜けています。
指摘させてもらった事は間違っていませんでした。
実は、この指摘をさせてもらった後に、このサンプルマージソート関数は、全ての whileループ判定の < を != に置き換えても問題ない気がしたので、全ての < を != を置き換えてみました。
以下が、その < を != 置き換えたプログラムの note 記事です。
後、これは重箱の隅をつつくような事なので報告しませんでしたが、p95 の、
次に、left_i は left の長さより短いので、
は、
次に、left_i は left の長さより小さいので、
の方が適切でしょう。left_i はインデックスを表す整数なので・・・
𝑷𝑺
2023-01-19 現在、この間違いは正誤表に載っていません。しかし、この間違いの確認をしていただける事が分かりました。
以下は、その確認が取れた清水川貴之さんのツイートです。
無視しているわけではなく、確認の時間が取れていません。
— Takayuki Shimizukawa (@shimizukawa) January 16, 2023
[追記]
対応していただきました。
ありがとうございます。「よりも長い」は間違いですね。
— Takayuki Shimizukawa (@shimizukawa) January 19, 2023
コード right_i < len(right) を満たさないので、「right_i は right の長さ以上のため」とするのがよさそうです。正誤表に追加しました。https://t.co/cjpbjUSwFo
#独学コンピューターサイエンティスト
#独CS #selftaughtcoder
#Python #Python3
#マージソート
#サンプルプログラム
#清水川貴之 さん