こんにちは
今回の学びは
・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は９百万なのでまだいけるはずなのですが、 これは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に影響するという事実を突きつけられた結果となりました。
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
ソートしてポインターを当てる、合計からどっちをづらせばいいかわかるやん。
まとめ
・dictに数百万単位のデータ投入は数秒のコストと心得よ
・ポインターはどっちに動かせばいいかわかりやすい状況をつくろう。ソートとか。
以上です