Pythonで世界で闘うプログラミング力を鍛える[chap02]
前回kigeso.hatenablog.com
の続きです。
今回は連結リストを扱うということでしたので、はじめに簡単に実装したリストを全ての問題で使用しています。
連結リスト [lib2.py]
from random import randint class MyCell: # シンプルな連結リストを実装しました # initCell関数で初期化できます # printCell関数でリストの要素を表示できます def __init__(self, data=None): self.data = data self.next = None # # MyCellを初期化 # def initCell(x=10): head = MyCell() if type(x) == int: n = head n.data = randint(1, 10) for _ in range(x-1): n.next = MyCell(randint(1, 10)) n = n.next elif type(x) == list: n = head n.data = x[0] for i in x[1:]: n.next = MyCell(i) n = n.next else: return None return head # # MyCellの中身を表示 # def printCell(head, N=None): cnt = 1 n = head while 1: print(n.data, end='') if n.next != None and (N == None or cnt < N): print('->', end='') else: print() break n = n.next cnt += 1 return
重複要素の削除
from lib2 import * # # O(n) 追加領域あり # def delete_duplicate(head): element = set() n = head pre = None while n != None: if n.data in element: pre.next = n.next else: element.add(n.data) pre = n n = n.next # # O(n^2) 追加領域なし # def delete_duplicate2(head): n = head while n.next != None: now = n while now.next != None: if n.data == now.next.data: now.next = now.next.next else: now = now.next n = n.next if __name__ == '__main__': l = [7,8,6,6,7,2,10,2,2] head = initCell(l) print('入力') printCell(head) delete_duplicate(head) printCell(head) head = initCell(l) print('入力') printCell(head) delete_duplicate2(head) printCell(head)
後ろからK番目を返す
from lib2 import * def Kth_from_back(head, k=3): n = head cnt = 0 while n.next != None: cnt += 1 n = n.next if cnt == k-1: break if n == None: print('False') return m = head while n.next != None: m = m.next n = n.next print(m.data) return if __name__ == '__main__': head = initCell() print('入力') printCell(head) Kth_from_back(head, k=5)
間の要素を削除
from lib2 import * def delete_element(node): n = node if n.next == None: node = None else: n.data = n.next.data n.next = n.next.next if __name__ == '__main__': head = initCell() print('入力') printCell(head) k = 5 print(k) node = head cnt = 0 while node.next != None: cnt += 1 if cnt == k: break node = node.next delete_element(node) printCell(head)
リストの分割
from lib2 import * # このコードはkより小さいものと大きいものの中間ノードを記憶している # けど、リストのheadとtailを使った方が簡単だ def divide_list(head, k): n = head out = MyCell() x_node = None #kより小さい値の中で最も後ろのノード while n != None: if x_node == None: # まだ値が入っていない if out.data == None: out.data = n.data # まだk未満の値が入っていない else: tmp = MyCell(n.data) tmp.next = out out = tmp if n.data < k: x_node = out else: # kより小さければ先頭に加える if n.data < k: tmp = MyCell(n.data) tmp.next = out out = tmp # kより大きければx_nodeの後に加える else: tmp = MyCell(n.data) tmp.next = x_node.next x_node.next = tmp n = n.next return out if __name__ == '__main__': head = initCell([3, 5, 8, 5, 10, 2, 1]) print('入力') printCell(head) k = 5 head = divide_list(head, k) printCell(head)
リストで表された2数の和
from lib2 import * # 最後の桁上がりに注意 # 例：5->5 と 5->4 を足すと、0->0->1となるように def list_sum(l1, l2): if l1 == None or l2 == None: return None n1, n2 = l1, l2 flg = False out = MyCell() tail = out while n1 != None or n2 != None or flg: num1 = n1.data if n1 != None else 0 num2 = n2.data if n2 != None else 0 ssum = num1+num2+int(flg) tail.next = MyCell(ssum%10) tail = tail.next flg = ssum >= 10 n1 = n1.next if n1 != None else None n2 = n2.next if n2 != None else None return out.next if __name__ == '__main__': list1 = initCell([7, 1, 6]) list2 = initCell([5, 9, 3]) print('list1') printCell(list1) print('list2') printCell(list2) print('ans') printCell(list_sum(list1, list2))
回文
from lib2 import * def is_palindrome(head): n = head reverse = MyCell() while n != None: reverse.data = n.data tmp = MyCell() tmp.next = reverse reverse = tmp n = n.next printCell(reverse.next) n = head r = reverse.next while n != None or r != None: if n != None and r == None: return False elif n == None and r != None: return False elif n.data != r.data: return False else: n = n.next r = r.next continue return True if __name__ == '__main__': head = initCell([1, 2, 3, 4, 5, 4, 3, 2, 1]) print('入力') printCell(head) print(is_palindrome(head))
共通するノード
from lib2 import * import random def make_common_list(): common = initCell(random.randrange(3, 10)) h1, h2 = initCell(random.randrange(3, 10)), initCell(random.randrange(3, 10)) n1, n2 = h1, h2 while n1 != None: if n1.next == None: n1.next = common break else: n1 = n1.next while n2 != None: if n2.next == None: n2.next = common break else: n2 = n2.next return h1, h2 # 判定のみ def is_common_list(h1, h2): end1, end2 = h1, h2 while end1.next != None: end1 = end1.next while end2.next != None: end2 = end2.next if end1 == end2: return True return False # 共通のノードを返す def is_common_list2(h1, h2): end1, end2 = h1, h2 len1 = 1 while end1.next != None: len1 += 1 end1 = end1.next len2 = 1 while end2.next != None: len2 += 1 end2 = end2.next if end1 != end2: return False n1, n2 = h1, h2 if len1 < len2: len1, len2 = len2, len1 n1, n2 = n2, n1 for _ in range(len1-len2): n1 = n1.next while 1: if n1 == n2: return n1 else: n1 = n1.next n2 = n2.next return False if __name__ == '__main__': h1, h2 = make_common_list() printCell(h1) printCell(h2) print(is_common_list(h1, h2)) printCell(is_common_list2(h1, h2))
ループの検出
from lib2 import * import random def make_roop_list(): h1 = initCell(random.randrange(3, 10)) h2 = initCell(random.randrange(3, 10)) n1, n2 = h1, h2 while 1: if n1.next == None: n1.next = h2 break else: n1 = n1.next while 1: if n2.next == None: n2.next = h2 break else: n2 = n2.next return h1 # フロイドの循環検出アルゴリズムっていう名前らしい def find_roop_head(n): head = n slow, fast = head, head while 1: if slow.next != None: slow = slow.next else: return False if fast.next != None: if fast.next.next != None: fast = fast.next.next else: return else: return False if slow == fast: break slow = head while 1: if slow == fast: return slow if slow.next != None: slow = slow.next else: return False if fast.next != None: fast = fast.next else: return False return False if __name__ == '__main__': n = make_roop_list() printCell(n, N=20) printCell(find_roop_head(n), 15)
Pythonで世界で闘うプログラミング力を鍛える[chap01]
大学生です。
「世界で闘うプログラミング力を鍛える本」を進めていこうかと思います。
技術力がなく、どこにも就職ができないと思ったのでプログラミングを勉強して行こうかと思います。特にGAFAに入りたいという気持ちがあるわけではありませんが、GAFAを狙うような人が使っている本だと思うとやる気が出てくるのでこの本がいいと思いました。ただ問題を解くのではなくブログにプログラムをあげることで、他人に見られるかもというプレッシャーを少しでも感じながらやって行こうと思います。
今回はChapter1[配列と文字列]をやっていきます。
ちなみに、公式（？）の答えはここにあります。
1.1 重複のない文字列
# O(n) def is_unique(st): # アスキーのとき if len(st) > 128: return False char_set = set() for s in st: if s not in char_set: char_set.add(s) else: return False return True # O(n^2) 追加メモリなし def is_unique2(st): # アスキーのとき if len(st) > 128: return False for i in range(len(st)-1): for j in range(i+1, len(st)): if st[i] == st[j]: return False return True if __name__ == "__main__": print('aiueo', is_unique('aiueo')) print('aiuea', is_unique('aiuea'))
1.2 順列チェック
# O(n) def is_reordering(st1, st2): if len(st1) != len(st2): return False char_dic = {} for s in st1: if s in char_dic: char_dic[s] += 1 else: char_dic[s] = 1 for s in st2: if s not in char_dic: return False else: if char_dic[s] < 1: return False else: char_dic[s] -= 1 return True # O(nlogn) 追加メモリなし def is_reordering2(st1, st2): if len(st1) != len(st2): return False else: return sorted(st1) == sorted(st2) if __name__ == "__main__": print('abecd', 'edcba', is_reordering('abecd', 'edcba'), is_reordering2('abecd', 'edcba')) print('abecdf', 'edcba', is_reordering('abecdf', 'edcba'), is_reordering2('abecdf', 'edcba')) print('abecd', 'edcbf', is_reordering('abecd', 'edcbf'), is_reordering2('abecd', 'edcbf')) print('abecd', 'abecd', is_reordering('abecd', 'abecd'), is_reordering2('abecd', 'abecd'))
1.3 URLify
def urlify(lst, n): space_count = 0 for s in lst: if s == ' ': space_count += 1 lst += list(' ' * (space_count*2)) idx = n + space_count*2 - 1 for i in reversed(range(n)): if lst[i] == ' ': lst[idx-2:idx+1] = list('%20') idx -= 2 else: lst[idx] = lst[i] idx -= 1 return lst def print_lst(lst): print(''.join(lst)) return if __name__ == "__main__": lst = list('fdaf fdafdas fafdkjk') print_lst(lst) print_lst(urlify(lst, len(lst)))
1.4 回文の順列
from collections import Counter from collections import defaultdict # O(n) def is_palindrome(st): st = st.lower() char_dic = Counter() for s in st: if 'a' <= s <= 'z': continue char_dic[s] += 1 flg = False for v in char_dic.values(): if v % 2 != 0: if flg: return False else: flg = True return True # O(n) def is_palindrome2(st): st = st.lower() char_dic = Counter() odd_cnt = 0 for s in st: if 'a' <= s <= 'z': continue char_dic[s] += 1 if char_dic[s] % 2 != 1: odd_cnt += 1 else: odd_cnt -= 1 return odd_cnt <= 1 if __name__ == "__main__": print(is_palindrome('Tact Coa')) print(is_palindrome2('Tact Coa'))
1.5 一発変換
def is_edit(str1, str2): cnt = 0 for s1, s2 in zip(str1, str2): if s1 != s2: cnt += 1 if cnt > 1: return False return True def is_add(str1, str2): if len(str1) > len(str2): return False cnt = 0 idx = 0 for i in range(len(str1)): if str1[i] != str2[idx]: idx += 1 if (idx-i) > 1: return False idx += 1 return True def is_one_operation(str1, str2): if abs(len(str1)-len(str2)) > 1: return False elif str1 == str2: return True elif len(str1) == len(str2): return is_edit(str1, str2) else: return is_add(str1, str2) or is_add(str2, str1) if __name__ == "__main__": str1 = 'pale' str2 = 'pal' print(str1, str2, is_one_operation(str1, str2))
1.6 文字列圧縮
# Bad 文字列の連結には O(n^2) def compress(st): new = st[0] pre = st[0] cnt = 1 for c in st[1:]: if pre == c: cnt += 1 else: new += str(cnt)+c cnt = 1 pre = c new += str(cnt) return new if len(st)>len(new) else st def compress2(st): cnt = 0 new = list() for i in range(len(st)): cnt += 1 if i+1 >= len(st) or st[i]!=st[i+1]: new.append(st[i]) new.append(str(cnt)) cnt = 0 return ''.join(new) if len(st)>len(new) else st if __name__ == '__main__': print(compress('aabcccccaaa')) print(compress2('aabcccccaaa')) print(compress('abcdefefefff')) print(compress2('abcdefefefff'))
1.7 行列の回転
# 計算量O(n^2) 追加領域O(n^2) def rotate_matrix(mat): col = len(mat) row = col new = [[-1]*row for _ in range(col)] for i in range(col): for j in range(row): new[i][j] = mat[col-1-j][i] return new # 計算量O(n^2) 追加領域O(1) def rotate_matrix2(mat): col = len(mat) row = col for i in range(int(col/2)): for j in range(i, row-1-i): tmp = mat[i][j] mat[i][j] = mat[col-j-1][i] mat[col-j-1][i] = mat[col-i-1][row-j-1] mat[col-i-1][row-j-1] = mat[j][row-i-1] mat[j][row-i-1] = tmp def print_matrix(mat): for i in range(len(mat)): print(mat[i]) print() if __name__ == '__main__': n = 8 mat = [[n*i+j for j in range(n)] for i in range(n)] print_matrix(mat) new = rotate_matrix(mat) print_matrix(new) rotate_matrix2(mat) print_matrix(mat)
1.8 ゼロの行列
# 計算量O(mn) 追加領域O(mn) def zero_padding(mat): f_row = set() f_col = set() for i in range(len(mat)): for j in range(len(mat[0])): if mat[i][j] == 0: f_col.add(i) f_row.add(j) for i in range(len(mat)): for j in range(len(mat[0])): if i in f_col or j in f_row: mat[i][j] = 0 # 計算量O(mn) def zero_padding2(mat): row_has0 = False col_has0 = False if 0 in mat[0]: row_has0 = True if 0 in [m[0] for m in mat]: col_has0 = True for i in range(1, len(mat)): for j in range(1, len(mat[0])): if mat[i][j] == 0: mat[i][0] = 0 mat[0][j] = 0 for i in range(1, len(mat)): for j in range(1, len(mat[0])): if mat[i][0]==0 or mat[0][j]==0: mat[i][j] = 0 if row_has0: for j in range(len(mat[0])): mat[0][j] = 0 if col_has0: for i in range(len(mat)): mat[i][0] = 0 def print_matrix(mat): for i in range(len(mat)): print(mat[i]) print() if __name__ == '__main__': mat = [[1, 4, 0, 3], [2, 4, 2, 1], [1, 4, 5, 3]] print_matrix(mat) zero_padding(mat) print_matrix(mat) mat = [[1, 4, 0, 3], [2, 4, 2, 1], [1, 4, 5, 3]] zero_padding2(mat) print_matrix(mat)
1.9 文字列の回転
def is_rotate(st1, st2): if len(st1) != len(st2): return False return st1 in st2*2 if __name__ == '__main__': st1 = 'waterbottle' st2 = 'erbottlewat' print(st1, st2, is_rotate(st1, st2)) st1 = 'raspberrypi' st2 = 'berrypirass' print(st1, st2, is_rotate(st1, st2))
Google Colab でモデルを学習する際のメモ
最近、Google Colabでちょっと重いモデルの学習を行った。
その際に、気になった点がいくつかあったのでメモ。
Colabではモデルの学習時間の比較を行っていけないと思った2つの理由。
（対処法がわかる方は教えていただけると嬉しいです）
90分問題
問題
Colabの有名な特徴の1つ目である、90分問題です。
実行中のノートブックに90分間アクセスしないと、セッションが切れてしまいます。
だからといって、いちいち手動でアクセスするのはめんどくさいですね。。。
対処法
こちらの方のコードを参考にしました。
60分に1回、コピペしたURLに飛んでくれるので、途中でセッションが切れることはありません。
ただし、パソコンの電源はきるわけにはいかないのが悲しいですね。
12時間問題
問題
Colabの有名な特徴の2つ目である、12時間問題です。
90分問題を対処しても、最大12時間でプログラムの実行は止まります。
ここに以下のように書いてありました。
ノートブックは、最大存続期間が最長 12 時間の仮想マシンに接続することで実行されます。
これは僕の実体験ですが、12時間も動いたことがないです。
もしかしたら僕のミスなのかもしれませんが、最短3時間弱で実行が終わっていました。
ちょっと大変なモデルを学習させているときは、最大でも7時間弱しか連続で計算できませんでした。
なので、正直僕は12時間という制限を疑っています。
（単に僕が使いすぎで、制限がきついのか、GPUだからか、わかんないな）
あと、12時間問題で実行が終わったあとは、数時間の使用制限があります（GPUだけかも）
あれ、急にプログラムの実行が終わるってことは学習していたモデルも全部パーになっちゃう？！？！
対処法
ちょこちょこモデルを保存しましょう。
なんと！ColabからGoogle Driveにアクセスできます。
そこで、1エポックごと等のタイミングでモデルを自分のGoogle Driveに保存することをオススメします。
続きから学習を行うときは、保存したモデルをロードすれば解決します。
GPU2つまで問題
そこまで知られていない問題だと思います。
これは、いくつかのモデルを動かしたい人だけが困っちゃう問題なのですが、
GPUを使って3つのノートブックを実行しようとすると、3つ目が実行されません。
使いすぎって怒られちゃいます。
対策はないです。（たぶん）
Proに課金したらいけるんかな。
2つまでで我慢しましょう。
GPUの種類問題
問題
Colabで使用できるGPUは4種類あります。
と、上のサイトにも書いてあります。
しかし、これらを選択する権利はユーザには与えられません。
対処法
僕らユーザができるのは、「!nvidia-smi -L」とうって、GPUを確認することのみです。
学習時間を測りたいなどの人はこのコマンドでGPUを確認することをオススメします。
しかし、Colabでモデルごとの学習時間を比較することはオススメできません。
GPUを統一したとしても、です。
理由は次の章です。
メモリの量問題
この問題はあまり見たことがなく、
正直、メモリが問題なのかどうかはわかってないのですが、、、
先日、Colabでいくつかのモデルを学習させていたのですが、
同じモデルを続きから学習させているのに、明らかに学習速度が初回に比べて遅い（または速い）
といった現象がわりと起こりました。（もちろんGPUは同じ）
具体的に1エポックごとの時間を比較してみると、1.5~2倍遅い（または速い）。
原因は正直不明なのですが、
また、追加のメモリを備えた仮想マシンが必要になりそうだということが Colab で検出されると、自動的にメモリの割り当てられる場合があります。
とある（原文そのまま）ので、おそらくメモリが割り当てられたときが速く、そうでないときが遅いのかなと思います。
最後に
なんかColabをディスったみたいな記事になりましたが、大好きですColab！
無料でこんなにGPUを使えるのはありがたすぎる！！
GPUがのったパソコンを買おうかと考えた時がありましたが、Colab Proに課金した方が確実にコスパ良さそうな気がしますね！
見てくれてありがとうね！
