こんにちは
今回の学びは
・math.ceilの一行を辞めたら２倍の性能がでた
・rotate imageの法則は覚えましょう。4つスワップの肝は左余白、右余白にあり！
問題は。。。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
これねー
問題の理解は簡単なんだが実装が難しいんだわ。
ゴリゴリ直球でやると必ずはまるね。
2month agoに解いているから、しかもそのときは解答見たはず。
で、
こんなパターンわかりっこねぇよ、と思ったののをおぼえていました。
今回はそれを思い出す作業に一時間かかりました。
こちらです
この最初、左上から初めて4つをスワップする。これって、なにかの式で
パターンかできないか？ってひたすら考える、という問題ですね。端的に行ってしまえば。
これを思いつくのすご〜く難しいです。
なんとなくパターンになってそう、というのは誰でもわかると思うですが
いざ式を建てるとなると超絶むずかしです。私の今回とったアプローチはとにかく小さいテストケースで
実際に文字に起こしてノートにかいて式を調整していきました
赤 -> 青 -> 緑の順に確認していっている様子が上のノートから読み取れるでしょうか。
目で見ていてパターン化できていると思ったら、それは必ず式に落とし込める！パターン化式が作れる。落ち着いてサンプルケースから構築せよ！
・rotate imageの法則は覚えましょう。4つスワップの肝は左余白、右余白にあり！
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は O(n)でございます
pseudocode（擬似コード）は上のノートのとおりです
実際の実装はこちら
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
length = len(matrix)
if length == 0: return matrix
#repeat = math.ceil(length/2) # ceilはずしただけで上位50%から一気に上位96%へ伸びたよ
repeat = length // 2 if length%2==0 else length // 2 + 1
for i in range(repeat):
sz = length - (i*2)
for n in range(sz-1):
j = i + n
print(i, j)
l = j - i
r = (i + sz) - j - 1
# swap
i_ = i+l
j_ = j+r
tmp2 = matrix[i_][j_] # O2
matrix[i_][j_] = matrix[i][j] # O2 <-- O1
i_ = i_+r
j_ = j_-l
tmp3 = matrix[i_][j_] # O3
matrix[i_][j_]= tmp2 # O3 <-- O2
i_ = i_-l
j_ = j_-r
tmp4 = matrix[i_][j_] # O4
matrix[i_][j_] = tmp3 # O4 <-- O3
matrix[i][j] = tmp4 # O1 <-- O4
一個パフォーマンスの改善点でよかったのは
#repeat = math.ceil(length/2) # ceilはずしただけで上位50%から一気に上位96%へ伸びたよ
math関数って遅いかもしれない
という、仮設ができました。ひとまず、
math.ceilの一行を辞めたら２倍の性能がでた
ということで。
まとめ
・math.ceilの一行を辞めたら２倍の性能がでた
・rotate imageの法則は覚えましょう。4つスワップの肝は左余白、右余白にあり！
以上です