いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 15 3 sum

投稿日:

こんにちは

今回の学びは

dictに数百万単位のデータ投入は数秒のコストと心得よ

・ポインターはどっちに動かせばいいかわかりやすい状況をつくろう。ソートとか。

問題は。。。

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

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

 

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

pseudocode(擬似コード)をかいてみますか。

。。。

実際の実装はこちら

import sys
sys.setrecursionlimit(314159265)
from collections import defaultdict
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        memo = defaultdict(list)
        sz = len(nums)
        for i in range(sz):
            for j in range(i+1, sz):
                y = nums[i] + nums[j]
                memo[-y].append((i, j))
        ans = set()
        for i in range(sz):
            x = nums[i]
            if x in memo:
                for candidate in memo[x]:
                    if i not in candidate:
                        indice = list((nums[candidate[0]], nums[candidate[1]], x))
                        indice.sort()
                        ans.add(tuple(indice))
        return list(ans)

 


O(N^2)を思いつく、時間もすくないので面接菅にこれで実装してもよいか聞いて
から実装しはじめる
12分で実装して
さらに7分かけてデバッグしました。
最終的にはTLEでエラーとなりあした。自分の分析ではO(N^2)でこの問題なら通るとおもったのですが
https://leetcode.com/submissions/detail/270830314/
のNが3000のケースでTLEです。3000*3000は9百万なのでまだいけるはずなのですが、
これはtime complexity分析を見誤りましたか?!

以下サンプルケースをくづしていく様子です
samples = [
    #([-1, 0, 1, 2, -1, -4], [[-1, 0, 1], [-1, -1, 2]]),
    # 0830 failed 113/331 test case
    # [-4, 0, 4]がはいってきてない。。。
    # そうか。。合計が被っている時にオーバーライトしちゃってるんだ。
    ([-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6], []),
    # 0834 TLE 311 / 313 test cases passed.
    # https://leetcode.com/submissions/detail/270830314/
    # O(N^2)では足りないといこがわかりました。
    # ではここから10minかけて、さらにO(N)とかO(NlogN)とかもしくはO(N^2)-X にならないかみていきます。
    # 0837 10 min timer start till 0846

]
ここで時間が40ふんほど経過しましたので
答えを見ることにしました。


少々おまちください
https://www.techseries.dev/products/tech-interview-pro/categories/1408104/posts/4821258

ソートして、ソート特性をいかして探していく方法!
O(N * (n/2)) と O(NlogN) なので
結局 O(N^2)だけで少し早い!?アルゴリズムとなる。

ソートするとポインターをどっちに動かせばいいかわかりやすい
ポインターはどっちに動かせばいいかわかりやすい状況をつくろう。ソートとか。

space is O(1)
so , answer would be time O(N^2)

let's code it up

こちら新しい実装です。
やることがわかってしまえば実装は簡単でした。
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        sz = len(nums)
        ans = set()
        nums.sort()
        for i in range(sz-2):
            # having 2 pointer
            l = i + 1
            r = sz - 1
            while l < r:
                local = nums[i] + nums[l] + nums[r]
                #print("%s , %s, %s => %s as sum" % (i, l, r, local))
                if local == 0:
                    ans.add((nums[i], nums[l], nums[r]))
                    l += 1
                elif local > 0:
                    # should decrease in next round, so moveing r toward left r-=1
                    r -= 1
                else:
                    l += 1

        return list(ans)

 


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

O(N^2)で spaceはO(1)です

 

実際、通るソリューションが実装できたので、前の私のO(N^2)と信じていた実装の実行速度を比較しましたら、以下のように前回の実装は5倍も遅い!結果となりました。この結果からO(N^2)ではないはずだ!との仮説がたちます。

# 新しいポインターでの実装
elapsed: 0.9121770858764648
# 前のセットでの実装
elapsed: 4.646041631698608

 

さてどこがO(N^2)から外れる原因の箇所でしょうか?

まずは、TLEの実装をすこしづつ削ってどこがボトルネックかみてみたら。。。。

`#memo[-y].append((i, j))`

をコメントしただけで、実行速度が0.4になりもうした!!

class Solution_hashmap_way_but_TLE_in_311_outof_313:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        memo = defaultdict(list)
        sz = len(nums)
        for i in range(sz):
            for j in range(i+1, sz):
                y = nums[i] + nums[j]
                #memo[-y].append((i, j))
        ans = set()
        return list(ans)

 

むむ!?

defaultdictが遅いのか?だってappend自体は早いでしょう!?

ということで

memo = defaultdict(list)
sz = len(nums)
for i in range(sz):
    for j in range(i+1, sz):
        y = nums[i] + nums[j]
        memo[-y] = (i, j)

とするとまた4秒かかったよ!遅いよ〜

appendは悪くないので、defaultdictをやめてみた。

するとさらに遅くなり5.5秒もかかった。つまりdefaultdictもわるくない。

class Solution_hashmap_way_but_TLE_in_311_outof_313:
    @timeit
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        memo = {}
        sz = len(nums)
        for i in range(sz):
            for j in range(i+1, sz):
                y = nums[i] + nums[j]
                if -y in memo:
                    memo[-y].append((i, j))
                else:
                    memo[-y]= [(i, j)]

つまり

dictであるmemoに大量にデータを投入すること自体が悪、

なのである、space(O^2)になっているので、dictの実装的にも数回mallocとかやってると思うし、そういう要因での遅延とみた。

なので、dictに数百万単位のデータ投入は数秒のコストと心得よ

を教訓とします

 

つまりは私のtime complexity分析は合っていました。しかしならが大量データを扱う場合は、space complexityがtime complexityに影響するという事実を突きつけられた結果となりました。

参考:pythonで競技プログラミングをする際のチップ

 

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

ソートしてポインターを当てる、合計からどっちをづらせばいいかわかるやん。

 

まとめ

dictに数百万単位のデータ投入は数秒のコストと心得よ

・ポインターはどっちに動かせばいいかわかりやすい状況をつくろう。ソートとか。

以上です

-アルゴリズム

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