いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 62 unique paths

投稿日:

こんにちは

今回の学びは

dpはまずはサンプルを埋めてパターンをあぶりだす。そして言葉にして検証する

import遅いからパフォーマンス欲しい時は削げ

 

問題は。。。

(時間配分は5分問題理解 10分検討 10分実装  20分振り返り の一文45分構成)

まずは入出力をしっかりおさえましょう。

 

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析)は 

brute forceで O(2^(m+n))

dpでO(m+n)です

実際の実装はこちら

 

前回の問題といい今回の問題もすんなり解法にたどり着けたので

dpの基本がしっかり身についてきた

と実感しています

 

実装後です。timespace analysis (時間とスペースの分析)は 

brute forceで O(2^(m+n))

dpでO(m+n)です

 

パフォーマンスですが、下位10%と良くないです。ここで疑問です

 

 

非常にシンプルなdp実装でこの結果とは他の人はどのような実装で良い

パフォーマンスをたたきだしているのでしょうか?

ということですこしのぞいています。

 

たとえばこれ([Python3] Dynamic programming)上位25%です。でも回答ベースは私と全く同じです

    def uniquePaths(self, m: int, n: int) -> int:
        dp = [ [0 for _ in range(n)] for _ in range(m)]       
        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

 

細かいimportの違いが大きいのでしょうか?

実際import抜いて走らせましたらば、、、はい!!見事いきなり上位25%に入りました

つまりimport遅いからパフォーマンス欲しい時は削げ

という学びを得ました

 

後は数学てきなアプローチをしている人も!フィボナッチ的な匂いは私もわかりましたよ。でも実際つかって解法だしているのなると、だいぶ上手ですね。

こちらの方も同じdpの解法だけど初期化とか、無駄を極限削ぎ落としている回答です。ただしパファーマンスは上がっておりません。つまり初期化や私がやっているループ中のvalidation(if文と参照)くらいならパフォに影響なしということも分りました。でもこの辺ケースbyケースなので今回のこの一回の事象を信じるわけではないですが、参考までにのメモとしておきます。

 

まとめ

・dpはまずはサンプルを埋めてパターンをあぶりだす。そして言葉にして検証する

import遅いからパフォーマンス欲しい時は削げ

以上です

-アルゴリズム

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