プログラミングとデータ構造とアルゴリズムについて振り返る

プログラミング・データ構造・アルゴリズムについて,振り返ってみたいと思います.

Paiza

以前からPython3とアルゴリズム関連の練習のために,paizaラーニングとスキルチェック問題をぽちぽちやっていました.

Python3しかやってこなかったせいで他がスカスカですが,なんとかSランクマスターバッジと全ランクマスターバッジを取得することができました.

f:id:Szarny:20171003221055p:plain

プログラミングとデータ構造とアルゴリズム

競技プログラミング界隈ではスピードと書きやすさのバランスからC++が人気のようですが,1度Pythonに浸かってしまうと離れられなくなってしまいました.

ライブラリ云々の豊富さもありますが,基本的な構文がシンプルかつ書きやすいのが本当に気に入っています.

最初はアルゴリズムとデータ構造関連もペーペーでした.
連想配列って何?」「スタックって使い道あるの?」「再帰?統治分割法?」というくらいのペーペーでした.

でも,ぽちぽちCランク,Bランクと進むにつれて,どんな問題に対してどんなデータ構造やアルゴリズムが効いてくるのかが分かってくるようになりました.
「あのデータ構造ってこんな時にスパッとハマるのか」と気づけたときは本当に楽しいし快感です.

学んだこと

ここまでのまとめとして,プログラミング,またデータ構造とアルゴリズムについて,感じたことや学んだことをまとめておこうと思います.

的確なコメントを,適切な量だけ書くこと

プログラミング入門書の30ページあたりに書いてありそうな文言ですが,本当に大事です.

ある時はソースコードの内容を完璧に理解していたとしても,悲しいかな,人間である以上すぐに頭から抜け落ちてしまいます.

特に,つり橋を渡るかのように,脆くて線の細いギリギリの理解をつなげて完成させたプログラムなんてなおさらです.
下手すれば,目の焦点を離しただけで忘れていることだってあります.
もちろん,ソースコードを見た瞬間に理解できるようなプログラムが望ましいのは分かります.
しかし,現実はそう単純ではないのも確かです.

そのため,書きたてほやほやの自分のソースコードにらめっこして,少しでも思考が途切れそうだと感じたら,考え直してみること.
それでもダメなら,迷わずコメントを書くようにした方が良いと考えます.

それは,将来読み返すであろう自分のため,それを初めて読むことになるかもしれない誰かのためになると思います.

では自分の書いているソースコードは果たしてどうだろうか」と自問してみてください。果たして、自分自身を含め、人に「このプログラムにはこういう意味があり、こういうことをしています」ということが明確に伝わるものになっているでしょうか。

Peter Sommerlad 真実を語るはコードのみ
真実を語るはコードのみ | プログラマが知るべき97のこと

すべてのコメントを読む人にとって価値のあるものにし、そうでないものは即座に削除するか書き直すべきであるということです。

Kevlin Henney コードに書けないことのみをコメントにする
コードに書けないことのみをコメントにする | プログラマが知るべき97のこと

きちんと命名すること

これまたプログラミング入門書の50ページあたりに書いてありそうな文言ですが,これも大事です.

いわゆるループカウンタに使う変数ならicountでも良いかもしれませんが,中規模なプログラムになると,たちまち厄介なことになります.

つまり,「名前が衝突すること」「何のための変数だったかが分からなくなってしまうこと」という大きなリスクを孕むことになるのです.

変数や関数に対して命名するとき,一呼吸置く必要があると思います.
counterは何をカウントしているのか,listは何のリストなのか,pointerは何を指すポインタなのか,いずれもはっきりしません.

ある権限を持つユーザ数をカウントするカウンタならauthorized_user_counter,あるノードと連結しているノードの数をカウントするカウンタならconnected_node_counterといったように,変数それ自身がこちらにアピールしてくれるようにすることが重要だと考えます.

適切な名前をつけられると言うことは、その機能が正しく理解されて、設計されているということで、逆にふさわしい名前がつけられないということは、その機能が果たすべき役割を設計者自身も十分理解できていないということなのではないでしょうか。

Matz 名前重要
名前重要 | プログラマが知るべき97のこと

まとめること・抽象化すること

それまでバラバラに処理していたことの本質やパターンを抽出し,よりまとまったデータ構造(リスト,スタック, キュー, etc.)やアルゴリズム(関数化, 探索, etc)を考案する,また,既にあるプログラムをこう言った考えの下にリファクタリングするという意味です.

ごく基本的なことかもしれませんが,「どことどこが似ているのか」「一見バラバラのように見える仕組みの中にパターンが潜んでいないか」ということに常に気を配る必要があると思います.

まとめること・抽象化することの実例(探索アルゴリズム)

例えば,マス目状の二次元配列において,周囲全8方向を探索するアルゴリズムを考えます.
f:id:Szarny:20171003230244p:plain

つまり,こんなデータを作り出したいわけです.

(x, y) = (0, -1)
(x, y) = (1, -1)
(x, y) = (1, 0)
(x, y) = (1, 1)
(x, y) = (0, 1)
(x, y) = (-1, 1)
(x, y) = (-1, 0)
(x, y) = (-1, -1)
ごり押し法

何も考えずにコーディングを行うと,以下のようになります.

def print_coordinates(x, y):
    print("(x, y) = ({}, {})".format(x, y))
    return

current_x = 0
current_y = 0

# 上方向から時計回りに
print_coordinates(current_x, current_y-1)
print_coordinates(current_x+1, current_y-1)
print_coordinates(current_x+1, current_y)
print_coordinates(current_x+1, current_y+1)
print_coordinates(current_x, current_y+1)
print_coordinates(current_x-1, current_y+1)
print_coordinates(current_x-1, current_y)
print_coordinates(current_x-1, current_y-1)
パターンを見つける

ここでパターンが無いか考えます.
よく見ると,+1-1以外は全く差がないことがわかります.

ここで,「ループを使ってうまく表現できないか」「差分だけを抜き出したらいいのではないか」と考えられれば,以下のようなアルゴリズムが思いつきます.

def print_coordinates(x, y):
    print("(x, y) = ({}, {})".format(x, y))
    return

current_x = 0
current_y = 0

# 増分をくくりだしてリスト化
delta_x_list = [0, 1, 1, 1, 0, -1, -1, -1]
delta_y_list = [-1, -1, 0, 1, 1, 1, 0, -1]

# 繰り返しをループに
for dx, dy in zip(delta_x_list, delta_y_list):
    print_coordinates(current_x+dx, current_y+dy)
三角関数で探索?

たとえ期待した結果が得られるとしても,これは行き過ぎでしょう.

import math

def print_coordinates(x, y):
    print("(x, y) = ({}, {})".format(x, y))
    return

current_x = 0
current_y = 0

radian = 0
for i in range(8):
    print_coordinates(round(math.sin(radian)), -round(math.cos(radian)))
    radian += (math.pi / 4)

問題を見極めること・方針を立てること

Have you seen it before? Or have you seen the same problem in a slightly different form

Look at the unknown! And try to think of a familiar problem having the same or a similar unknown.

G.Polya How to Solve It

与えられた問題は何であるのか,どんなデータが分かっていて,何が分かっていないのかを明らかにする必要があります.

なぜなら,問題を理解しないことには,プログラムを組み立てられないからです.

個人的な意見ですが,プログラミングに関して「この問題が解けない」という時には,「どうすれば良いのか分からない」のではなくて「そもそも問題の意味が分からない」「何をすればいいのか分からない」という状況が多いように感じます.

そうして,問題を見極められたならば,「どのようなアルゴリズムやデータ構造がその問題に対して有効か」という方針を打ち立てる必要があります.
ここでは,過去に同じようなプログラムを組んだ覚えはないか,その時にどんな手法が有効だったのかに焦点を合わせる必要があります.

思い出せたのなら,それを使えば大丈夫でしょう.
一方で,思い出せなかった場合でも,「あのアルゴリズムは部分的に利用できるな」とか「この部分だけなら以前にやったことがある」というモノがあれば,解決の糸口を掴むことができるでしょう.
それがハッキリすればしめたもので,後はそれに沿って我慢強くコーディングしていけばよいだけです.

Here is a problem related to yours and solved before. Could you use it? Could you use its result? Could you use its method? Should you introduce some auxiliary element in order to make its use possible?

G.Polya How to Solve It

おわりに

プログラミング・データ構造・アルゴリズムについて,今までの経験をもとに振り返ってみました.
コメントや変数といった実用的なことから,パターンを発見したり問題を見極めたりといった抽象的なことまで,触れることができたかと思います.

もちろん,ここで書いたことはほんと一握りであり,内容も全く不十分だと思います.
自分自身,つい面倒になって適当な名前を付けたり,問題をよく理解しないままにコーディングを始めたり...といったことをついついしてしまいます.
これから様々な問題に直面する毎に,これらのことを思い出しながらコツコツ解いていけば,こういったことは自然に身に付くのではないかと思います.身に付けたいです.