はじめに
paizaやAtCoderなどの競技プログラミングの問題で座標はよく出てきますし、将棋や囲碁などのボードゲームを作成するときや、エイトクイーン問題を解くときは必ず座標を使います。
この記事では、座標の多様な表現を紹介します。
よくある座標
以下の座標を二つのデータ構造で表現します。
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | a | b | c |
| 1 | d | e | f |
ここでは横に並ぶ番号をx, 縦に並ぶ番号をyとします。
伝統的二次元配列
>> point = [['a', 'b', 'c'], ['d', 'e', 'f']]
>> point[0][0]
'a'
>> point[1][2]
'f'
メリット
- 伝統的で、言語によらない記述。
- シンプル
デメリット
- よく混乱する。
((縦, 横)の順でアクセスするのは案外普通なのですが)
x と y を使う場合は(x, y)、つまり(横, 縦)と見たい感じはします。
ですが後述しますが、(y, x)は行の配列として見れますので捉え方としては自然です。(y, x)と見るのは少し混乱すると思いますがいずれ慣れます。
座標をハードコーディングするときは見栄えをよくしましょう。
point = [['a', 'b', 'c'], ['d', 'e', 'f']]
↓
point = [['a', 'b', 'c'],
['d', 'e', 'f']]
先ほども述べたように上記の例の解釈はいわば、行の配列です。
少し考えると、データを列の配列と解釈することも可能なことがわかります。
point = [['a', 'd'],
['b', 'e'],
['c', 'f']]
コーディング上ではわかりづらいですが、これで(x, y)というふうにアクセスできます。
point[2][0]
# 'c'
一般的なのはどちらか
行の配列、列の配列、それぞれに有用性がありますが、
一般的なのは、行の配列だと思います。
point = [['a', 'b', 'c'],
['d', 'e', 'f']]
Excelでの集計や、データベース操作のGUIクライアントアプリは行を下に向かって並べるように表示をしていることが多いです。
例: 行の配列
| id | name | age |
|---|---|---|
| 1 | python_man | 20 |
| 2 | python_girl | 18 |
ですので(y, x)と見るのは案外すぐ慣れると思います。
伝統的二次元配列はとにかくシンプルで、記述が簡単なやり方です。
組(タプル)に値を対応させる辞書型
オススメの方法です。どうしても(横, 縦)とアクセスしたいときはこのやり方でわかりやすくなります。
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | a | b | c |
| 1 | d | e | f |
eの場所はどのように表しますか。
横番号をx, 縦番号をy として、
(x, y) → 文字 というふうに考えてみてください。
...
(1, 1) → e
になるのかなと思います。
他のも表してみましょう。
(0, 0) → a
(2, 1) → f
はい、簡単です。
これが馴染むのであれば、これをそのまま辞書にしてしまいましょう。
>> point = {(0, 0): 'a', (1, 0): 'b', (2, 0): 'c',
(0, 1): 'd', (1, 1): 'e', (2, 1): 'f'}
見た目は悪いです。
ところで、アクセスはどうなるでしょう。
>> point[(2, 1)]
'f'
Pythonではしばしばタプルのかっこは省略できます。
>> point[2, 1]
'f'
結構直感的ではないですか?
私は思います。おすすめです。
これだけではないです。この表現は広く応用できます。
例えば添え字が整数以外だったらどうしますか？このやり方ではそのまま表現できます。
| A | B | C | |
|---|---|---|---|
| P | a | b | c |
| Q | d | e | f |
>> point = {('A', 'P'): 'a', ('B', 'P'): 'b', ('C', 'P'): 'c',
('A', 'Q'): 'd', ('B', 'Q'): 'e', ('C', 'Q'): 'f'}
>> point['C', 'P']
'c'
メリット
- アクセス方法が直感的。
- 数学っぽい。
デメリット
- 順序性はない。
- 馴染みづらい。
一次元に落とし込める座標
以下の座標を考えてみましょう。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 0 | * | * | ||||||
| 1 | * | * | ||||||
| 2 | * | * | ||||||
| 3 | * | * |
座標に何かがあるというパターンで、ある縦の列に要素が一つだけというパターンです。(将棋の二歩のような状況ではないというとわかりやすいでしょうか)
一意な対応
伝統的な二次元配列の表現では以下のようになりそうです。
ありがちな表現は、存在しないとき 0 とし、存在するとき 1 とする方法。False, Trueでも可能です。
point = [[0, 0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 1, 1, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0]]
悪くはないですが、
上の表は同じ縦の列に要素が一つだけ(縦の列に対して値が一意に定っている)なので、
次のように一次元配列で表すことが可能です。
point = [3, 3, 2, 2, 1, 1, 0, 0]
メモリ節約だけでなく、高速化にもなります。何かが存在するというような座標の場合は一次元配列にできないか考えてみましょう。
おわりに
今のところ私が出会った座標の表現は以上になります。
それぞれに有用性があると思いますので、場面で使い分けるのが良いと思います。
他にもこんな表現があるという方は是非コメントで教えてください。
おまけ: 組(タプル)から値への対応と行列
行列の厳密な定義(Wikipedia)
行列を集合を使って定義するとしたら以下のようになります。
行数を m、 列数を n とするとき、
$R = 1, ..., m$ と $C = 1, ..., n$ の直積集合 $R×C$ から、成分の属する体$F$への写像となります。
R×C \rightarrow F
添字を$i$, $j$ とすると成分$x$への対応は以下のようになります。
(i, j) \mapsto x
これはまさに紹介した通りの辞書型の形です。