いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 48 rotate image

投稿日:

こんにちは

今回の学びは

math.ceilの一行を辞めたら2倍の性能がでた

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の一行を辞めたら2倍の性能がでた

ということで。

 

まとめ

math.ceilの一行を辞めたら2倍の性能がでた

rotate imageの法則は覚えましょう。4つスワップの肝は左余白、右余白にあり!

 

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.